An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916928686129152 |
|---|---|
| author | Feller, Roman Pinsker, Michael |
| author_facet | Feller, Roman Pinsker, Michael |
| contents | For a set F of finite tournaments, the F-free orientation problem is the problem of deciding if a given finite undirected graph can be oriented in such a way that the resulting oriented graph does not contain any member of F. Using the theory of smooth approximations, we give a new shorter proof of the complexity dichotomy for such problems obtained recently by Bodirsky and Guzmán-Pro. In fact, our approach yields a complexity dichotomy for a considerably larger class of computational problems where one is given an undirected graph along with additional local constraints on the allowed orientations. Moreover, the border between tractable and hard problems is also described by a decidable algebraic condition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20263 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments Feller, Roman Pinsker, Michael Combinatorics Computational Complexity Logic in Computer Science Rings and Algebras For a set F of finite tournaments, the F-free orientation problem is the problem of deciding if a given finite undirected graph can be oriented in such a way that the resulting oriented graph does not contain any member of F. Using the theory of smooth approximations, we give a new shorter proof of the complexity dichotomy for such problems obtained recently by Bodirsky and Guzmán-Pro. In fact, our approach yields a complexity dichotomy for a considerably larger class of computational problems where one is given an undirected graph along with additional local constraints on the allowed orientations. Moreover, the border between tractable and hard problems is also described by a decidable algebraic condition. |
| title | An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments |
| topic | Combinatorics Computational Complexity Logic in Computer Science Rings and Algebras |
| url | https://arxiv.org/abs/2405.20263 |