On the parameterized complexity of maximum degree contraction problem

DOI10.1007/S00453-021-00897-6OpenAlexW4226428923MaRDI QIDQ832521

Saket Saurabh, Prafullkumar Tale

Publication date: 25 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/13329/

zbMATH Keywords

parameterized complexitygraph contractionFPT algorithmsETH-lower boundmaximum degree contractionno-poly kernel

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

A single exponential-time FPT algorithm for cactus contraction

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Increasing the minimum degree of a graph by contractions
• Parameterized complexity of three edge contraction problems with degree constraints
• A generalization of Nemhauser and Trotter's local optimization theorem
• On bounded-degree vertex deletion parameterized by treewidth
• Edge-contraction problems
• Isolation concepts for efficiently enumerating dense subgraphs
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• An FPT algorithm for contraction to cactus
• On the NP-hardness of edge-deletion and -contraction problems
• Reduction algorithms for graphs of small treewidth
• Obtaining planarity by contracting few edges
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• On the parameterized complexity of contraction to generalization of trees
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Contracting graphs to paths and trees
• A faster FPT algorithm for bipartite contraction
• Parametrized complexity theory.
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• Contracting Few Edges to Remove Forbidden Induced Subgraphs
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• A 4 k ² kernel for feedback vertex set
• Path Contraction Faster than $2^n$
• On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
• A Linear Kernel for Co-Path/Cycle Packing
• Contractibility and NP-completeness
• Color-coding
• Lossy Kernels for Graph Contraction Problems
• Kernelization
• Lossy kernelization
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Split Contraction
• Paths to Trees and Cacti
• Obtaining a Bipartite Graph by Contracting Few Edges
• Parameterized Algorithms
• Slightly Superexponential Parameterized Problems
• On the Parameterized Complexity Of Grid Contraction
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

This page was built for publication: On the parameterized complexity of maximum degree contraction problem