On the parameterized approximability of contraction to classes of chordal graphs

DOI10.1145/3470869MaRDI QIDQ5066147zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

FPT-approximationgraph contractioninapproximabilitylossy kernels

Mathematics Subject Classification ID

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

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.

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

Cited in

(10)

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

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)