Fine-Grained Classification of Detecting Dominating Patterns

If $S=\mathrm{\varnothing }$, then $V(P)=R$ and Lemma 3.6 applies to all of $P$. Recall that any dominating set of size $k$ contains a heavy vertex $v_h$ (a vertex of degree at least $n/k-1$), hence we can first guess this vertex in time $𝒪(\frac{m}{n})$. By Lemma 3.4, there is a spanning subgraph of $P$ that is isomorphic to a disjoint union of edges and odd cycles and we can find such a spanning subgraph in $f(k)=𝒪(1)$ time. Assume that this decomposition yields $\alpha$ odd cycles and $\beta$ disjoint edges. If $\beta >0$, we show that we can decompose $P-v_h$ further into two graphs $B_1,B_2$ such that they satisfy the following conditions:

• $\mathrm{■}$

  Each $B_i$ is a disjoint union of independent $P_3$’s (paths of length two) and $K_2$’s (independent edges), such that each copy of $P_3$ will correspond to a subgraph of $G$ that is isomorphic to $P_3$ and whose all vertices either have degree at most $\sqrt{m}$, or one of the endpoints has degree at least $\sqrt{m}$. ⁶⁶6Hence in $G$ we will be able to enumerate all subgraphs isomorphic to $P_3$ that fulfill this degree requirement in time $𝒪(m^{3/2})$.

• $\mathrm{■}$

  $B_1\cup B_2$ is a spanning subgraph of $P-v_h$.

• $\mathrm{■}$

  (Without loss of generality) $0\le |V(B_1)|-|V(B_2)|\le 2$.

• $\mathrm{■}$

  We can enumerate all copies of $G$ isomorphic to $B_i$ that satisfy the degree constraints of $P_3$ in time $𝒪(m^{|B_i|/2})$.

In particular, for $k\ge 16$, we have $|V(B_1)|+|V(B_2)|=k-1\ge 15$, and combining this with the inequality above, we can conclude that $|V(B_1)|\ge |V(B_2)|\ge 7$. Using that the rectangular matrix multiplication constant $\alpha \ge 0.321$, and that $m\ge n$, we for the exponent

and hence we obtain for all $k\ge 16$:

If on the other hand $\beta =0$ (i.e. the decomposition contains only copies of odd cycles), we proceed similarly, but the best bound on the size difference between $B_1$ and $B_2$ is $0\le |V(B_1)|-|V(B_2)|\le 3$, which is not good enough in general. To get around this issue, we distinguish between two cases. If there exists a vertex in $P-v_h$ that is mapped to a vertex of degree $\ge \sqrt{m}$ in $G$, we can make sure that there exists a copy of $P_3$ whose one endpoint will be mapped to a vertex in $G$ that has degree at least $\sqrt{m}$. We can decompose this $P_3$ further into an edge and a vertex of degree $\ge \sqrt{m}$, and intuitively use these components to “re-balance” the sets $V(B_1)$ and $V(B_2)$ as above. If on the other hand all vertices in $P-v_h$ are mapped to vertices in $G$ that have degree at most $\sqrt{m}$, we then know that if $|Y|:=|G-N_G[v_h]|\ge (k-1)\sqrt{m}+1$, there is no valid solution. If on the other hand $|Y|\le (k-1)\sqrt{m}$, by Lemma 3.1, we can find any such solution in time bounded by $𝒪\left(\frac{m}{n}\mathrm{MM}(m^{\frac{|V(B_1)|}{2}},\sqrt{m},m^{\frac{|V(B_2)|}{2}})\right)$. Similarly as in previous case, for $k\ge 16$, we get that $|V(B_1)|\ge |V(B_1)|\ge 6$ and again since $\alpha \ge 0.321$, we obtain $\omega (1,\frac{1}{|V(B_1)|},1)=\omega (1,\frac{1}{|V(B_2)|},1)=2$. Hence, we can bound the time complexity as

$◀$ The second case for basic patterns is that the decomposition into $S$, $N(S)$ and $R$ as in Definition 1.1 yields $S\ne \mathrm{\varnothing }$. Intuitively this case is simpler than the one above, since we can use the sets $S,N(S)$ to simulate $\beta >0$, even if $\beta =0$ and “balance” the sets $V(B_1)$ and $V(B_2)$. We only sketch the proof, as the details are quite similar to the ones above.

Similarly as above, construct the sets $B_1$ and $B_2$ by finding a spanning subgraph of $P[R]$ that consists of union of independent $P_3$’s and $K_2$’s and distributing the connected components as equally as possible. Clearly, we have that $|V(B_1)|+|V(B_2)|=|R|$, and (without loss of generality) $0\le |V(B_1)|-|V(B_2)|\le 3$. Since $S\ne \mathrm{\varnothing }$, also $N(S)\ne \mathrm{\varnothing }$ (by definition $S$ contains no isolated vertices), hence we can distribute the edges from a perfect matching between the set $N(S)$ and some subset of $S$ of size $|N(S)|$ (such perfect matching always exists by Hall’s marriage theorem) between the sets $B_1$ and $B_2$ similarly as in previous lemma to obtain graphs $B_1^{\prime },B_2^{\prime }$. Clearly, it holds that $|V(B_1^{\prime })|+|V(B_2^{\prime })|=2|N(S)|+|R|$ and (without loss of generality) $0\le |V(B_1^{\prime })|-|V(B_2^{\prime })|\le 2$. We then define the graphs $Q_1,Q_2$ that consist of $\lfloor \frac{|S|-|N(S)|}{2}\rfloor$ and $\lceil \frac{|S|-|N(S)|}{2}\rceil$ isolated vertices respectively. Similarly as above, we can enumerate all subgraphs of $G$ isomorphic to $B_i^{\prime }\cup Q_i$ in time $𝒪\left(n^{|Q_i|}{m}^{\frac{|B_i^{\prime }|}{2}}\right)$. Also, by similar arguments as above, we have that for $k\ge 16$, the matrices are “thin enough” that rectangular matrix multiplication techniques can be used to obtain the tight running time of

$◀$

We first guess a heavy vertex $w$ (a vertex satisfying $\mathrm{deg}(w)\ge n/3-1$). We then run a breadth-first-search from $w$ and let $\left(X_0=\{w\},X_1,\mathrm{\dots },X_n\right)$ be the obtained BFS layering. Note that for any $\mathrm{\ell }\ge 3$, if $X_{\mathrm{\ell }}$ is non-empty, we can conclude that there is no dominating clique that contains $w$ and we can proceed with the next choice of the heavy vertex. Otherwise, finding any dominating triangle in $G$ that contains $w$ is equivalent to finding an edge $u,v$ in $X_1$ that dominates all vertices in $X_2$. For any vertex $u$, we write $N_2(u):=N(u)\cap X_2$. Using the principle of inclusion-exclusion, we can write $|N_2(u)\cup N_2(v)|=|N_2(u)|+|N_2(v)|+|N_2(u)\cap N_2(v)|$. We note that for any pair of vertices $u,v\in X_1$ the value $|N_2(u)\cap N_2(v)|$ corresponds to the number of triangles containing the edge $uv$. Hence, by employing the algorithm from Lemma 3.11, we obtain the desired time. $◀$ On the other hand, by coming up with a more involved argument, we are able to construct a randomized algorithm that matches the lower bound (up to resolving the matrix multiplication exponent $\omega$) for the remaining small pattern, namely Dominating $4$-Clique. The algorithm starts similarly as above. That is, we first guess a heavy vertex $w$ in time $𝒪\left(\frac{m}{n}\right)$, and then we partition the vertices into two sets $X_1$ and $X_2$ based on the distance from $w$ and thus reduce to detecting a triangle in $X_1$ that dominates $X_2$. We then consider two cases based on the size of $X_2$. If $|X_2|\le 3\sqrt{m}$, this turns out to be quite easy, and boils down to using standard matrix multiplication algorithms (with a bit more careful analysis). If on the other hand $|X_2|>3\sqrt{m}$, we then either reduce to counting cliques (triangles and $K_4$’s) in a certain restricted setting, or use the randomized bloom-filter based approach of [21] (with a finer-grained analysis) to achieve the desired running time. This approach gives us the proof of Theorem 3.10 and we provide the detailed proof in the full version of the paper.

If $r=k$, then this problem is precisely the Maximal $k$-Independent Set problem, and by [30] can be solved in the time bounded by ${\left(\frac{m^{(k-1)/2+\omega /2}}{n}\right)}^{1+o(1)}$, as desired. Hence, we may assume that $2\le r\le k-2$ (if $P$ contains at least one edge, then at least two vertices have degree $\ge 1$). Let $X:=\{x\in V(P):{\mathrm{deg}}_P(x)\ge 1\}$ and $Y:=V(P)\setminus X$ be the set of non-isolated and isolated vertices in $P$ respectively. Let $S,N(S),R$ be the partition of $V(P)$ as in Definition 1.1. We can enumerate all induced subgraphs of $G$ isomorphic to $P[X]$ in some time $𝒪\left(t_{P[X]}^{(1)}(n,m)\right)$ (the ratio of the size of this set to $t_{P[X]}(n,m)$ depends only on whether the set $S$ is empty or not). For each enumerated subgraph $H$, we appeal to the randomized Dominating $r$-Independent Set algorithm from [30] on the graph $G-N[H]$ that runs in $𝒪\left(t_r^{(2)}(n,m)\right)$ (depends on which vertex from $P$ is mapped to a heavy vertex). It is straightforward to see that this algorithm is correct. We conclude the proof by showing that the product of $t_{P[X]}^{(1)}(n,m)$ and $t_r^{(2)}(n,m)$ is in all cases bounded by $t_P(n,m)$ (see the full version of the paper for details). $◀$

Things get slightly more complicated when dealing with patterns that only have one isolated vertex. In particular, the preprocessing part of the algorithm above takes in the worst case $\mathrm{\Theta }\left(t_{P[X]}(n,m)\cdot m\right)$, while for pattern graphs with only one isolated vertex, we have $t_P(n,m)=𝒪\left(t_{P[X]}(n,m)\cdot \sqrt{m}\right)$. To circumvent this overhead, we employ a more careful analysis and use a hashing-based approach similar to that in Section 3.2. We first provide an algorithm for two special cases of some of the smallest patterns that exhibit this structure and then the idea is to reduce any pattern to one of these special cases.

Without loss of generality, assume that $\mathrm{deg}(u)\ge \mathrm{deg}(v)$. Let $t$ be such that $t\le \mathrm{deg}(u)\le 2t$. Assume first that $t\le \sqrt{m}$. Then each vertex $u,v,w$ has degree bounded by $𝒪(\sqrt{m})$ and so, if there exists a valid triple that dominates $Y$, the size of $Y$ must also be bounded by $𝒪(\sqrt{m})$. Hence by Lemma 3.1 we can enumerate all valid triples in time $\mathrm{MM}(m,\sqrt{m},\sqrt{m})\le m^{(\omega +1)/2+o(1)}$, as desired.⁷⁷7Since vertices $u,v$ are adjacent, there are at most $m$ choices for this pair, and $w$ is by assumption in $Y$, and $|Y|\le 𝒪(\sqrt{m})$ For the rest of this proof we assume that $t\ge \sqrt{m}$. We now proceed to enumerate all valid triples $u,v,w$ such that $\mathrm{deg}(v)\le \sqrt{m}$. To this end, we run the following routine. For each of the $𝒪(m/t)$ valid choices for the vertex $u$, construct the tripartite graph $H_u=(V_u^{(1)}\cup V_u^{(2)}\cup V_u^{(3)},E_u)$, where $V_u^{(1)}$ corresponds to a copy of $N(u)$, while $V_u^{(2)}$ and $V_u^{(3)}$ each correspond to a copy of the set $Y-N(u)$. The set of edges $E_u$ is constructed naturally, that is, for each pair $x\in V_u^{(i)},y\in V_u^{(j)}$ for $i\ne j$ we add an edge $xy$ if and only if the edge between the corresponding vertices is present in $G$ (we assume that each vertex is adjacent to itself in $G$). It is easy to see that for any fixed $u$, any valid choice of $v,w$ corresponds precisely to a choice of $v\in V_u^{(1)}$ and $w\in V_u^{(2)}$ such that the following two conditions are satisfied: 1) $V_u^{(3)}\subseteq N(w)\cup N(v)$ and 2) $vw\notin E(H_u)$. Now, since we are only enumerating triples $u,v,w$ where both $v,w$ have degrees at most $\sqrt{m}$, if for a fixed $u$ the set $V_u^{(3)}$ contains more than $2\sqrt{m}$ vertices, we can conclude that no pair $v,w$ satisfies both conditions and proceed with the next choice of $u$. On the other hand, if $|V_u^{(2)}|=|V_u^{(3)}|\le 2\sqrt{m}$, by Lemma 3.1, for any fixed $u$, we can enumerate all the valid pairs of non-adjacent vertices $v,w$ that dominate $Y-N(u)$ in time

Repeating this for each of the possible $𝒪(m/t)$ many choices of vertex $u$ yields the desired time. It remains to enumerate the triples of vertices $u,v,w$ where $\mathrm{deg}(v)\ge \sqrt{m}$. Recall also that $2t\ge \mathrm{deg}(u)\ge \mathrm{deg}(v)$ and $t\ge \sqrt{m}$. Hence, since by the first condition of the Lemma, we are only interested in the triples $u,v,w$ with $\mathrm{deg}(w)\le \sqrt{m}\le t$, if the set $Y$ contains more than $5t$ vertices, we can conclude that no triple $u,v,w$ satisfies $Y\subseteq N[u]\cup N[v]\cup N[w]$. Hence, we can assume that $Y\le 5t$. Let $B$ be a matrix whose rows correspond to adjacent pairs of vertices $u,v$ with $t\le \mathrm{deg}(u)\le 2t$ and $\mathrm{deg}(v)\ge \sqrt{m}$ and whose columns correspond to the set $Y$. We set the entry $B[(u,v),y]$ to $0$ if either $u$ or $v$ are adjacent to $y$ and to $1$ otherwise. Similarly, we construct a matrix $C$ whose columns correspond to the set of vertices $w\in Y$ such that $\mathrm{deg}(w)\le \sqrt{m}$ and the rows correspond to $Y$. Set the entry $B[y,w]$ to $1$ if $w$ and $y$ are adjacent (we understand that each vertex is adjacent to itself) and $0$ otherwise. Notice that $u,v,w$ dominate $Y$ if and only if $(B\cdot C)[(u,v),w]={\sum }_{k}B[w,k]$ (each vertex that is not dominated by the pair $(u,v)$ is dominated by $w$). Also notice that the matrix $B$ is an $𝒪\left(\frac{m\sqrt{m}}{t}\right)\times 𝒪\left(t\right)$ and $C$ is an $𝒪\left(t\right)\times 𝒪\left(t\right)$ matrix with at most $m$ non-zeros. Hence by a Lemma from [21] (see full version for details), we can enumerate with high probability all valid triples $u,v,w$ in time $\sqrt{m}\cdot m^{\omega /2+o(1)}=m^{\frac{\omega +1}{2}+o(1)}$, as desired. We remark that we enumerate all valid triples for any fixed $t$ in the claimed time. To enumerate all the valid triples, simply run the previous algorithm $𝒪(\log (n))$ times, once for each $\mathrm{\ell }\in 1,\mathrm{\dots },\lfloor \log (n)\rfloor$, setting $t=2^{\mathrm{\ell }}$. $◀$ An almost identical argument as in previous lemma can also be used to show that we can efficiently enumerate the solutions that are isomorphic to $C_{2r+1}+K_1$.