Misra, NeeldharaNeeldharaMisraPanolan, FahadFahadPanolanSaurabh, SaketSaketSaurabh2025-08-312025-08-312019-01-01[9783030199548]10.1007/978-3-030-19955-5_252-s2.0-85068597915https://d8.irins.org/handle/IITG2025/23429An edge Hamiltonian path of a graph is a permutation of its edge set where every pair of consecutive edges have a vertex in common. Unlike the seemingly related problem of finding an Eulerian walk, the edge Hamiltonian path is known to be a NP -hard problem, even on fairly restricted classes of graphs. We introduce a natural optimization variant of the notion of an edge Hamiltonian path, which seeks the longest sequence of distinct edges with the property that every consecutive pair of them has a vertex in common. We call such a sequence of edges an edge-linked path, and study the parameterized complexity of the problem of finding edge-linked paths with at least k edges. We show that the problem is FPT when parameterized by k, and unlikely to admit a polynomial kernel even on connected graphs. On the other hand, we show that the problem admits a Turing kernel of polynomial size. To the best of our knowledge, this is the first problem on general graphs to admit Turing kernels with adaptive oracles (for which a non-adaptive kernel is not known). We also design a single-exponential parameterized algorithm for the problem when parameterized by the treewidth of the input graph.falseEdge Hamiltonian cycle | FPT | Turing kernelizationConference Paper16113349286-29820192cpBook Series1