Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2206.11828 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914645447540736 |
|---|---|
| author | Bodlaender, Hans L. Groenland, Carla Jacob, Hugo Pilipczuk, Marcin Pilipczuk, Michał |
| author_facet | Bodlaender, Hans L. Groenland, Carla Jacob, Hugo Pilipczuk, Marcin Pilipczuk, Michał |
| contents | In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in $f(k)n^{O(1)}$ time and $f(k)\log n$ space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on `tree-structured graphs' are complete for this class: we show that List Colouring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by $\log n$, and Max Cut parameterized by cliquewidth are also XALP-complete.
Besides finding a `natural home' for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most $f(k)n^{O(1)}$ and use $f(k)\log n$ space. Moreover, we introduce `tree-shaped' variants of Weighted CNF-Satisfiability and Multicolour Clique that are XALP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_11828 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Problems on Tree-structured Graphs Bodlaender, Hans L. Groenland, Carla Jacob, Hugo Pilipczuk, Marcin Pilipczuk, Michał Computational Complexity In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in $f(k)n^{O(1)}$ time and $f(k)\log n$ space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on `tree-structured graphs' are complete for this class: we show that List Colouring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by $\log n$, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a `natural home' for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most $f(k)n^{O(1)}$ and use $f(k)\log n$ space. Moreover, we introduce `tree-shaped' variants of Weighted CNF-Satisfiability and Multicolour Clique that are XALP-complete. |
| title | On the Complexity of Problems on Tree-structured Graphs |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2206.11828 |