Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective

The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth’s theorem on posets and Kőnig’s theorem on matchings in bipartite graphs. The theorem asserts that for every graph G, the vertex set of G can be partitioned into at most α(G) vertex-disjoint paths, where α(G) is the maximum size of an independent set in G. The proof of the Gallai-Milgram theorem is constructive and yields a polynomial-time algorithm that computes a covering of G by at most α(G) vertex-disjoint paths. While the Gallai-Milgram theorem is tight—there are graphs where one really needs α(G) paths, not fewer, to cover the vertex set of G—it was not known prior to our work whether deciding if a graph G could be covered by fewer than α(G) vertex-disjoint paths can be done in polynomial time. We resolve this question by proving the following algorithmic extension of the Gallai–Milgram theorem for undirected graphs: There is an algorithm that, for an n-vertex graph G and an integer parameter k ≥ 1, runs in time 22O(k4logk) · nO(1) and outputs a path cover P of G together with either a correct conclusion that P is a minimum-size path cover or an independent set of size |P| + k, certifying that P contains at most α(G) − k paths. Thus, for k ∈ O((loglogn)1/4−ε) our algorithm runs in polynomial time, and either computes a minimum-size path cover of G, or finds a path cover of size at most α(G) − k. We find the existence of such an algorithm quite surprising for the following reason. The problems of computing a path cover and a maximum independent set are both notoriously hard, yet our algorithm either solves one of them or provides meaningful information about the other. The proof of our algorithmic extension of the Gallai–Milgram theorem is non-trivial and builds on several novel algorithmic ideas. One of the key subroutines in our algorithm is an FPT algorithm, parameterized by α(G), for deciding whether G contains a Hamiltonian path. This result is of independent interest—prior to our work, no polynomial-time algorithm for deciding Hamiltonicity was known, even for graphs with independence number at most three. Moreover, the algorithmic techniques we develop apply to a wide array of problems in undirected graphs, including Hamiltonian Cycle, Path Cover, Largest Linkage, and Topological Minor Containment. We show that all these problems are FPT when parameterized by the independence number of the graph. Notably, the independence-number parameterization departs from the typical direction of research in parameterized complexity. First, α(G) measures a graph’s density, whereas most prior work in the area focuses on parameters describing sparsity, such as treewidth or vertex cover. Second, most structural parameters studied in parameterized complexity can be computed exactly or well-approximated in polynomial or even FPT time, whereas computing α(G) is notoriously difficult from almost any computational perspective. The fact that it can nevertheless serve as the basis for efficient parameterization is particularly striking.