Approximability of clique transversal in perfect graphs

DOI10.1007/S00453-017-0315-3MaRDI QIDQ724231zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, R. Krithika, N. S. Narayanaswamy, Venkatesh Raman

Publication date 25 July 2018

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-017-0315-3

zbMATH Keywords

linear programmingapproximation algorithmsperfect graphsodd cycle transversalr-clique transversal

Mathematics Subject Classification ID

Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Perfect graphs (05C17)

Recommendations

• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
• Approximation algorithms for clique transversals on some graph classes
• On clique-transversals and clique-independent sets
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs

Cites work

• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• scientific article; zbMATH DE number 2044950 (Why is no real title available?)
• A kernelization algorithm for \(d\)-hitting set
• Algorithmic graph theory and perfect graphs
• Another disjoint compression algorithm for odd cycle transversal
• Approximation algorithms for NP-hard problems.
• Faster parameterized algorithms using linear programming
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
• Finding odd cycle transversals.
• Geometric algorithms and combinatorial optimization
• Half-integrality, LP-branching, and FPT algorithms
• Kernels: Annotated, Proper and Induced
• Normal hypergraphs and the perfect graph conjecture
• On the complexity of \(k\)-SAT
• On the existence of subexponential parameterized algorithms
• On the hardness of approximating minimum vertex cover
• Parameterized algorithms
• Parameterized algorithms for \((r,l)\)-partization
• Properties of vertex packing and independence system polyhedra
• Recognizing Berge graphs
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• The design of approximation algorithms
• The node-deletion problem for hereditary properties is NP-complete
• The sandwich theorem
• The strong perfect graph theorem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex packings: Structural properties and algorithms

Cited in

(7)

• Optimal‐size clique transversals in chordal graphs
• Computing the clique number of \(a\)-perfect graphs in polynomial time
• Approximation algorithms for clique transversals on some graph classes
• The algorithmic complexity of the minus clique-transversal problem
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Reconfiguration of colorable sets in classes of perfect graphs
• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs

This page was built for publication: Approximability of clique transversal in perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q724231)