Source-linked AI summary
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
Noga Alon, Shai Gutner
TL;DR
Finding a small dominating set is difficult on general graphs, motivating algorithms for restricted graph families. This paper develops algorithms for degenerated and excluded-minor graphs, alongside induced-cycle search. It establishes fixed-parameter tractability for dominating set on degenerated graphs and gives improved bounds for specific excluded-minor families.
Problem
Dominating set is W[2]-complete on general graphs, motivating the search for graph families where it is fixed-parameter tractable; linear-time algorithms were previously known only for planar graphs.
Source: §1 · p. 2Method
The paper develops dominating-set algorithms for degenerated and excluded-minor graph families and uses random separation with color-coding for induced-subgraph search.
Source: §1 · p. 3Results
Dominating set runs in k^O(dk)n, improving to (O(h))^hk n and (O(log h))^(hk/2)n for the stated excluded-minor families; excluded-minor induced cycles take O(n) expected and O(n log n) worst-case time.
Source: §1 · p. 3Takeaways & Limitations
The results establish linear-time fixed-parameter tractability for dominating set on degenerated graphs, a broader class than the planar graphs for which such algorithms were previously known.
Source: §1 · p. 2The reduced black-and-white graph setting requires W to be independent, each white vertex to have degree at least 2, and distinct neighborhoods.
Source: §2 · p. 5
Abstract
from arXiv · showhide
There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a $k^{O(dk)} n$ time algorithm for finding a dominating set of size at most $k$ in a $d$-degenerated graph with $n$ vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain $K_h$ as a topological minor, we give an improved algorithm for the problem with running time $(O(h))^{hk} n$. For graphs which are $K_h$-minor-free, the running time is further reduced to $(O(\log h))^{hk/2} n$. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed $H$ and $k$, we show that if an $H$-minor-free graph $G$ with $n$ vertices contains an induced cycle of size $k$, then such a cycle can be found in O(n) expected time as well as in $O(n \log n)$ worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs.
1 Introduction
The paper establishes fixed-parameter algorithms for dominating set on degenerated graphs, with improved bounds for excluded-minor classes. It also gives algorithms for induced cycles and examines the limits of linear-time cycle finding in degenerated graphs.
Motivation
- The general-graph dominating-set problem is W[2]-complete, motivating the search for graph families where it is fixed-parameter tractable.The paper also addresses open questions from Cai, Chan and Chan about induced-cycle algorithms in degenerated graphs.Source: §1 · pp. 2–3
Prior work
- Linear-time fixed-parameter algorithms for dominating set had previously been established only for planar graphs, while fixed-parameter tractability was known for map graphs and fixed powers of H-minor-free graphs.The paper presents degenerated graphs as the most general class for which fixed-parameter tractability for this problem had been established.Source: §1 · p. 2
Induced paths and cycles
- O(n) expected time and O(n log n) worst-case time find an induced k-cycle in an H-minor-free graph for fixed H and k.The derandomization improves on the earlier log^2 n loss described for induced cycles in degenerated graphs.Source: §1 · p. 3
Dominating set
- k^{O(dk)}n time suffices for dominating set in d-degenerated graphs, improving to (O(h))^{hk}n for graphs without a K_h topological minor and (O(log h))^{hk/2}n for K_h-minor-free graphs.All three algorithms extend to finding a minimum-weight dominating set of size at most k within the same time bounds.Source: §1 · p. 3
Induced paths and cycles
- Deterministic O(n) time finds induced cycles of size at most 5 in degenerated graphs, while linear time for longer cycles is described as unlikely.The paper also presents an expected-linear algorithm and deterministic O(n log n) derandomization for induced cycles in graphs with an excluded minor.Source: §1 · p. 3
Techniques
- The dominating-set algorithms generalize bounded-search-tree methods using combinatorial lemmas about vertices that dominate many set elements or have small degree.The induced-cycle algorithm for non-trivial minor-closed families combines random separation with color-coding and derandomizes via explicit families of generalized perfect hash functions.Source: §1 · p. 4
2 Preliminaries
The preliminaries define graph and neighborhood notation, degeneracy, and the paper’s black-and-white formulation of dominating set. They also specify the conditions for a black-and-white graph to be reduced.
Notation
- N(v) denotes the neighbors of v, and v dominates those neighbors together with itself; G−v deletes v, while G[V′] is induced by V′.For directed graphs, N⁺(V′) denotes the vertices that are out-neighbors of at least one vertex in V′.Source: §2 · p. 4
Degeneracy
- A graph is d-degenerated if every induced subgraph has a vertex of degree at most d; such graphs admit an acyclic orientation with maximum outdegree at most d.The orientation can be found in O(|E|) time, and a d-degenerated graph has fewer than dn edges.Source: §2 · p. 4
Dominating set
- For a black-and-white graph, the task is to choose at most k vertices that dominate every black vertex not chosen.The vertex set is partitioned into black and white vertices; the definition permits selecting vertices from either set.Source: §2 · pp. 4–5
Reduced graphs
- A reduced black-and-white graph has an independent white set whose vertices each have degree at least 2 and pairwise distinct neighborhoods.These are the stated conditions defining reduced graphs.Source: §2 · p. 5
3 Algorithms for the Dominating Set Problem
The algorithms use structural bounds on which vertices can dominate many black vertices to obtain fixed-parameter running times for degenerated graphs and sharper bounds for excluded-minor families. The approach also extends to weighted dominating set without changing the stated time bounds.
3.1 Degenerated Graphs
- At most (4d + 2)k vertices can dominate at least |B|/k black vertices when |B| > (4d + 2)k.This combinatorial lemma supplies the branching bound for the degenerated-graph algorithm.Source: §3.1 · p. 5
- k^O(dk)n time suffices to find a dominating set of size at most k in a d-degenerated black-and-white graph.The search uses a bound on vertices dominating at least |B|/k black vertices, which limits its branching before the algorithm checks partitions of B.Source: §3.1 · p. 5
3.2 Graphs with an Excluded Minor
- In the topological-minor-free case, a reduced graph has a black vertex of degree at most (ch)^h for a constant c > 0.For K_h-minor-free graphs, the corresponding degree bound is (c log h)^h/2.Source: §3.2 · p. 7
- (O(h))^hk n time suffices for dominating set of size at most k when the graph excludes K_h as a topological minor.The algorithm obtains its bound using a low-degree black vertex in a reduced graph.Source: §3.2 · p. 7
- (O(log h))^hk/2 n time suffices for dominating set of size at most k in a K_h-minor-free graph.The bound follows from a degree bound for a black vertex in a reduced graph.Source: §3.2 · pp. 7–8
3.3 The Weighted Case
- The weighted algorithms retain the same time bounds, but must scan the whole search tree rather than stop at the first valid solution.They select minimum-weight dominators for pieces and discard the heavier of equal-neighborhood white vertices.Source: §3.3 · p. 8
4 Finding Induced Cycles
The paper gives deterministic linear-time algorithms for induced cycles of length at most five in d-degenerated graphs, and expected-linear and deterministic O(n log n) algorithms for fixed-length induced cycles in minor-closed graph families. Its method for the latter combines random separation and color-coding.
4.1 Degenerated Graphs
- For fixed d ≥ 1 and k ≤ 5, induced cycles of length k in a d-degenerated graph can be found deterministically in O(n) time.The algorithm first orients edges so every vertex has outdegree at most d, then uses cycle-specific checks.Source: §4.1 · p. 9
- A linear-time algorithm for induced C6 in 2-degenerated graphs would yield a general-graph triangle algorithm in O(|V| + |E|) time.Subdividing every edge produces a 2-degenerated graph whose induced C6s correspond to triangles in the original graph.Source: §4.1 · pp. 9–10
4.2 Minor-Closed Families of Graphs
- For every fixed k, an induced k-cycle in a graph from a non-trivial minor-closed family can be found in O(n) expected time or O(n log n) deterministic time.The randomized method uses random separation followed by color-coding; derandomization uses a family of perfect hash functions.Source: §4.2 · p. 10
- Random separation retains a target induced cycle while removing its out-neighbors with probability at least 2^-k(d+1).Color-coding then preserves it as a multicolored cycle with probability at least 2k^1-k, which can be found in O(n) time.Source: §4.2 · p. 10
5 Concluding Remarks
The paper’s excluded-minor dominating-set algorithm generalizes and improves algorithms for planar and bounded-genus graphs. The conclusion also highlights a possible broader use for its techniques and leaves open whether stronger running times are possible.
5 Concluding Remarks
- The excluded-minor dominating-set algorithm generalizes and improves known algorithms for planar and bounded-genus graphs.Source: §5 · p. 11
- Similar techniques may help improve and simplify other known fixed-parameter algorithms for graphs with an excluded minor.Source: §5 · p. 11
- Whether excluded-minor graphs admit a 2^O(√k)n^c-time algorithm with absolute c, or even a 2^O(√k)n-time algorithm, remains open.Source: §5 · p. 11