加拉伊和米尔格拉姆的经典定理（1960年）断言，对于任意图G，其顶点集可以划分为至多\(\alpha(G)\)个互不相交的路径，其中\(\alpha(G)\)是图G中最大独立集的大小。加拉伊-米尔格拉姆定理的证明是构造性的，并给出了一种在多项式时间内计算至多由\(\alpha(G)\)个互不相交路径覆盖图G的算法。我们证明了对于无向图的一个算法扩展：确定一个无向图能否被少于\(\alpha(G)-k\)个互不相交路径覆盖是固定参数可解的（FPT），参数化为k。更具体地说，我们提供了一个算法，对于n阶图G和整数参数\(k \geq 1\)，运行时间为\(2^{k^{O(k^4)}} \cdot n^{O(1)}\)，并输出图G的一个路径覆盖P。此外，它： - 要么正确报告P是最小规模的路径覆盖， - 要么与P一起输出一个大小为\(|P|+k\)的独立集，证明P包含至多\(\alpha(G)-k\)条路径。 我们的算法中的一个关键子程序是参数化为\(\alpha(G)\)的FPT算法，用于判断图G是否包含哈密顿路径。这一结果本身具有独立的兴趣——在我们的工作之前，即使对于独立数最多为3的图，也未有已知的多项式时间算法来决定哈密顿性。此外，我们开发的技术适用于无向图中的广泛问题，包括哈密顿回路、路径覆盖、最大链路和拓扑子图包含。我们表明这些问题在参数化为图的独立数时都是FPT。值得注意的是，独立数参数化描述了图的密度，这与参数化复杂性研究的典型方向不同，后者关注描述图稀疏性的参数，如树宽或顶点覆盖数。

The classic theorem of Gallai and Milgram (1960) asserts that for every graph G, the vertex set of G can be partitioned into at most \alpha(G) vertex-disjoint paths, where \alpha(G) is the maximum size of an independent set in G. The proof of Gallai--Milgram's theorem is constructive and yields a polynomial-time algorithm that computes a covering of G by at most \alpha(G) vertex-disjoint paths. We prove the following algorithmic extension of Gallai--Milgram's theorem for undirected graphs: determining whether an undirected graph can be covered by fewer than \alpha(G) - k vertex-disjoint paths is fixed-parameter tractable (FPT) when parameterized by k. More precisely, we provide an algorithm that, for an n-vertex graph G and an integer parameter k \ge 1, runs in time 2^{k^{O(k^4)}} \cdot n^{O(1)}, and outputs a path cover P of G. Furthermore, it: - either correctly reports that P is a minimum-size path cover, - or outputs, together with P, an independent set of size |P| + k certifying that P contains at most \alpha(G) - k paths. A key subroutine in our algorithm is an FPT algorithm, parameterized by \alpha(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 3. Moreover, the 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, which describes graph's density, departs from the typical flow of research in parameterized complexity, which focuses on parameters describing graph's sparsity, like treewidth or vertex cover.