On the Parameterized Complexity of Maximum Degree Contraction Problem.

DOI10.4230/lipics.ipec.2020.26OpenAlexW3117463086MaRDI QIDQ6089673

Prafullkumar Tale, Saket Saurabh

Publication date: 13 November 2023

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

zbMATH Keywords

lower boundFPT algorithmETHgraph contraction problemsno polynomial kernel

Mathematics Subject Classification ID

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

Related Items (1)

On the parameterized complexity of grid contraction

Cites Work

• Unnamed Item
• 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
• 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
• 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.