DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.28

Generalized Completion Problems with Forbidden Tournaments

Authors: Zeno Bitter and Antoine Mottet

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

A recent result by Bodirsky and Guzmán-Pro gives a complexity dichotomy for the following class of computational problems, parametrized by a finite family F of finite tournaments: given an undirected graph, does there exist an orientation of the graph that avoids every tournament in F? One can see the edges of the input graphs as constraints imposing to find an orientation. In this paper, we consider a more general version of this problem where the constraints in the input are not necessarily about pairs of variables and impose local constraints on the global oriented graph to be found. Our main result is a complexity dichotomy for such problems, as well as a classification of such problems where the yes-instances have bounded treewidth duality. As a consequence, we obtain a streamlined proof of the result by Bodirsky and Guzmán-Pro using the theory of smooth approximations due to Mottet and Pinsker.

Cite as

Zeno Bitter and Antoine Mottet. Generalized Completion Problems with Forbidden Tournaments. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bitter_et_al:LIPIcs.MFCS.2024.28,
  author =	{Bitter, Zeno and Mottet, Antoine},
  title =	{{Generalized Completion Problems with Forbidden Tournaments}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.28},
  URN =		{urn:nbn:de:0030-drops-205844},
  doi =		{10.4230/LIPIcs.MFCS.2024.28},
  annote =	{Keywords: Tournaments, completion problems, constraint satisfaction problems, homogeneous structures, polymorphisms}
}

Search Results

Documents authored by Bitter, Zeno

Generalized Completion Problems with Forbidden Tournaments

Abstract

Cite as

Thanks for your feedback!

Could not send message