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 with arboricity , we have

Often, using the arboricity, we can obtain the same complexity algorithm without high-degree low-degree technique. Note the arboricity is . 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 are set contains a total of elements. is the universe, with size .

Theorem2

There is a probability distribution over , such that for each , the probability a random set covers is at least . There exists a set cover of .

Proof

There exists a set that covers at least for any . Therefore each greedy iteration decrease the size of uncovered universe by an fraction. So there can be at most iterations, where . One can show suffices.

Theorem3

There is a dominating set incident to edges.

Proof

Fix a . We repeatedly removing vertices with degree no more than from the graph, and add it into a set . The total degree of is at most . Now the remaining vertices has degree at least . Using the set cover theorem, and let the distribution to be the uniform distribution. If all elements are covered at least by fraction of the set, then we obtain a set cover of size . Indeed, just let the sets for each , and we pick them uniformly. We set . Since the degree of each vertex is at least , then there is a dominating set of size , and incident to edges. Add the dominating set to . is a dominating set, and the number of edges incident to it is , set and we obtain the desired result.

One can show the above result is almost optimal, as there exists graphs where every dominating set incidents edges. The same bound holds for weakly connected dominating set, that is a dominating set such that the edges incident to forms a connected graph. The stronger modification of this result was used in deciding the -connectivity of a matroid [2].

2 Finding small subgraphs

2.1 Finding a triangle

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

Theorem4

There is a time algorithm to decide if the graph has a triangle, where is the maximum degree.

Proof

Indeed, for each vertex , we consider its neighbors, see if any is adjacent to each other. We then delete . The algorithm takes time.

Theorem5

There is a time algorithm to decide if the graph has a triangle.

Proof

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

Theorem6

There is a time algorithm to decide if the graph has a triangle.

Proof

Let 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 . It will use at most time. Now, for the remaining graph, it is clear the maximum degree is at least . Note, there can be at most vertices. We use the time algorithm. The final running time is . Set and we are done.

ProofAlternative

We modify the algorithm a little. For each vertex , we consider its neighbor , and check if has a neighbor that is in . Then we delete , and move on to next vertex. The running time become . Now, assume we pick vertices by the largest to smallest in term of degrees. We rearrange the sum and obtain . Because , we have the running time .

2.2 A motivating problem

Let be sets with total of elements. How quickly can we find two distinct and such that ? This problem can be shown to be equivalent to finding a colored in a bipartite graph. That is, for input bipartite graph . Find a where the side of two vertices has to be in .

2.3 Finding a in bipartite graphs

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

Let be an ordering such that . There exists an algorithm that finds an ordering of vertices , and returns for each and . Here is the set of neighbors of in . Here we show an algorithm solves the above problem when the arboricity is small.

The algorithm is as follows [1]. Take , we consider each neighbor . Maintain a set for each vertex distance from . Add into each of ’s neighbor in . would give us information of . We delete and keep going. It is known the algorithm takes time. This allows us to compute in the same time. Hence we directly obtain running time. However, we show something better is possible if we are not interested in finding all , but find any . We also need the following theorem.

Theorem7

One can check if there exists a in the bipartite graph in time.

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

Theorem8-free theorem

There exists a constant , such that each vertex graph with edges contains a .

Theorem9

There is a time algorithm to find a in the graph.

Proof

If the arboricity is . We use the first algorithm and we get running time . Otherwise, we know there is a subgraph with minimum degree at least . The subgraph can be found by repeatedly deleting vertices of minimum degree. The subgraph with the previous property has vertices and edges. One can see . If , then we know there exists a in by the previous theorem, and we can apply the time algorithm in the subgraph to find the . The total running time is therefore . We set . One can check after lot of algebra, it make sure the condition is satisfied. The algorithm takes time.

2.4 Finding a colored in bipartite graphs

For finding , the low arboricity algorithm for works here. The algorithm is still fine. It’s not hard to generalize and show a running time algorithm.

However, in order to solve the motivating problem. We need a colored .

Let’s consider a in , and consider the first indexed vertex . If , then we are done, as the algorithm will find it. If , then we will solve the problem in another way, which gives us some time improvement when .

For each in , we consider that has distance from and . We consider the set of vertices . If there are two sets and has intersection size at least , then we claim there exists a in . Now, this becomes finding a in the input sets. The total size of the input sets are . Hence we can use time to find a . Hence this implies a time algorithm to find a .

Using the idea for finding , we can mix the time algorithm and the time algorithm. Working out the algebra shows the following theorem.

Theorem10

There is a time algorithm for finding a colored .

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.