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--. 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 \((\frac{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 \(\frac{4}{3}\) assuming the unique games conjecture. We also show intractability results in the parameterized complexity framework." />
用户名： 密码： 验证码：
LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
详细信息    查看全文
  • 作者：Samuel Fiorini (17)
    R. Krithika (18)
    N. S. Narayanaswamy (18)
    Venkatesh Raman (19)
  • 刊名：Lecture Notes in Computer Science
  • 出版年：2014
  • 出版时间：2014
  • 年：2014
  • 卷：8737
  • 期：1
  • 页码：430-442
  • 全文大小：276 KB
  • 参考文献：1. Abu-Khzama, F.N.: A kernelization algorithm for d-hitting set. Journal of Computer and System Sciences?76(7), 524-31 (2010) k" title="It opens in new window">CrossRef
    2. Berge, C.: F?rbung von graphen, deren s?mtliche bzw. deren ungerade kreise starr sind (zusammenfassung). Wissenschaftliche Zeitschrift, Martin Luther Universit?t Halle-Wittenberg Mathematisch-Naturwissenschaftliche Reihe 10, 114-15 (1961)
    3. Berry, L.A., Kennedy, W.S., King, A.D., Li, Z., Reed, B.A.: Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph. Discrete Applied Mathematics?158(7), 765-70 (2010) k" title="It opens in new window">CrossRef
    4. Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. Journal of Computer and System Sciences?67, 789-07 (2003) k" title="It opens in new window">CrossRef
    5. Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R.: The strong perfect graph theorem. Annals of Mathematics?164(1), 51-29 (2006) k" title="It opens in new window">CrossRef
    6. Dell, H., Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 251-60 (2010)
    7. Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics?162(1), 439-85 (2005) k" title="It opens in new window">CrossRef
    8. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Elsevier Science B.V. (2004)
    9. Gr?tschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer (1988)
    10. Guruswami, V., Lee, E.: Inapproximability of feedback vertex set for bounded length cycles. Electronic Colloquium on Computational Complexity (ECCC)?21, 6 (2014)
    11. Iwata, Y., Oka, K., Yuichi, Y.: Linear-time fpt algorithms via network flow. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 1749-761 (2014)
    12. Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2??-em class="a-plus-plus">ε. Journal of Computer and System Sciences?74(3), 335-49 (2008) k" title="It opens in new window">CrossRef
    13. Knuth, D.: The sandwich theorem. Electronic Journal of Combinatorics?1(A1), 1-8 (1994)
    14. Kratsch, S., Wahlstr?m, M.: Compression via matroids: A randomized polynomial kernel for odd cycle transversal. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 94-03 (2012)
    15. Krithika, R., Narayanaswamy, N.S.: Another disjoint compression algorithm for odd cycle transversal. Information Processing Letters?113(22-4), 849-51 (2013) k" title="It opens in new window">CrossRef
    16. Krithika, R., Narayanaswamy, N.S.: Parameterized algorithms for ( / r, / l)-partization. Journal of Graph Algorithms and Applications?17(2), 129-46 (2013) k" title="It opens in new window">CrossRef
    17. Lokshtanov, D., Narayanaswamy, N.S., Raman, V., Ramanujan, M.S., Saurabh, S.: Faster parameterized algorithms using linear programming. CoRR abs/1203.0833. A preliminary version appeared in the Proceedings of STACS (2012)
    18. Lovász, L.: On minimax theorems of combinatorics. Ph.D thesis, Matemathikai Lapok 26, 209-64 (1975)
    19. Nemhauser, G.L., Trotter, L.E.: Properties of vertex packing and independence system polyhedra. Mathematical Programming?6(1), 48-1 (1974) k" title="It opens in new window">CrossRef
    20. Nemhauser, G.L., Trotter, L.E.: Vertex packings: Structural properties and algorithms. Mathematical Programming?8(1), 232-48 (1975) k" title="It opens in new window">CrossRef
    21. Reed, B.A., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters?32, 299-01 (2004) k" title="It opens in new window">CrossRef
    22. Wagler, A.: Critical and anticritical edges in perfect graphs. In: Brandst?dt, A., Van Le, B. (eds.) WG 2001. LNCS, vol.?2204, pp. 317-27. Springer, Heidelberg (2001) k" title="It opens in new window">CrossRef
    23. Wahlstr?m, M.: Half-integrality, lp-branching and fpt algorithms. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 1762-781 (2014)
  • 作者单位：Samuel Fiorini (17)
    R. Krithika (18)
    N. S. Narayanaswamy (18)
    Venkatesh Raman (19)

    17. Département de Mathématique, Université libre de Bruxelles, Brussels, Belgium
    18. Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, India
    19. The Institute of Mathematical Sciences, Chennai, India
  • ISSN：1611-3349
文摘
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??-em class="a-plus-plus">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--. 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 \((\frac{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 \(\frac{4}{3}\) assuming the unique games conjecture. We also show intractability results in the parameterized complexity framework.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址：北京市海淀区学院路29号 邮编：100083

电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700