DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2012.182

Contraction checking in graphs on surfaces

Authors: Marcin Kaminski and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract

The Contraction Checking problem asks, given two graphs H and G as input, whether H can be obtained from G by a sequence of edge contractions. Contraction Checking remains NP-complete, even when H is fixed. We show that this is not the case when G is embeddable in a surface of fixed Euler genus. In particular, we give an algorithm that solves Contraction Checking in f(h,g)*|V(G)|^3 steps, where h is the size of H and g is the Euler genus of the input graph G.

Cite as

Marcin Kaminski and Dimitrios M. Thilikos. Contraction checking in graphs on surfaces. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 182-193, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kaminski_et_al:LIPIcs.STACS.2012.182,
  author =	{Kaminski, Marcin and Thilikos, Dimitrios M.},
  title =	{{Contraction checking in graphs on surfaces}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{182--193},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.182},
  URN =		{urn:nbn:de:0030-drops-34032},
  doi =		{10.4230/LIPIcs.STACS.2012.182},
  annote =	{Keywords: Surfaces, Topological Minors, Contractions, Parameterized algorithms, Linkages}
}

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}
}

Search Results

Documents authored by Kaminski, Marcin

Contraction checking in graphs on surfaces

Abstract

Cite as

The k-in-a-path Problem for Claw-free Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message