The Art Gallery Guardian

The high-degree low-degree technique and arboricity


In this piece we demonstrate the high-degree low-degree technique in graphs. Often, we obtain running times that depends on the individual degrees of the vertices. If the graph has only low degree vertices, then a faster algorithm exists. For graph with only large degrees, then it is dense, and can often be handled in another way.

We will also use the information of arboricity. Mainly, there are a few useful statements.

Theorem1

For a graph G=(V,E)G=(V,E) with arboricity α\alpha, we have uvEmin(deg(u),deg(v))2αm \sum_{uv\in E} \min(\deg(u),\deg(v)) \leq 2\alpha m

Often, using the arboricity, we can obtain the same complexity algorithm without high-degree low-degree technique. Note the arboricity is O(m)O(\sqrt{m}). The application of arboricity are from [1].

Some of the algorithms described can be speedup by using matrix multiplication, or faster combinatorial boolean matrix multiplication. We avoid them for simplicity of exposition.

1 Dominating set with few edges

The set cover problem, given S={S1,,Sn}\mathcal{S} = \set{S_1,\ldots,S_n} are nn set contains a total of mm elements. U=SSSU=\bigcup_{S\in \mathcal{S}} S is the universe, with size uu.

Theorem2

There is a probability distribution DD over S\mathcal{S}, such that for each uu, the probability a random set SS covers uu is at least ε\e. There exists a set cover of loguε\ceil{\frac{\log u}{\e}}.

Proof

There exists a set that covers at least εU\e |U'| for any UUU' \subset U. Therefore each greedy iteration decrease the size of uncovered universe by an ε\e fraction. So there can be at most tt iterations, where (1ε)t<1(1-\e)^t<1. One can show loguε\ceil{\frac{\log u}{\e}} suffices.

Theorem3

There is a dominating set incident to O(nnlogn)O(n\sqrt{n\log n}) edges.

Proof

Fix a δ\delta. We repeatedly removing vertices with degree no more than δ\delta from the graph, and add it into a set DD. The total degree of DD is at most nδn\delta. Now the remaining vertices has degree at least δ\delta. Using the set cover theorem, and let the distribution to be the uniform distribution. If all elements are covered at least by ε\e fraction of the set, then we obtain a set cover of size O(loguε)O(\frac{\log u}{\e}). Now, let the sets N(v)N(v) for each vv. Since degree is bounded by at most nn, we can obtain a dominating set of size O(nlogne)O(\frac{n\log n}{e}). We set ε=δ/n\e=\delta/n. Since the degree of each vertex is at least δ\delta, then there is a covering of O(n2lognδ)O(\frac{n^2\log n}{\delta}). Add the vertices induces this set cover to DD. DD is a dominating set, and its size is O(nδ+n2lognδ)O(n\delta +\frac{n^2\log n}{\delta}), set δ=nlogn\delta=\sqrt{n\log n} and we obtain the desired result.

One can show the above result is almost optimal, as there exists graphs where every dominating set incidents Ω(n3/2)\Omega(n^{3/2}) edges. The same bound holds for weakly connected dominating set, that is a dominating set DD such that the edges incident to DD forms a connected graph. The stronger modification of this result was used in deciding the 44-connectivity of a matroid [2].

2 Finding small subgraphs

2.1 Finding a triangle

A triangle is 33 vertices pairwise adjacent to each other, another name for K3K_3.

Theorem4

There is a O(mΔ)O(m\Delta) time algorithm to decide if the graph has a triangle, where Δ\Delta is the maximum degree.

Proof

Indeed, for each vertex vv, we consider its neighbors, see if any is adjacent to each other. We then delete vv. The algorithm takes O(vdeg2(v))=O(mΔ)O(\sum_{v} \deg^2(v)) = O(m\Delta) time.

Theorem5

There is a O(n3)O(n^3) time algorithm to decide if the graph has a triangle.

Proof

The naive algorithm, for each 33 vertices, we decide if it forms a triangle.

Theorem6

There is a O(m3/2)O(m^{3/2}) time algorithm to decide if the graph has a triangle.

Proof

Let tt be a parameter we will find later. Apply the above algorithm by picking the vertex with the smallest degree, until the next vertex has degree at least tt. It will use at most O(mt)O(mt) time. Now, for the remaining graph, it is clear the maximum degree is at least tt. Note, there can be at most n/tn/t vertices. We use the O(n3)O(n^3) time algorithm. The final running time is O(mt+(m/t)3)O(mt+(m/t)^3). Set t=mt=\sqrt{m} and we are done.

ProofAlternative

We modify the algorithm a little. For each vertex vv, we consider its neighbor uu, and check if uu has a neighbor that is in vv. Then we delete vv, and move on to next vertex. The running time become vV(deg(v)+uN(v)deg(u))\sum_{v\in V} (\deg(v)+\sum_{u\in N(v)} \deg(u)). Now, assume we pick vertices by the largest to smallest in term of degrees. We rearrange the sum and obtain vV(deg(v)+uN(v)deg(u))=vVdeg(v)+2uvEmin(deg(u),deg(v))=O(αm)\sum_{v\in V} (\deg(v)+\sum_{u\in N(v)} \deg(u)) = \sum_{v\in V} \deg(v) + 2 \sum_{uv\in E} \min(\deg(u),\deg(v)) = O(\alpha m). Because αm\alpha\leq \sqrt{m}, we have the running time O(m3/2)O(m^{3/2}).

2.2 A motivating problem

Let S1,,SnS_1,\ldots,S_n be sets with total of mm elements. How quickly can we find two distinct ii and jj such that SiSj|S_i\cap S_j|\geq \ell? This problem can be shown to be equivalent to finding a colored K2,K_{2,\ell} in a bipartite graph. That is, for input bipartite graph G=(A,B,E)G=(A,B,E). Find a K2,K_{2,\ell} where the side of two vertices has to be in AA.

2.3 Finding a C4C_4 in bipartite graphs

This section we use technique that follows from [3]. Although we are into finding C4C_4, but some theorems are more general for K2,K_{2,\ell}, so we will state them too. Note finding a colored K2,2K_{2,2} and finding a K2,2K_{2,2} is the same problem due to symmetry.

Let v1,,vnv_1,\ldots,v_n be an ordering such that deg(vi)deg(vj)\deg(v_i)\geq \deg(v_j). There exists an algorithm that finds an ordering of vertices v1,,vnv_1,\ldots,v_n, and returns Ni(vi)Ni(vj)N_i(v_i)\cap N_i(v_j) for each ii and j>ij>i. Here Ni(v)N_i(v) is the set of neighbors of vv in G[{vi,,vn}]G[\set{v_i,\ldots,v_n}]. Here we show an algorithm solves the above problem when the arboricity is small.

The algorithm is as follows [1]. Take vv, we consider each neighbor uu. Maintain a set SwS_w for each vertex ww distance 22 from vv. Add uu into each of uu’s neighbor in ww. SwS_w would give us information of N(v)N(w)N(v)\cap N(w). We delete vv and keep going. It is known the algorithm takes O(α(G)m)O(\alpha(G)m) time. This allows us to compute C4C_4 in the same time. Hence we directly obtain O(m3/2)O(m^{3/2}) running time. However, we show something better is possible if we are not interested in finding all C4C_4, but find any C4C_4. We also need the following theorem.

Theorem7

One can check if there exists a K2,K_{2,\ell} in the bipartite graph G=(A,B,E)G=(A,B,E) in O(n2)O(\ell n^2) time.

Now, we combine the two algorithms. It requires a theorem in extremal graph theory can be found in [4].

Theorem8K2,K_{2,\ell}-free theorem

There exists a constant cc, such that each nn vertex graph with cn3/21/2c n^{3/2} \ell^{1/2} edges contains a K2,K_{2,\ell}.

Theorem9

There is a O(m4/3)O(m^{4/3}) time algorithm to find a C4C_4 in the graph.

Proof

If the arboricity is tt. We use the first algorithm and we get running time O(tm)O(t m). Otherwise, we know there is a subgraph with minimum degree at least tt. The subgraph can be found by repeatedly deleting vertices of minimum degree. The subgraph GG' with the previous property has nnn'\leq n vertices and mntm'\leq n't edges. One can see nm/tm/tn'\leq m'/t\leq m/t. If cn3/2mntcn'^{3/2}\leq m' \leq n't, then we know there exists a C4C_4 in GG' by the previous theorem, and we can apply the O(n2)O(n^2) time algorithm in the subgraph to find the C4C_4. The total running time is therefore O(tm+n2)=O(tm+(m/t)2)O(tm + n'^2) = O(tm+(m/t)^2). We set t=c3/2m1/3t=c^{3/2} m^{1/3}. One can check after lot of algebra, it make sure the condition cn3/2ntcn'^{3/2}\leq n't is satisfied. The algorithm takes O(m4/3)O(m^{4/3}) time.

2.4 Finding a colored K2,3K_{2,3} in bipartite graphs

For finding K2,K_{2,\ell}, the low arboricity algorithm for C4C_4 works here. The O(α(G)m)O(\alpha(G)m) algorithm is still fine. It’s not hard to generalize and show a O(1/3m4/3)O(\ell^{1/3}m^{4/3}) running time algorithm.

However, in order to solve the motivating problem. We need a colored K2,K_{2,\ell}.

Let’s consider a K2,K_{2,\ell} in GG, and consider the first indexed vertex vv. If vAv\in A, then we are done, as the algorithm will find it. If vBv\in B, then we will solve the problem in another way, which gives us some time improvement when =3\ell=3.

For each viv_i in BB, we consider vjBv_j\in B that has distance 22 from viv_i and j>ij>i. We consider the set of vertices Si,j=Ni(vi)Ni(vj)S_{i,j} = N_i(v_i)\cap N_i(v_j). If there are two sets Si,jS_{i,j} and Sa,bS_{a,b} has intersection size at least 22, then we claim there exists a K2,3K_{2,3} in GG. Now, this becomes finding a C4C_4 in the input sets. The total size of the input sets are O(α(G)m)O(\alpha(G)m). Hence we can use O((α(G)m)4/3)O((\alpha(G)m)^{4/3}) time to find a C4C_4. Hence this implies a O((α(G)m)4/3)O((\alpha(G)m)^{4/3}) time algorithm to find a K2,3K_{2,3}.

Using the idea for finding C4C_4, we can mix the ((α(G)m)4/3)((\alpha(G)m)^{4/3}) time algorithm and the O(n2)O(n^2) time algorithm. Working out the algebra shows the following theorem.

Theorem10

There is a O(m28/15)O(m^{28/15}) time algorithm for finding a colored K2,3K_{2,3}.

References

[1] N. Chiba, T. Nishizeki, Arboricity and Subgraph Listing Algorithms, SIAM Journal on Computing. 14 (1985) 210–223 10.1137/0214017.

[2] A. Rajan, Algorithmic applications of connectivity and related topics in matroid theory, PhD thesis, Northwestern University, 1987.

[3] N. Alon, R. Yuster, U. Zwick, Finding and counting given length cycles, Algorithmica. 17 (1997) 209–223 10.1007/BF02523189.

[4] Z. Füredi, New asymptotics for bipartite turán numbers, Journal of Combinatorial Theory, Series A. 75 (1996) 141–144 10.1006/jcta.1996.0067.

Posted by Chao Xu on .
Tags: algorithm, graph.