Witness-Sensitive Detection of Induced Diamonds

Our first algorithm detects an $r$-heavy induced diamond with a running time that improves as $r$ increases. At a high level, we are looking for an edge that is contained in two different maximal cliques, as such an edge implies an induced diamond. Intuitively, one might expect that the presence of an $r$-heavy diamond would make detection easier via sampling. However, we must be careful: there may be only one such special edge in the graph, making it hard to sample directly.

Concretely, we use the aforementioned edge-based characterization of diamond-free graphs: $G$ is diamond-free if and only if every edge of $G$ is contained in exactly one maximal clique [19, Lemma 7]. We call an edge that lies in two or more maximal cliques a violating edge, since its existence implies an induced diamond. For an edge $e=(u,v)$, we can test whether it is violating in $O(n^2)$ time by computing $W(e)\triangleq (N(u)\cap N(v))\cup \{u,v\}$ and checking whether $W(e)$ is a clique: $e$ is violating if and only if $W(e)$ is not a clique. This yields a simple $O(m{n}^2)$ time algorithm for induced diamond detection. While this can be improved upon as mentioned earlier [29, 55], this approach does not benefit from the fact that there is an $r$-heavy diamond.

We strengthen this characterization as follows to leverage the existence of an $r$-heavy diamond. We know that there exists a violating edge that lies in a clique of size at least $r$, called an $r$-heavy violating edge. Is finding such an edge any easier? We cannot sample $o(m)$ edges and expect to hit an $r$-heavy violating edge with good probability, since there may be only one such edge (see Figure 2(a)). Luckily, an $r$-heavy violating edge implies the existence of many other edges that are easier to find, and we can use them to find the violating edge itself, as follows. Given an $r$-heavy violating edge $f$ that lies in a clique $C$ of size at least $r$, we refer to every edge in $C$ as an $r$-heavy revealing edge. While there might be only one $r$-heavy violating edge, it implies at least $\mathrm{\Omega }(r^2)$ distinct $r$-heavy revealing edges (the edges in $C$). Therefore, we can sample $o(m)$ edges and expect to hit an $r$-heavy revealing edge with good probability. We then use it to find the violating edge $f$.

Given this observation, our goal is to (1) sample a small set of vertices $S$ that induces a small set of edges $L$ containing an $r$-heavy revealing edge w.h.p., and (2) efficiently test whether an edge $e\in L$ is $r$-heavy revealing. We provide a simple procedure to test whether an edge $e$ is revealing in $O({|W(e)|}^2+n)$ time: first check whether $W(e)$ is a clique (if not, $e$ is already violating); if it is, search for a neighbor $z\notin W(e)$ connected to two vertices in $W(e)$. To avoid processing large cliques, we only test edges $e$ such that $|W(e)|\in [r,2r)$. That is, we run the same algorithm in a round-robin fashion with different values of $r$ until one of them detects an induced diamond. Specifically, we run the algorithm for values of $r=2^i$ for $i=0,1,2,\mathrm{\dots },\log n$, where the $i$-th iteration samples $\tilde{O}({(n/2^i)}^2)$ edges, and tests only edges $e$ with $|W(e)|\in [2^i,2^{i+1})$. In what follows, we analyze the $i$-th iteration for which $r_{\max }/2\le 2^i\le r_{\max }$. This iteration is guaranteed to find an $r$-heavy revealing edge w.h.p. and its running time is the fastest among all iterations that find such an edge.

To obtain $L$, we select a random subset $S$ of $\mathrm{\Theta }(n\log n/r)$ vertices. Then, using fast matrix multiplication, we compute $|W(e)|$ for every $e$ with both endpoints in $S$ in $\mathrm{𝖬𝖬}(|S|,n,|S|)=\tilde{O}(r\cdot {(n/r)}^{\omega })$ time, where we add an edge $e$ to $L$ if $|W(e)|\in [r,2r)$. Clearly, the size of $L$ is at most the square of the size of $S$. So far, we explained how to find $L$ in $\tilde{O}(r\cdot {(n/r)}^{\omega })$ time, and how to process it in time $O(\left|L\right|\cdot (r^2+n))=\tilde{O}(n^2+n^3/r^2)$.

We improve upon the above processing time via two modifications. First, we modify the algorithm so that after processing an edge $e\in L$, it removes from $L$ all edges with both endpoints in $W(e)$. Note that this never removes an edge $e^{\prime }$ that is a revealing edge, for the following reason. Let $e^{\prime }$ be such a removed edge and consider its set $W(e^{\prime })$. If $W(e^{\prime })=W(e)$, then $e^{\prime }$ is revealing if and only if $e$ is revealing, so testing $e^{\prime }$ in addition to $e$ is redundant. If $W(e^{\prime })\ne W(e)$, then $e^{\prime }$ is itself a violating edge, which means that $e$ is a revealing edge and the algorithm would terminate when processing $e$.

Second, we provide an improved analysis that shows that the algorithm stops after processing $\tilde{O}(n/r+n^2/r^3)$ edges, which is better than the trivial bound of $|L|=\tilde{O}({(n/r)}^2)$. To see why, let $e_i$ be the $i$-th edge that is processed, and consider the auxiliary bipartite graphs $F_i$ with parts $(W(e_1),W(e_2),\mathrm{\dots },W(e_i))$ and $V(G)$, in which the clique $W(e_j)$ is connected to the vertex $v$ if and only if $v\in W(e_j)$. We show that if $F_i$ contains a cycle of length at most $6$, then the algorithm stops while processing the first $i$ edges. To illustrate this, suppose that $F_i$ contains a $4$-cycle while $F_{i-1}$ does not. Then $W(e_i)$ shares two vertices $(x,y)$ with some previous clique $W(e_j)$, meaning that $(x,y)$ is a violating edge and every edge in $W(e_i)$ is $r$-revealing. Therefore, when processing $e_i$, the algorithm determines its revealing edge and stops, without processing any further edge. For $6$-cycles, the argument is more complex but similar. Classical bounds on edge count in unbalanced bipartite graphs with no $4$-cycle or $6$-cycle [45, 47] imply that for $i\ge 64(n/r+n^2/r^3)$, the graph $F_i$ contains a cycle of length at most $6$.¹¹1Note that showing that either $F_i$ has no short cycle or we encounter a diamond does not seem to generalize to larger cycles (which would yield a better bound), as an $8$-cycle does not necessarily imply a diamond. Therefore, the algorithm processes at most $O(n/r+n^2/r^3)$ edges. To summarize, we find the set $L$ in $\tilde{O}(r\cdot {(n/r)}^{\omega })$ time and process only $O(n/r+n^2/r^3)$ edges from $L$, each in $O(r^2+n)$ time, for a total time of $\tilde{O}(r\cdot {(n/r)}^{\omega }+n^3/r^3+nr)$.

Our second algorithm targets the regime where many induced diamonds are $r$-light. Our starting point is the sampling framework of [53, 17, 18] that takes a $k$-vertex subgraph detection algorithm and converts it into a witness-sensitive algorithm. We describe how it works for induced diamond detection, the algorithm needed to use it, why this is hard, and finally our main technical novelty for obtaining the required algorithm.

In the framework, we assign a random coloring $\phi :V(G)\to [4]$ and search for colorful patterns, i.e., patterns whose $4$ vertices have $4$ distinct colors. This consists of two steps: (1) sampling $\tilde{O}(1)$ induced subgraphs, and (2) searching for colorful induced diamonds in each one.

The sampling step uses the color classes to sample vertices with different probabilities. Specifically, each sampled subgraph $H$ is obtained by sampling vertices of color $i$ with probability $p_i$ for $i\in [4]$. We refer to the sampling probabilities as a sampling vector denoted by $P=(p_1,p_2,p_3,p_4)$, and we denote the sampled subgraph by $H\leftarrow G[P]$. To obtain our collection of induced subgraphs, we consider all sampling vectors in $ℱ={\{1,1/2,1/4,\mathrm{\dots },1/n\}}^4$ and sample one subgraph for each $P\in ℱ$. Note that the sampling vectors are independent of the underlying pattern we want to find. The key guarantee of the framework is that if $G$ contains $t$ induced diamonds, then there exists a good $P\in ℱ$ such that $H\leftarrow G[P]$ contains a colorful induced diamond with $\tilde{\mathrm{\Omega }}(1)$ probability and $w(P)=\tilde{O}(1/t)$, where $w(P)={\prod }_{i=1}^4{p}_i$ is the weight of $P$.

The second step is to search for a colorful induced diamond in $H$. Assume that $P$ is the promised good sampling vector. To illustrate the potential speedup and challenges, consider two extreme cases, depending on whether $P$ is the balanced vector $P_{\mathrm{balanced}}=(p,p,p,p)$ for $p=1/t^{1/4}$, or an unbalanced vector, such as $P_{\mathrm{unbalanced}}=(1,1,1,1/t)$. For $H\leftarrow G[P_{\mathrm{balanced}}]$, the graph $H$ has $O(n/t^{1/4})$ vertices, so faster colorful induced diamond detection on $H$ sounds plausible. For the unbalanced case, things are more complicated. For $H\leftarrow G[P_{\mathrm{unbalanced}}]$, the graph $H$ has $\mathrm{\Theta }(n)$ vertices and possibly $\mathrm{\Theta }(|E(G)|)$ edges, so $H$ is not sparser than $G$.

We show that a refined analysis of the sampling framework does yield a speedup when many induced diamonds are $r$-light. Previously, we argued that in the worst case, every induced diamond might contain the same triplet of vertices, e.g., $(v_1,v_2,w_1)$ in Figure 2(a), and therefore the only good sampling vector was $P_{\mathrm{unbalanced}}=(1,1,1,1/t)$. In this case, however, the three repeated vertices lie in a large clique, so there exists an $r$-heavy diamond. Specifically, let $W=N(v_1)\cap N(v_2)$ be the common neighborhood of $v_1,v_2$, and let $W^{\prime }=W\setminus \left\{w_1\right\}$. If $(v_1,v_2,w_1)$ are the three vertices in all induced diamonds, then $W^{\prime }$ is a clique, and every diamond is $|W^{\prime }|$ heavy. In this case, we use the $r$-heavy diamond detection algorithm. On the other hand, for sufficiently small $r$ that is a function of $t$, the $r$-light diamond detection algorithm is faster. We do not know for which $r$ to switch between the two algorithms²²2Since rectangular matrix multiplication has no closed-form expression, we cannot find, for every $t$, the value of $r$ for which the two running times are equal. but we do not need this information; rather, we simply run both algorithms in parallel and stop when one of them detects an induced diamond. To illustrate when the $r$-light diamond algorithm is faster, assume that there is no $r$-heavy diamond for $r\le {|W|}^{1-\epsilon }$ for some constant $\epsilon >0$. Then $W^{\prime }$ is not a clique, and by Turán’s theorem there are many non-edges in $G[W]$, specifically at least $\mathrm{\Omega }({|W|}^2/r)=\mathrm{\Omega }({|W|}^{1+\epsilon })$ non-edges, so there must be at least $\mathrm{\Omega }({|W|}^{\epsilon })$ vertices in $W$ that are endpoints of non-edges, proving that no vertex in $W$ is “too” important. Therefore, we can hope to find a good sampling vector that is more balanced than $P_{\mathrm{unbalanced}}$. Specifically, we show that $P=(1,1,\sqrt{r/t},\sqrt{r/t})$ hits an induced diamond with $\tilde{\mathrm{\Omega }}(1)$ probability. This illustrates how having no $r$-heavy diamonds simplifies the family of graphs we have to deal with. Yet, we still need to handle general graphs with no $r$-heavy diamonds, and we cannot assume that there are only two Deg3 vertices as in the above example. To get our speedup, we show that either $x_3=\tilde{\mathrm{\Omega }}(\sqrt{t/r_{\max }})$, i.e., there are many Deg3 vertices, or that $P=(1,1,\sqrt{r_{\max }/t},\sqrt{r_{\max }/t})$ hits a colorful induced diamond with $\tilde{\mathrm{\Omega }}(1)$ probability, where in both cases we obtain a running time of $\tilde{O}(\mathrm{𝖬𝖬}(n,n,n\cdot \sqrt{r_{\max }/t}))$. To prove that $P=(1,1,\sqrt{r/t},\sqrt{r/t})$ hits a colorful induced diamond with probability $\tilde{\mathrm{\Omega }}(1)$, our main technical contribution deviates from the black-box use of the sampling framework. Specifically, we show that we can combine the framework (which is oblivious to $G$) with structural properties implied by $r$-lightness to obtain a faster algorithm. Our proof gradually refines the sampling vector from $P^{(1)}=(1/t)$ to $P^{(4)}=(p_1,p_2,p_3,p_4)$ by extending its dimension (i.e., the number of coordinates) in a very subtle manner.