On the parameterized complexity of contraction to generalization of trees

DOI10.4230/LIPICS.IPEC.2017.1zbMATH Open1435.68120arXiv1708.00622OpenAlexW2909582894MaRDI QIDQ5111860FDOQ5111860

Prafullkumar Tale, Saket Saurabh, Akanksha Agrawal

Publication date: 27 May 2020

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)})$.

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

Recommendations

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parametrized complexity theory.
• Title not available (Why is that?)
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• Title not available (Why is that?)
• Contracting graphs to paths and trees
• Obtaining planarity 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
• Obtaining a bipartite graph by contracting few edges
• Edge-contraction problems
• 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
• Deterministic Parameterized Connected Vertex Cover
• Title not available (Why is that?)
• Improved kernel results for some FPT problems based on simple observations
• Title not available (Why is that?)

Cited In (2)

• Reducing the vertex cover number via edge contractions
• 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)