Contracting to a Longest Path in H-Free Graphs

Walter Kern; Daniel Paulusma

doi:10.48550/arXiv.1810.01542

Contracting to a Longest Path in H-Free Graphs

Walter Kern
, Daniel Paulusma

Discrete Mathematics and Mathematical Programming

Research output: Working paper › Preprint › Academic

19 Downloads (Pure)

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 $H$-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.

Original language	English
Publisher	ArXiv.org
Number of pages	39
DOIs	https://doi.org/10.48550/arXiv.1810.01542
Publication status	Published - 2 Oct 2018

Keywords

cs.DS
cs.CC
cs.DM
math.CO

Access to Document

10.48550/arXiv.1810.01542

Article-v1Final published version, 674 KB

1 Conference contribution

Contracting to a longest path in H-free graphs
Kern, W. & Paulusma, D., Dec 2020, 31st International Symposium on Algorithms and Computation: ISAAC 2020, December 14–18, 2020, Hong Kong, China (Virtual Conference). Cao, Y., Cheng, S.-W. & Li, M. (eds.). Dagstuhl, p. 221-2218 1998 p. 22. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 181).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Open Access
File
6 Link opens in a new tab Citations (Scopus)

55 Downloads (Pure)

Cite this

@techreport{022c60f618a14a6390cfe9202a815312,

title = "Contracting to a Longest Path in H-Free Graphs",

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 \$H\$-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. ",

keywords = "cs.DS, cs.CC, cs.DM, math.CO",

author = "Walter Kern and Daniel Paulusma",

year = "2018",

month = oct,

day = "2",

doi = "10.48550/arXiv.1810.01542",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Contracting to a Longest Path in H-Free Graphs

AU - Kern, Walter

AU - Paulusma, Daniel

PY - 2018/10/2

Y1 - 2018/10/2

N2 - 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 $H$-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.

AB - 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 $H$-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.

KW - cs.DS

KW - cs.CC

KW - cs.DM

KW - math.CO

U2 - 10.48550/arXiv.1810.01542

DO - 10.48550/arXiv.1810.01542

M3 - Preprint

BT - Contracting to a Longest Path in H-Free Graphs

PB - ArXiv.org

ER -

Contracting to a Longest Path in H-Free Graphs

Abstract

Keywords

Access to Document

Fingerprint

Research output

Contracting to a longest path in H-free graphs

Cite this