XNLP-Hardness of Parameterized Problems on Planar Graphs

Hans L. Bodlaender; Krisztina Szilágyi

doi:10.1007/978-3-031-75409-8_8

XNLP-Hardness of Parameterized Problems on Planar Graphs

Hans L. Bodlaender, Krisztina Szilágyi^*

^*Corresponding author for this work

Sub Algorithms and Complexity

Utrecht University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)n^O(1) time and g(k)logn space, where n is the size of the input instance and k the parameter. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. These two classes are a “natural home” for many standard graph problems and their generalizations. In this paper, we show the hardness of several problems on planar graphs, parameterized by outerplanarity, treewidth and pathwidth, thus strengthening several existing results. In particular, we show XNLP-hardness of the following problems parameterized by outerplanarity: All-or-Nothing Flow, Target Outdegree Orientation, Capacitated (Red-Blue) Dominating Set, Target Set Selection etc. We also show the XNLP-completeness of Scattered Set parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers
Editors	Daniel Kráľ, Martin Milanič
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	107-120
Number of pages	14
ISBN (Print)	9783031754081
DOIs	https://doi.org/10.1007/978-3-031-75409-8_8
Publication status	Published - 2025
Event	50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024 - Gozd Martuljek, Slovenia Duration: 19 Jun 2024 → 21 Jun 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14760 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024
Country/Territory	Slovenia
City	Gozd Martuljek
Period	19/06/24 → 21/06/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Keywords

Outerplanarity
Parameterized Complexity
Planar Graphs
XALP
XNLP

Access to Document

10.1007/978-3-031-75409-8_8

Cite this

Bodlaender, H. L., & Szilágyi, K. (2025). XNLP-Hardness of Parameterized Problems on Planar Graphs. In D. Kráľ, & M. Milanič (Eds.), Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers (pp. 107-120). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14760 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-75409-8_8

Bodlaender, Hans L. ; Szilágyi, Krisztina. / XNLP-Hardness of Parameterized Problems on Planar Graphs. Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. editor / Daniel Kráľ ; Martin Milanič. Springer Science and Business Media Deutschland GmbH, 2025. pp. 107-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{48ec1d2692564362b9c365134456bb7f,

title = "XNLP-Hardness of Parameterized Problems on Planar Graphs",

abstract = "The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)nO(1) time and g(k)logn space, where n is the size of the input instance and k the parameter. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. These two classes are a “natural home” for many standard graph problems and their generalizations. In this paper, we show the hardness of several problems on planar graphs, parameterized by outerplanarity, treewidth and pathwidth, thus strengthening several existing results. In particular, we show XNLP-hardness of the following problems parameterized by outerplanarity: All-or-Nothing Flow, Target Outdegree Orientation, Capacitated (Red-Blue) Dominating Set, Target Set Selection etc. We also show the XNLP-completeness of Scattered Set parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity.",

keywords = "Outerplanarity, Parameterized Complexity, Planar Graphs, XALP, XNLP",

author = "Bodlaender, {Hans L.} and Krisztina Szil{\'a}gyi",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024 ; Conference date: 19-06-2024 Through 21-06-2024",

year = "2025",

doi = "10.1007/978-3-031-75409-8_8",

language = "English",

isbn = "9783031754081",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "107--120",

editor = "Daniel Kr{\'a}{\v I} and Martin Milani{\v c}",

booktitle = "Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers",

address = "Germany",

}

Bodlaender, HL & Szilágyi, K 2025, XNLP-Hardness of Parameterized Problems on Planar Graphs. in D Kráľ & M Milanič (eds), Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14760 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 107-120, 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024, Gozd Martuljek, Slovenia, 19/06/24. https://doi.org/10.1007/978-3-031-75409-8_8

XNLP-Hardness of Parameterized Problems on Planar Graphs. / Bodlaender, Hans L.; Szilágyi, Krisztina.
Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. ed. / Daniel Kráľ; Martin Milanič. Springer Science and Business Media Deutschland GmbH, 2025. p. 107-120 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14760 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - XNLP-Hardness of Parameterized Problems on Planar Graphs

AU - Bodlaender, Hans L.

AU - Szilágyi, Krisztina

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025

Y1 - 2025

N2 - The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)nO(1) time and g(k)logn space, where n is the size of the input instance and k the parameter. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. These two classes are a “natural home” for many standard graph problems and their generalizations. In this paper, we show the hardness of several problems on planar graphs, parameterized by outerplanarity, treewidth and pathwidth, thus strengthening several existing results. In particular, we show XNLP-hardness of the following problems parameterized by outerplanarity: All-or-Nothing Flow, Target Outdegree Orientation, Capacitated (Red-Blue) Dominating Set, Target Set Selection etc. We also show the XNLP-completeness of Scattered Set parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity.

AB - The class XNLP consists of (parameterized) problems that can be solved nondeterministically in f(k)nO(1) time and g(k)logn space, where n is the size of the input instance and k the parameter. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. These two classes are a “natural home” for many standard graph problems and their generalizations. In this paper, we show the hardness of several problems on planar graphs, parameterized by outerplanarity, treewidth and pathwidth, thus strengthening several existing results. In particular, we show XNLP-hardness of the following problems parameterized by outerplanarity: All-or-Nothing Flow, Target Outdegree Orientation, Capacitated (Red-Blue) Dominating Set, Target Set Selection etc. We also show the XNLP-completeness of Scattered Set parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity.

KW - Outerplanarity

KW - Parameterized Complexity

KW - Planar Graphs

KW - XALP

KW - XNLP

UR - http://www.scopus.com/inward/record.url?scp=85218473369&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-75409-8_8

DO - 10.1007/978-3-031-75409-8_8

M3 - Conference contribution

AN - SCOPUS:85218473369

SN - 9783031754081

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 107

EP - 120

BT - Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers

A2 - Kráľ, Daniel

A2 - Milanič, Martin

PB - Springer Science and Business Media Deutschland GmbH

T2 - 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024

Y2 - 19 June 2024 through 21 June 2024

ER -

Bodlaender HL, Szilágyi K. XNLP-Hardness of Parameterized Problems on Planar Graphs. In Kráľ D, Milanič M, editors, Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2025. p. 107-120. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-75409-8_8