XALP-completeness of Parameterized Problems on Planar Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912179393921024 |
|---|---|
| author | Bodlaender, Hans L. Szilágyi, Krisztina |
| author_facet | Bodlaender, Hans L. Szilágyi, Krisztina |
| contents | The class XNLP consists of (parameterized) problems that can be solved nondeterministically in $f(k)n^{O(1)}$ time and $f(k)\log n$ 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 the XALP-completeness of the following problems parameterized by outerplanarity: All-or-Nothing Flow, Target Outdegree Orientation, Capacitated (Red-Blue) Dominating Set, Target Set Selections etc. We also show the XNLP-completeness of Scattered Set parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_03087 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | XALP-completeness of Parameterized Problems on Planar Graphs Bodlaender, Hans L. Szilágyi, Krisztina Computational Complexity 05C10, 68Q15 G.2.2 The class XNLP consists of (parameterized) problems that can be solved nondeterministically in $f(k)n^{O(1)}$ time and $f(k)\log n$ 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 the XALP-completeness of the following problems parameterized by outerplanarity: All-or-Nothing Flow, Target Outdegree Orientation, Capacitated (Red-Blue) Dominating Set, Target Set Selections etc. We also show the XNLP-completeness of Scattered Set parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity. |
| title | XALP-completeness of Parameterized Problems on Planar Graphs |
| topic | Computational Complexity 05C10, 68Q15 G.2.2 |
| url | https://arxiv.org/abs/2402.03087 |