(2020) On the Parameterized Approximability of Contraction to Classes of Chordal Graphs.

Text
main.pdf Download (876kB)  Preview 
Abstract
A graph operation that 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 FContraction problem, where F is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph G and an integer k, FContraction asks whether there exists X ⊆ E(G) such that G/X ∈ F and X ≤ k. Here, G/X is the graph obtained from G by contracting edges in X. We obtain the following results for the FContraction problem.  Clique Contraction is known to be FPT. However, unless NP ⊆ coNP/poly, it does not admit a polynomial kernel. We show that it admits a polynomialsize approximate kernelization scheme (PSAKS). That is, it admits a (1 + ε)approximate kernel with {O}(k^{f(ε)}) vertices for every ε > 0.  Split Contraction is known to be W[1]Hard. We deconstruct this intractability result in two ways. Firstly, we give a (2+ε)approximate polynomial kernel for Split Contraction (which also implies a factor (2+ε)FPTapproximation algorithm for Split Contraction). Furthermore, we show that, assuming GapETH, there is no (5/4δ)FPTapproximation algorithm for Split Contraction. Here, ε, δ > 0 are fixed constants.  Chordal Contraction is known to be W[2]Hard. We complement this result by observing that the existing W[2]hardness reduction can be adapted to show that, assuming FPT ≠ W[1], there is no F(k)FPTapproximation algorithm for Chordal Contraction. Here, F(k) is an arbitrary function depending on k alone. We say that an algorithm is an h(k)FPTapproximation algorithm for the FContraction problem, if it runs in FPT time, and on any input (G, k) such that there exists X ⊆ E(G) satisfying G/X ∈ F and X ≤ k, it outputs an edge set Y of size at most h(k) ⋅ k for which G/Y is in F. We find it extremely interesting that three closely related problems have different behavior with respect to FPTapproximation.
Item Type:  Conference or Workshop Item (A Paper) (Paper) 

Divisions:  Dániel Marx (DM) 
Conference:  APPROX International Workshop on Approximation Algorithms for Combinatorial Optimization Problems 
Depositing User:  Prafullkumar Tale 
Date Deposited:  04 May 2021 11:27 
Last Modified:  04 May 2021 11:27 
Primary Research Area:  NRA1: Trustworthy Information Processing 
URI:  https://publications.cispa.saarland/id/eprint/3315 
Actions
Actions (login required)
View Item 