An improved linear kernel for the cycle contraction problem

DOI10.1016/J.IPL.2019.05.003MaRDI QIDQ2274484zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 20 September 2019

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

edge contractiongraph algorithmslinear kernelparameterized tractability

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The problem of modifying a given graph to satisfy certain properties has been one of the central topics in parameterized tractability study. In this paper, we study the cycle contraction problem, which makes a graph into a cycle by edge contractions. The problem has been studied {by Belmonte et al. [IPEC 2013]} who obtained a linear kernel with at most $6k+6$ vertices. We provide an improved kernel with at most $5k+4$ vertices for it in this paper.

Recommendations

• Paths to trees and cacti
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Parameterized complexity of three edge contraction problems with degree constraints

Cites work

• Editing graphs to satisfy degree constraints: a parameterized approach
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Improved kernel results for some FPT problems based on simple observations
• Increasing the minimum degree of a graph by contractions
• Obtaining a bipartite graph by contracting few edges
• Obtaining planarity by contracting few edges
• Obtaining split graphs by edge contraction
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Parameterized complexity of three edge contraction problems with degree constraints

Cited in

(4)

• Improved kernel results for some FPT problems based on simple observations
• Contracting to a longest path in H-free graphs
• Revisiting path contraction and cycle contraction
• Revisiting path contraction and cycle contraction

This page was built for publication: An improved linear kernel for the cycle contraction problem

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