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 -