Contracting to a longest path in H-free graphs
From MaRDI portal
Publication:6065420
DOI10.4230/LIPICS.ISAAC.2020.22arXiv1810.01542OpenAlexW3113647070MaRDI QIDQ6065420
Author name not available (Why is that?)
Publication date: 14 November 2023
Abstract: We prove two dichotomy results for detecting long paths as patterns in a given graph. The NP-hard problem Longest Induced Path is to determine the longest induced path in a graph. The NP-hard problem Longest Path Contractibility is to determine the longest path to which a graph can be contracted to. By combining known results with new results we completely classify the computational complexity of both problems for -free graphs. Our main focus is on the second problem, for which we design a general contractibility technique that enables us to reduce the problem to a matching problem.
Full work available at URL: https://arxiv.org/abs/1810.01542
No records found.
No records found.
This page was built for publication: Contracting to a longest path in H-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065420)
