2020/06/18 by Spoorthy Gunda, Pallavi Jain, Gunda, Spoorthy +7
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2006.10364
openalex publication_date 2020/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph operation that em contracts edges is one of the fundamental\noperations in the theory of graph minors. Parameterized Complexity of editing\nto a family of graphs by contracting k edges has recently gained substantial\nscientific attention, and several new results have been obtained. Some\nimportant families of graphs, namely the subfamilies of chordal graphs, in the\ncontext of edge contractions, have proven to be significantly difficult than\none might expect. In this paper, we study the \ cal F-Contraction\nproblem, where cal F is a subfamily of chordal graphs, in the realm of\nparameterized approximation. Formally, given a graph G and an integer k,\n\ cal F-Contraction asks whether there exists X \⊆ E(G)\nsuch that G/X \∈ cal F and |X| \≤ k. Here, G/X is the graph obtained\nfrom G by contracting edges in X. We obtain the following results for the\n\ cal F-Contraction problem. (1) We show that \Clique\nContraction admits a polynomial-size approximate kernelization scheme\n( textsfPSAKS). (2) We give a (2+\ε)-approximate polynomial kernel\nfor \Split Contraction (which also implies a factor\n(2+\ε)- FPT-approximation algorithm for \ Split Contraction).\nFurthermore, we show that, assuming textsf Gap-ETH, there is no\n\(\(5)/(4)-\δ \)- FPT-approximation algorithm for\n\Split Contraction. Here, \ε, \δ>0 are fixed constants.\n(3) \Chordal Contraction is known to be WTH. We complement this\nresult by observing that the existing textsfW[2]-hardness reduction can be\nadapted to show that, assuming FPT \≠ textsfW[1], there is no\nF(k)- FPT-approximation algorithm for \Chordal Contraction. Here,\nF(k) is an arbitrary function depending on k alone.\n