Witness-Sensitive Detection of Induced Diamonds

Abstract

We provide a fast \emph{witness-sensitive} algorithm for detecting an induced diamond (a $K_4$ minus an edge) in an $n$-vertex graph containing $t$ induced diamonds. Our algorithm runs in time $\tilde{O}(\min(n^{2.425}/t^{0.25}+n^2, n^ω))$ with high probability, improving upon the prior state of the art (witness-oblivious) algorithm that runs in time $O(n^ω\log{n})$ [Vassilevska Williams, Wang, Williams, Yu, SODA 2014] whenever $t \geq n^{(3-ω)/3}$, where $ω< 2.372$ is the matrix multiplication exponent. Our key insight is that the size of a clique containing one of the triangles of an induced diamond plays a crucial role in detecting such a diamond. We say that a diamond is $r$-heavy if this size is at least $r$, and we provide a fast detection algorithm for $r$-heavy diamonds in $\tilde{O}(r \cdot (n/r)^ω+ (n/r)^3+ nr)$ time. When there are no $r$-heavy diamonds, we provide a different fast detection algorithm in $\tilde{O}(\mathsf{MM}(n,n,n\sqrt{r/t}))$ time, where $\mathsf{MM}(a,b,c)$ denotes the time to multiply an $a \times b$ matrix by a $b \times c$ matrix, which is conditionally optimal for $r=\tilde{O}(1)$. Our main technical contribution is in designing a refinement framework for sampling vectors, which allows sampling vertices for detecting diamonds in a manner that is adaptive to the structure of graphs with no $r$-heavy diamonds. We establish that our technique is of a wide applicability, by showing how it also allows for faster witness-sensitive algorithms for $4$-SUM and for a special case of $4$-cycles.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.