Gunda, Spoorthy ;
Jain, Pallavi ;
Lokshtanov, Daniel ;
Saurabh, Saket ;
Tale, Prafullkumar
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
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.
BibTeX  Entry
@InProceedings{gunda_et_al:LIPIcs:2020:12654,
author = {Spoorthy Gunda and Pallavi Jain and Daniel Lokshtanov and Saket Saurabh and Prafullkumar Tale},
title = {{On the Parameterized Approximability of Contraction to Classes of Chordal Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {51:151:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12654},
URN = {urn:nbn:de:0030drops126545},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.51},
annote = {Keywords: Graph Contraction, FPTApproximation, Inapproximability, Lossy Kernels}
}
11.08.2020
Keywords: 

Graph Contraction, FPTApproximation, Inapproximability, Lossy Kernels 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 