On the parameterized approximability of contraction to classes of chordal graphs

DOI10.1145/3470869zbMATH Open1495.68178arXiv2006.10364OpenAlexW3196689725MaRDI QIDQ5066147FDOQ5066147

Authors: Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh, Prafullkumar Tale 

Publication date: 29 March 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Abstract: A graph operation that {em contracts edges} is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting $k$ edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this paper, we study the extsc{$calF$-Contraction} problem, where $calF$ is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph $G$ and an integer $k$, extsc{ $calF$-Contraction} asks whether there exists $XsubseteqE(G)$ such that $G/XincalF$ and $|X|leqk$. Here, $G/X$ is the graph obtained from $G$ by contracting edges in $X$. We obtain the following results for the extsc{ $calF$-Contraction} problem. $(1)$ We show that extsc{Clique Contraction} admits a polynomial-size approximate kernelization scheme ( extsf{PSAKS}). $(2)$ We give a $(2+epsilon)$-approximate polynomial kernel for extsc{Split Contraction} (which also implies a factor $(2+epsilon)$-FPT-approximation algorithm for extsc{ Split Contraction}). Furthermore, we show that, assuming extsf{ Gap-ETH}, there is no $left(frac54-deltaight)$-FPT-approximation algorithm for extsc{Split Contraction}. Here, $epsilon,delta>0$ are fixed constants. $(3)$ extsc{Chordal Contraction} is known to be WTH. We complement this result by observing that the existing extsf{W[2]-hardness} reduction can be adapted to show that, assuming FPT $eq$ extsf{W[1]}, there is no $F(k)$-FPT-approximation algorithm for extsc{Chordal Contraction}. Here, $F(k)$ is an arbitrary function depending on $k$ alone.

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

Recommendations

• Obtaining split graphs by edge contraction
• Obtaining split graphs by edge contraction
• Contracting few edges to remove forbidden induced subgraphs
• scientific article; zbMATH DE number 6862097
• Split contraction: the untold story

zbMATH Keywords

inapproximabilitygraph contractionlossy kernelsFPT-approximation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Graph operations (line graphs, products, etc.) (05C76) Parameterized complexity, tractability and kernelization (68Q27)

Cited In (10)

• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Edge contractions in subclasses of chordal graphs
• Lossy kernels for graph contraction problems
• Split contraction: the untold story
• Obtaining split graphs by edge contraction
• Obtaining split graphs by edge contraction
• On the parameterized complexity of maximum degree contraction problem
• Contracting few edges to remove forbidden induced subgraphs
• Title not available (Why is that?)

This page was built for publication: On the parameterized approximability of contraction to classes of chordal graphs

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