A Survey on Graph Problems Parameterized Above and Below Guaranteed Values
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910375259144192 |
|---|---|
| author | Gutin, Gregory Mnich, Matthias |
| author_facet | Gutin, Gregory Mnich, Matthias |
| contents | We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values, a research area which was pioneered by Venkatesh Raman. Those problems seek, for a given graph $G$, a solution whose value is at least $g(G)+k$ or at most $g(G)-k$, where $g(G)$ is a guarantee on the value that any solution on $G$ takes. The goal is to design algorithms which find such solution in time whose complexity in $k$ is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_12278 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Survey on Graph Problems Parameterized Above and Below Guaranteed Values Gutin, Gregory Mnich, Matthias Data Structures and Algorithms We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values, a research area which was pioneered by Venkatesh Raman. Those problems seek, for a given graph $G$, a solution whose value is at least $g(G)+k$ or at most $g(G)-k$, where $g(G)$ is a guarantee on the value that any solution on $G$ takes. The goal is to design algorithms which find such solution in time whose complexity in $k$ is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results. We discuss a large number of algorithms and intractability results, and complement them by several open problems. |
| title | A Survey on Graph Problems Parameterized Above and Below Guaranteed Values |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2207.12278 |