We study the parameterized complexity of various path (and cycle) problems, the parameter being the length of the path. For example, we show that the problem of the existence of a maximal path of length k in a graph G is fixed-parameter tractable, while its counting version is #W[1]- complete. The corresponding problems for chordless (or induced) paths are W[2]-complete and #W[2]-complete respectively. With the tools developed in this paper we derive the NP-completeness of a related classical problem, thereby solving a problem due to Hedetniemi.
['Yijia Chen', 'Jörg Flum']
On Parameterized Path and Chordless Path Problems