On the Parameterized Complexity of Maximum Degree Contraction Problem.

DOI10.4230/LIPICS.IPEC.2020.26OpenAlexW3117463086MaRDI QIDQ6089673FDOQ6089673

Publication date: 13 November 2023

Full work available at URL: https://dblp.uni-trier.de/db/conf/iwpec/ipec2020.html#0001T20

lower bound FPT algorithm ETH graph contraction problems no polynomial kernel

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

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

Cited In (8)

Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
Parameterized complexity of three edge contraction problems with degree constraints
On the parameterized complexity of grid contraction
On the parameterized complexity of the Maximum Exposure Problem
A general framework for computing maximal contractions
A decomposition based algorithm for maximal contractions
Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)
Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization

This page was built for publication: On the Parameterized Complexity of Maximum Degree Contraction Problem.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6089673)