A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909605975556096 |
|---|---|
| author | Bourneuf, Romain Cocquet, Julien Tang, Chaoliang Thomassé, Stéphan |
| author_facet | Bourneuf, Romain Cocquet, Julien Tang, Chaoliang Thomassé, Stéphan |
| contents | As shown by Robertson and Seymour, deciding whether the complete graph $K_t$ is a minor of an input graph $G$ is a fixed parameter tractable problem when parameterized by $t$. From the approximation viewpoint, the gap to fill is quite large, as there is no PTAS for finding the largest complete minor unless $P = NP$, whereas a polytime $O(\sqrt n)$-approximation algorithm was given by Alon, Lingas and Wahlén.
We investigate the complexity of finding $K_t$ as interval minor in ordered graphs (i.e. graphs with a linear order on the vertices, in which intervals are contracted to form minors). Our main result is a polytime $f(t)$-approximation algorithm, where $f$ is triply exponential in $t$ but independent of $n$. The algorithm is based on delayed decompositions and shows that ordered graphs without a $K_t$ interval minor can be constructed via a bounded number of three operations: closure under substitutions, edge union, and concatenation of a stable set. As a byproduct, graphs avoiding $K_t$ as an interval minor have bounded chromatic number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05997 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Polynomial-Time Approximation Algorithm for Complete Interval Minors Bourneuf, Romain Cocquet, Julien Tang, Chaoliang Thomassé, Stéphan Data Structures and Algorithms Discrete Mathematics Combinatorics As shown by Robertson and Seymour, deciding whether the complete graph $K_t$ is a minor of an input graph $G$ is a fixed parameter tractable problem when parameterized by $t$. From the approximation viewpoint, the gap to fill is quite large, as there is no PTAS for finding the largest complete minor unless $P = NP$, whereas a polytime $O(\sqrt n)$-approximation algorithm was given by Alon, Lingas and Wahlén. We investigate the complexity of finding $K_t$ as interval minor in ordered graphs (i.e. graphs with a linear order on the vertices, in which intervals are contracted to form minors). Our main result is a polytime $f(t)$-approximation algorithm, where $f$ is triply exponential in $t$ but independent of $n$. The algorithm is based on delayed decompositions and shows that ordered graphs without a $K_t$ interval minor can be constructed via a bounded number of three operations: closure under substitutions, edge union, and concatenation of a stable set. As a byproduct, graphs avoiding $K_t$ as an interval minor have bounded chromatic number. |
| title | A Polynomial-Time Approximation Algorithm for Complete Interval Minors |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2505.05997 |