Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
This paper presents a fixed-parameter tractable algorithm that resolves the open question of whether a graph can be covered by fewer than vertex-disjoint paths by outputting either a minimum path cover or an independent set certifying the cover's near-optimality, while also providing the first polynomial-time Hamiltonian path decision for graphs with independence number at most three.