On the Parameterized Complexity of Contraction to Generalization of Trees.

DOI10.4230/LIPIcs.IPEC.2017.1zbMath1435.68120arXiv1708.00622OpenAlexW2909582894MaRDI QIDQ5111860

Prafullkumar Tale, Saket Saurabh, Akanksha Agrawal

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1708.00622

zbMATH Keywords

graph algorithmsfixed-parameter tractabilitygraph contractiongeneralization of trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Reducing the vertex cover number via edge contractions ⋮ Lossy kernelization of same-size clustering

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Parameterized complexity of three edge contraction problems with degree constraints
• Improved kernel results for some FPT problems based on simple observations
• Edge-contraction problems
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On the NP-hardness of edge-deletion and -contraction problems
• Obtaining planarity by contracting few edges
• Contracting graphs to paths and trees
• A faster FPT algorithm for bipartite contraction
• Parametrized complexity theory.
• Contracting Few Edges to Remove Forbidden Induced Subgraphs
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Deterministic Parameterized Connected Vertex Cover
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms