DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.3

Cycles in Unions of Transitive Tournaments

Authors: Bogdan Alecu, Pedro Bureo Villafana, and Vadim Lozin

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

A tournament is an orientation of a complete graph. A bitournament is an orientation of a complete bipartite graph. Let G be an oriented graph which is the (not necessarily disjoint) union of a bounded number of transitive tournaments. When is it possible to remove the arc sets of a bounded number of transitive bitournaments from G in order to make G acyclic? In this paper, we begin investigating this question and its ties to lettericity of graphs and geometric griddability of permutations, two independently developed notions that highlight very similar structural features in their respective objects. We explore the problem through the lens of "minimal obstructions", i.e. minimal classes of directed graphs for which this is not possible, and identify an infinite collection of such classes.

Cite as

Bogdan Alecu, Pedro Bureo Villafana, and Vadim Lozin. Cycles in Unions of Transitive Tournaments. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alecu_et_al:LIPIcs.WG.2026.3,
  author =	{Alecu, Bogdan and Bureo Villafana, Pedro and Lozin, Vadim},
  title =	{{Cycles in Unions of Transitive Tournaments}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.3},
  URN =		{urn:nbn:de:0030-drops-261694},
  doi =		{10.4230/LIPIcs.WG.2026.3},
  annote =	{Keywords: Structural graph theory, directed graphs, permutation patterns, graph lettericity, minimum feedback arc set problem, well-quasi-orderability, transitive tournaments}
}

Document

DOI: 10.4230/LIPIcs.WG.2026.14

Graph Classes Closed Under Self-Intersection

Authors: Konrad K. Dabrowski, Vadim Lozin, Martin Milanič, Andrea Munaro, Daniël Paulusma, and Viktor Zamaraev

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

A graph class is monotone if it is closed under taking subgraphs. A monotone class defined by finitely many obstructions has bounded treewidth if and only if one of the obstructions is a tripod, i.e. a disjoint union of subdivided claws and paths. This dichotomy also characterizes exactly those monotone graph classes for which many NP-hard graph problems admit polynomial-time algorithms. These dichotomies do not extend to the universe of all hereditary classes. This leads to the question of whether we can extend known dichotomies for monotone classes to larger families of hereditary classes. We answer this question affirmatively by considering the family of hereditary graph classes closed under self-intersection. This family is known to be located strictly between the monotone and hereditary classes. We prove a new structural characterization of graphs in self-intersection-closed classes excluding a tripod. In contrast to monotone classes excluding a tripod, these classes do not necessarily have bounded treewidth; in fact, they do not even need to be sparse. We use our characterization to give a complete dichotomy for Maximum Independent Set, and its weighted variant, on self-intersection-closed classes defined by finitely many obstructions: these problems are in P if the class excludes a tripod and NP-hard otherwise. Our dichotomy generalizes several known results on Maximum Independent Set in the literature. We also apply our characterization to obtain a dichotomy for Maximum Induced Matching on self-intersection-closed classes of bipartite graphs defined by finitely many obstructions, and for Satisfiability and Counting Satisfiability on self-intersection-closed classes of (bipartite) incidence graphs defined by finitely many obstructions. Finally, we use our characterization to obtain a dichotomy for boundedness of clique-width for self-intersection-closed classes of bipartite graphs defined by finitely many obstructions.

Cite as

Konrad K. Dabrowski, Vadim Lozin, Martin Milanič, Andrea Munaro, Daniël Paulusma, and Viktor Zamaraev. Graph Classes Closed Under Self-Intersection. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dabrowski_et_al:LIPIcs.WG.2026.14,
  author =	{Dabrowski, Konrad K. and Lozin, Vadim and Milani\v{c}, Martin and Munaro, Andrea and Paulusma, Dani\"{e}l and Zamaraev, Viktor},
  title =	{{Graph Classes Closed Under Self-Intersection}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.14},
  URN =		{urn:nbn:de:0030-drops-261801},
  doi =		{10.4230/LIPIcs.WG.2026.14},
  annote =	{Keywords: graph classes, self-intersection closed, dichotomy, independent set, clique-width, treewidth}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.47

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs

Authors: Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

For a fixed set H of graphs, a graph G is H-subgraph-free if G does not contain any H ∈ H as a (not necessarily induced) subgraph. A recent framework gives a complete classification on H-subgraph-free graphs (for finite sets H) for problems that are solvable in polynomial time on graph classes of bounded treewidth, NP-complete on subcubic graphs, and whose NP-hardness is preserved under edge subdivision. While a lot of problems satisfy these conditions, there are also many problems that do not satisfy all three conditions and for which the complexity in H-subgraph-free graphs is unknown. We study problems for which only the first two conditions of the framework hold (they are solvable in polynomial time on classes of bounded treewidth and NP-complete on subcubic graphs, but NP-hardness is not preserved under edge subdivision). In particular, we make inroads into the classification of the complexity of four such problems: Hamilton Cycle, k-Induced Disjoint Paths, C₅-Colouring and Star 3-Colouring. Although we do not complete the classifications, we show that the boundary between polynomial time and NP-complete differs among our problems and also from problems that do satisfy all three conditions of the framework, in particular when we forbid certain subdivisions of the "H"-graph (the graph that looks like the letter "H"). Hence, we exhibit a rich complexity landscape among problems for H-subgraph-free graph classes.

Cite as

Vadim Lozin, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Mark Siggers, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lozin_et_al:LIPIcs.ISAAC.2024.47,
  author =	{Lozin, Vadim and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Siggers, Mark and Smith, Siani and van Leeuwen, Erik Jan},
  title =	{{Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{47:1--47:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.47},
  URN =		{urn:nbn:de:0030-drops-221747},
  doi =		{10.4230/LIPIcs.ISAAC.2024.47},
  annote =	{Keywords: forbidden subgraph, complexity dichotomy, edge subdivision, treewidth}
}

Search Results

Documents authored by Lozin, Vadim

Cycles in Unions of Transitive Tournaments

Abstract

Cite as

Graph Classes Closed Under Self-Intersection

Abstract

Cite as

Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message