Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2

Golovach, P.A.; Heggernes, P.; Kratch, D.; Lima, P.T.; Paulusma, D.

Abstract

Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class H. There are both polynomial-time solvable and NP-complete results in this direction, depending on H. We present a general framework for the problem if H is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where H is the class of outerplanar graphs and H is the class of graphs of pathwidth at most 2.

Citation

Golovach, P., Heggernes, P., Kratch, D., Lima, P., & Paulusma, D. (2019). Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Algorithmica, 81(7), 2795-2828. https://doi.org/10.1007/s00453-019-00555-y

• Journal Article Type: Article
• Acceptance Date: Feb 22, 2019
• Online Publication Date: Mar 2, 2019
• Publication Date: Apr 30, 2019
• Deposit Date: Feb 22, 2019
• Publicly Available Date: Mar 2, 2020
• Journal: Algorithmica
• Print ISSN: 0178-4617
• Electronic ISSN: 1432-0541
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 81
• Issue: 7
• Pages: 2795-2828
• DOI: https://doi.org/10.1007/s00453-019-00555-y
• Public URL: https://durham-repository.worktribe.com/output/1307495