On the parameterized complexity of contraction to generalization of trees

DOI10.4230/LIPICS.IPEC.2017.1MaRDI QIDQ5111860zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Saket Saurabh, Prafullkumar Tale

Publication date 27 May 2020

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

zbMATH Keywords

graph algorithmsfixed-parameter tractabilitygraph contractiongeneralization of trees

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: For a family of graphs $calF$, the $mathcalF$-Contraction problem takes as an input a graph $G$ and an integer $k$, and the goal is to decide if there exists $SsubseteqE(G)$ of size at most $k$ such that $G/S$ belongs to $calF$. Here, $G/S$ is the graph obtained from $G$ by contracting all the edges in $S$. Heggernes et al.~[Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied $calF$-Contraction when $calF$ is a simple family of graphs such as trees and paths. In this paper, we study the $mathcalF$-Contraction problem, where $calF$ generalizes the family of trees. In particular, we define this generalization in a "parameterized way". Let $mathbb{T}_{e}ll$ be the family of graphs such that each graph in $mathbb{T}_{e}ll$ can be made into a tree by deleting at most $ell$ edges. Thus, the problem we study is $mathbb{T}_{e}ll$-Contraction. We design an FPT algorithm for $mathbb{T}_{e}ll$-Contraction running in time $mathcalO((2sqrt(ell){)}^{mathcalO(k+ell)}cdot{n}^{mathcalO(1)})$. Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by $k$. Inspired by the negative result for the kernelization, we design a lossy kernel for $mathbb{T}_{e}ll$-Contraction of size $mathcalO([k(k+2ell){]}^{(lceilfracalphaalpha-1ceil+1)})$.

Recommendations

• On the parameterized complexity of contraction to generalization of trees
• Paths to trees and cacti
• An FPT algorithm for contraction to cactus

Cites work

• scientific article; zbMATH DE number 1222098 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 6862097 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Contracting few edges to remove forbidden induced subgraphs
• Deterministic parameterized connected vertex cover
• Edge-contraction problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fundamentals of parameterized complexity
• Improved kernel results for some FPT problems based on simple observations
• Obtaining a bipartite graph by contracting few edges
• Obtaining planarity by contracting few edges
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• On the NP-hardness of edge-deletion and -contraction problems
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• Parameterized algorithms
• Parameterized complexity of three edge contraction problems with degree constraints
• Parametrized complexity theory.
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

Cited in

(8)

• Paths to trees and cacti
• Reducing the vertex cover number via edge contractions
• An FPT algorithm for contraction to cactus
• Lossy kernels for graph contraction problems
• On the parameterized complexity of contraction to generalization of trees
• Paths to trees and cacti
• On the parameterized complexity of grid contraction
• Lossy kernelization of same-size clustering

This page was built for publication: On the parameterized complexity of contraction to generalization of trees

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