TY - GEN

T1 - Contraction checking in graphs on surfaces

AU - Kamiński, Marcin

AU - Thilikos, Dimitrios M.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Contractions

KW - Linkages

KW - Parameterized algorithms

KW - Surfaces

KW - Topological Minors

UR - http://www.scopus.com/inward/record.url?scp=84880318116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880318116&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2012.182

DO - 10.4230/LIPIcs.STACS.2012.182

M3 - Conference contribution

AN - SCOPUS:84880318116

SN - 9783939897354

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 182

EP - 193

BT - 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012

Y2 - 29 February 2012 through 3 March 2012

ER -