On the parameterized complexity of maximum degree contraction problem

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

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 complexity graph contraction FPT algorithms ETH-lower bound maximum degree contraction no-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
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
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