2 Search Results for "Volec, Jan"

Document

DOI: 10.4230/LIPIcs.MFCS.2025.26

Computational Complexity of Covering Regular Trees

Authors: Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

A graph covering projection, also referred to as a locally bijective homomorphism, is a mapping between the vertices and edges of two graphs that preserves incidences and is a local bijection. This concept originates in topological graph theory but has also found applications in combinatorics and theoretical computer science. In this paper we consider undirected graphs in the most general setting - graphs may contain multiple edges, loops, and semi-edges. This is in line with recent trends in topological graph theory and mathematical physics. We advance the study of the computational complexity of the H-Cover problem, which asks whether an input graph allows a covering projection onto a parameter graph H. The quest for a complete characterization started in 1990’s. Several results for simple graphs or graphs without semi-edges have been known, the role of semi-edges in the complexity setting has started to be investigated only recently. One of the most general known NP-hardness results states that H-Cover is NP-complete for every simple connected regular graph of valency greater than two. We complement this result by considering regular graphs H arising from connected acyclic graphs by adding semi-edges. Namely, we prove that any graph obtained by adding semi-edges to the vertices of a tree making it a d-regular graph with d ≥ 3, defines an NP-complete graph covering problem. In line with the so called Strong Dichotomy Conjecture, we prove that the NP-hardness holds even for simple graphs on input.

Cite as

Jan Bok, Jiří Fiala, Nikola Jedličková, and Jan Kratochvíl. Computational Complexity of Covering Regular Trees. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2025.26,
  author =	{Bok, Jan and Fiala, Ji\v{r}{\'\i} and Jedli\v{c}kov\'{a}, Nikola and Kratochv{\'\i}l, Jan},
  title =	{{Computational Complexity of Covering Regular Trees}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.26},
  URN =		{urn:nbn:de:0030-drops-241338},
  doi =		{10.4230/LIPIcs.MFCS.2025.26},
  annote =	{Keywords: graph cover, covering projection, semi-edges, multigraphs, complexity, constrained homomorphisms, trees}
}

Document

DOI: 10.4230/LIPIcs.SOCG.2015.300

Limits of Order Types

Authors: Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, and Jan Volec

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag algebras, which were used to open various questions on graphs to mechanical solving via semidefinite programming. We define flag algebras of order types, and use them to obtain, via the semidefinite method, new lower bounds on the density of 5- or 6-tuples in convex position in arbitrary point sets, as well as some inequalities expressing the difficulty of sampling order types uniformly. We next consider graphons, a representation of limits of dense graphs that enable their study by continuous probabilistic or analytic methods. We investigate how planar measures fare as a candidate analogue of graphons for limits of order types. We show that the map sending a measure to its associated limit is continuous and, if restricted to uniform measures on compact convex sets, a homeomorphism. We prove, however, that this map is not surjective. Finally, we examine a limit of order types similar to classical constructions in combinatorial geometry (Erdos-Szekeres, Horton...) and show that it cannot be represented by any somewhere regular measure; we analyze this example via an analogue of Sylvester's problem on the probability that k random points are in convex position.

Cite as

Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos, Jean-Sébastien Sereni, and Jan Volec. Limits of Order Types. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 300-314, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{goaoc_et_al:LIPIcs.SOCG.2015.300,
  author =	{Goaoc, Xavier and Hubard, Alfredo and de Joannis de Verclos, R\'{e}mi and Sereni, Jean-S\'{e}bastien and Volec, Jan},
  title =	{{Limits of Order Types}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{300--314},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.300},
  URN =		{urn:nbn:de:0030-drops-51264},
  doi =		{10.4230/LIPIcs.SOCG.2015.300},
  annote =	{Keywords: order types, Limits of discrete structures, Flag algebras, Erdos-Szekeres, Sylvester’s problem}
}

Refine by Type
2 Document/PDF
1 Document/HTML

Refine by Publication Year
1 2025
1 2015

Refine by Author
1 Bok, Jan
1 Fiala, Jiří
1 Goaoc, Xavier
1 Hubard, Alfredo
1 Jedličková, Nikola
Show More...

Refine by Series/Journal
2 LIPIcs

Refine by Classification
1 Mathematics of computing → Graph theory

Refine by Keyword
1 Erdos-Szekeres
1 Flag algebras
1 Limits of discrete structures
1 Sylvester’s problem
1 complexity
Show More...

2 Search Results for "Volec, Jan"

Computational Complexity of Covering Regular Trees

Abstract

Cite as

Limits of Order Types

Abstract

Cite as

Thanks for your feedback!

Could not send message