Contraction checking in graphs on surfaces

Authors Marcin Kaminski, Dimitrios M. Thilikos



PDF
Thumbnail PDF

File

LIPIcs.STACS.2012.182.pdf
  • Filesize: 2.3 MB
  • 12 pages

Document Identifiers

Author Details

Marcin Kaminski
Dimitrios M. Thilikos

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.STACS.2012.182

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.
Keywords
  • Surfaces
  • Topological Minors
  • Contractions
  • Parameterized algorithms
  • Linkages

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
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