Header menu link for other important links
X
LP approaches to improved approximation for clique transversal in perfect graphs
Published in Springer Verlag
2014
Volume: 8737 LNCS
   
Pages: 430 - 442
Abstract
Given an undirected simple graph G, a subset T of vertices is an r-clique transversal if it has at least one vertex from every r-clique in G. I.e. T is an r-clique transversal if G-S is K r -free. r-clique transversals generalize vertex covers as a vertex cover is a set of vertices whose deletion results in a graph that is K 2-free. Perfect graphs are a well-studied class of graphs on which a minimum vertex cover can be obtained in polynomial time. However, the problem of finding a minimum r-clique transversal is NP-hard even for r=3. As any induced odd length cycle in a perfect graph is a triangle, a triangle-free perfect graph is bipartite. I.e. in perfect graphs, a 3-clique transversal is an odd cycle transversal. In this work, we describe an(r+1/2) -approximation algorithm for r-clique transversal on weighted perfect graphs improving on the straightforward r-approximation algorithm. We then show that 3-Clique Transversal is APX-hard on perfect graphs and it is NP-hard to approximate it within any constant factor better than 4/3 assuming the unique games conjecture. We also show intractability results in the parameterized complexity framework. © 2014 Springer-Verlag Berlin Heidelberg.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
ISSN03029743
Open AccessNo
Concepts (11)
  •  related image
    Approximation algorithms
  •  related image
    Polynomial approximation
  •  related image
    Constant factors
  •  related image
    MINIMUM VERTEX COVER
  •  related image
    ODD CYCLE TRANSVERSALS
  •  related image
    PARAMETERIZED COMPLEXITY
  •  related image
    Polynomial-time
  •  related image
    R-APPROXIMATION ALGORITHMS
  •  related image
    Triangle-free
  •  related image
    UNIQUE GAMES CONJECTURE
  •  related image
    Graph theory