On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges

DOI10.1007/978-3-319-03898-8_21zbMath1406.68034OpenAlexW281935416MaRDI QIDQ2867087

Daniel Lokshtanov, Neeldhara Misra, Saket Saurabh

Publication date: 10 December 2013

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03898-8_21

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (15)

Paths to Trees and Cacti ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ Hadwiger Number of Graphs with Small Chordality ⋮ On the parameterized complexity of grid contraction ⋮ Reducing the vertex cover number via edge contractions ⋮ Obtaining split graphs by edge contraction ⋮ A single exponential-time FPT algorithm for cactus contraction ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Contracting to a longest path in H-free graphs ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Paths to trees and cacti ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ An improved linear kernel for the cycle contraction problem ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees. ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

This page was built for publication: On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges