Search Results

Documents authored by Fiala, Jiří

Found 2 Possible Name Variants:

Fiala, Jiri

Document
DOI: 10.4230/LIPIcs.MFCS.2021.21
Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases

Authors: Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for graphs with semi-edges. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a notion well known and deeply studied in classical topology. Graph covers have found applications in discrete mathematics for constructing highly symmetric graphs, and in computer science in the theory of local computations. In 1991, Abello et al. asked for a classification of the computational complexity of deciding if an input graph covers a fixed target graph, in the ordinary setting (of graphs with only edges). Although many general results are known, the full classification is still open. In spite of that, we propose to study the more general case of covering graphs composed of normal edges (including multiedges and loops) and so-called semi-edges. Semi-edges are becoming increasingly popular in modern topological graph theory, as well as in mathematical physics. They also naturally occur in the local computation setting, since they are lifted to matchings in the covering graph. We show that the presence of semi-edges makes the covering problem considerably harder; e.g., it is no longer sufficient to specify the vertex mapping induced by the covering, but one necessarily has to deal with the edge mapping as well. We show some solvable cases and, in particular, completely characterize the complexity of the already very nontrivial problem of covering one- and two-vertex (multi)graphs with semi-edges. Our NP-hardness results are proven for simple input graphs, and in the case of regular two-vertex target graphs, even for bipartite ones. We remark that our new characterization results also strengthen previously known results for covering graphs without semi-edges, and they in turn apply to an infinite class of simple target graphs with at most two vertices of degree more than two. Some of the results are moreover proven in a more general setting (e.g., finding k-tuples of pairwise disjoint perfect matchings in regular graphs, or finding equitable partitions of regular bipartite graphs).
Cite as

Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl. Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2021.21,
  author =	{Bok, Jan and Fiala, Ji\v{r}{\'\i} and Hlin\v{e}n\'{y}, Petr and Jedli\v{c}kov\'{a}, Nikola and Kratochv{\'\i}l, Jan},
  title =	{{Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.21},
  URN =		{urn:nbn:de:0030-drops-144611},
  doi =		{10.4230/LIPIcs.MFCS.2021.21},
  annote =	{Keywords: graph cover, covering projection, semi-edges, multigraphs, complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2469
The k-in-a-path Problem for Claw-free Graphs

Authors: Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Testing whether there is an induced path in a graph spanning $k$ given vertices is already \NP-complete in general graphs when $k=3$. We show how to solve this problem in polynomial time on claw-free graphs, when $k$ is not part of the input but an arbitrarily fixed integer.
Cite as

Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma. The k-in-a-path Problem for Claw-free Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 371-382, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fiala_et_al:LIPIcs.STACS.2010.2469,
  author =	{Fiala, Jiri and Kaminski, Marcin and Lidick\'{y}, Bernard and Paulusma, Dani\"{e}l},
  title =	{{The k-in-a-path Problem for Claw-free Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{371--382},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2469},
  URN =		{urn:nbn:de:0030-drops-24692},
  doi =		{10.4230/LIPIcs.STACS.2010.2469},
  annote =	{Keywords: Induced path, claw-free graph, polynomial-time algorithm}
}

Fiala, Jiří

Document
DOI: 10.4230/LIPIcs.MFCS.2021.21
Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases

Authors: Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for graphs with semi-edges. The notion of graph covering is a discretization of coverings between surfaces or topological spaces, a notion well known and deeply studied in classical topology. Graph covers have found applications in discrete mathematics for constructing highly symmetric graphs, and in computer science in the theory of local computations. In 1991, Abello et al. asked for a classification of the computational complexity of deciding if an input graph covers a fixed target graph, in the ordinary setting (of graphs with only edges). Although many general results are known, the full classification is still open. In spite of that, we propose to study the more general case of covering graphs composed of normal edges (including multiedges and loops) and so-called semi-edges. Semi-edges are becoming increasingly popular in modern topological graph theory, as well as in mathematical physics. They also naturally occur in the local computation setting, since they are lifted to matchings in the covering graph. We show that the presence of semi-edges makes the covering problem considerably harder; e.g., it is no longer sufficient to specify the vertex mapping induced by the covering, but one necessarily has to deal with the edge mapping as well. We show some solvable cases and, in particular, completely characterize the complexity of the already very nontrivial problem of covering one- and two-vertex (multi)graphs with semi-edges. Our NP-hardness results are proven for simple input graphs, and in the case of regular two-vertex target graphs, even for bipartite ones. We remark that our new characterization results also strengthen previously known results for covering graphs without semi-edges, and they in turn apply to an infinite class of simple target graphs with at most two vertices of degree more than two. Some of the results are moreover proven in a more general setting (e.g., finding k-tuples of pairwise disjoint perfect matchings in regular graphs, or finding equitable partitions of regular bipartite graphs).
Cite as

Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl. Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2021.21,
  author =	{Bok, Jan and Fiala, Ji\v{r}{\'\i} and Hlin\v{e}n\'{y}, Petr and Jedli\v{c}kov\'{a}, Nikola and Kratochv{\'\i}l, Jan},
  title =	{{Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.21},
  URN =		{urn:nbn:de:0030-drops-144611},
  doi =		{10.4230/LIPIcs.MFCS.2021.21},
  annote =	{Keywords: graph cover, covering projection, semi-edges, multigraphs, complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2469
The k-in-a-path Problem for Claw-free Graphs

Authors: Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Testing whether there is an induced path in a graph spanning $k$ given vertices is already \NP-complete in general graphs when $k=3$. We show how to solve this problem in polynomial time on claw-free graphs, when $k$ is not part of the input but an arbitrarily fixed integer.
Cite as

Jiri Fiala, Marcin Kaminski, Bernard Lidický, and Daniël Paulusma. The k-in-a-path Problem for Claw-free Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 371-382, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fiala_et_al:LIPIcs.STACS.2010.2469,
  author =	{Fiala, Jiri and Kaminski, Marcin and Lidick\'{y}, Bernard and Paulusma, Dani\"{e}l},
  title =	{{The k-in-a-path Problem for Claw-free Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{371--382},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2469},
  URN =		{urn:nbn:de:0030-drops-24692},
  doi =		{10.4230/LIPIcs.STACS.2010.2469},
  annote =	{Keywords: Induced path, claw-free graph, polynomial-time algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact