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.
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 .
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 .
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 .
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.
There is a dominating set incident to edges.
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 . Now, let the sets for each . Since degree is bounded by at most , we can obtain a dominating set of size . We set . Since the degree of each vertex is at least , then there is a covering of . Add the vertices induces this set cover to . is a dominating set, and its size 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 Finding small subgraphs
2.1 Finding a triangle
A triangle is vertices pairwise adjacent to each other, another name for .
There is a time algorithm to decide if the graph has a triangle, where is the maximum degree.
Indeed, for each vertex , we consider its neighbors, see if any is adjacent to each other. We then delete . The algorithm takes time.
There is a time algorithm to decide if the graph has a triangle.
The naive algorithm, for each vertices, we decide if it forms a triangle.
There is a time algorithm to decide if the graph has a triangle.
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.
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 . 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 . 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.
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 .
There exists a constant , such that each vertex graph with edges contains a .
There is a time algorithm to find a in the graph.
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.
There is a time algorithm for finding a colored .
 N. Chiba, T. Nishizeki, Arboricity and Subgraph Listing Algorithms, SIAM Journal on Computing. 14 (1985) 210–223 10.1137/0214017.
 A. Rajan, Algorithmic applications of connectivity and related topics in matroid theory, PhD thesis, Northwestern University, 1987.
 N. Alon, R. Yuster, U. Zwick, Finding and counting given length cycles, Algorithmica. 17 (1997) 209–223 10.1007/BF02523189.
 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.