2026-07-22T19:23:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3403 2024-03-06T10:34:10Z ddc:004 open_access

Contraction checking in graphs on surfaces Kaminski, Marcin Thilikos, Dimitrios M. Surfaces Topological Minors Contractions Parameterized algorithms Linkages 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marcin Kaminski and Dimitrios M. Thilikos 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.182 urn:nbn:de:0030-drops-34032 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.182 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode