The \(k\) -separator problem: polyhedra, complexity and approximation results

详细信息    查看全文

• 作者：Walid Ben-Ameur (1)
  Mohamed-Ahmed Mohamed-Sidi (1)
  Jos茅 Neto (1)
  
  1. Institut Mines-T茅l茅com ; T茅l茅com SudParis ; CNRS Samovar UMR 5157 ; 9 Rue Charles Fourier ; 91011聽 ; Evry Cedex ; France
  
• 关键词：Graph partitioning ; Complexity theory ; Optimization ; Approximation algorithms ; Polyhedra
• 刊名：Journal of Combinatorial Optimization
• 出版年：2015
• 出版时间：January 2015
• 年：2015
• 卷：29
• 期：1
• 页码：276-307
• 全文大小：427 KB
• 参考文献：1. Arnborg S, Lagergren J, Seese D (1991) Easy problems for tree-decomposable graphs. J Algorithms 12:308鈥?40 CrossRef
  2. Balas E (1998) Disjunctive programming: properties of the convex hull of feasible points. Discret Appl Math 89:1鈥?4 CrossRef
  3. Balas E, de Souza C (2005) The vertex separator problem: a polyhedral investigation. Math Program 103:583鈥?08 CrossRef
  4. Balas E, Yu C (1989) On graphs with polynomially solvable maximum-weight clique problem. Networks 19:247鈥?53 CrossRef
  5. Ben-Ameur W, Mohamed-Sidi M-A., Neto J (2013) The k-separator problem. In: Proceedings of COCOON 2013, Springer LNCS 7936, pp 337鈥?48
  6. Bodlaender HL (1993) A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of STOC鈥?3, pp 226鈥?34
  7. Boliac R, Cameron K, Lozin V (2004) On computing the dissociation number and the induced matching number of bipartite graphs. Ars Combin 72:241253
  8. Borie RB (1995) Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs. Algorithmica 14:123鈥?37 CrossRef
  9. Bornd枚rfer R, Ferreira CE, Martin A (1998) Decomposing matrices into blocks. SIAM J Optim 9:236鈥?69 CrossRef
  10. Broersma H, Kloks T, Kratsch D, M眉ller H (1999) Independent sets in asteroidal triple-free graphs. SIAM J Discret Math 12:276鈥?87 CrossRef
  11. Cameron K, Hell P (2006) Independent packings in structured graphs. Math Program Ser B 105:201鈥?13 CrossRef
  12. Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162:439鈥?85 CrossRef
  13. Gavril F (2000) Maximum weight independent sets and cliques in intersection graphs of filaments. Inf Process Lett 73:181鈥?88 CrossRef
  14. Goldschmidt O, Hochbaum D (1997) K-edge subgraphs problems. Discree Appl Math 74:159鈥?69 CrossRef
  15. Habib M, McConnell R, Paul C, Viennot L (2000) Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing. Theor Comput Sci 234:59鈥?4 CrossRef
  16. Hastad J (1999) Clique is hard to approximate within \(n^{1-\epsilon }\) . Acta Math 182:105鈥?42 CrossRef
  17. Hayard RB (1985) Weakly triangulated graphs. J Combin Theory Ser B 39:200鈥?09 CrossRef
  18. Khot S, Regev O (2008) Vertex cover might be hard to approximate to within \(2- \epsilon \) . J Comput Syst Sci 74:335鈥?49 CrossRef
  19. Kloks T (1994) Treewidth: computations and approximations, vol 842. Lecture Notes in Computer Science, Springer, Berlin
  20. Korte B, Vygen J (2005) Combinatorial optimization: theory and algorithms. Springer, New York
  21. Lozin V, Milanic M (2008) A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J Discret Algorithms 6:595鈥?04 CrossRef
  22. Lozin V, Rautenbach D (2003) Some results on graphs without long induced paths. Inform Process Lett 88:167鈥?71 CrossRef
  23. Minty G (1980) On maximal independent sets of vertices in claw-free graphs. J Combin Theory Ser B 28:284鈥?04 CrossRef
  24. Oosten M, Rutten J, Spiksma F (2007) Disconnecting graphs by removing vertices: a polyhedral approach. Stat Neerl 61:35鈥?0 CrossRef
  25. Orlovich Y, Dolgui A, Finke G, Gordon V, Werner F (2011) The complexity of dissociation set problems in graphs. Discret Appl Math 159:1352鈥?366 CrossRef
  26. Papadimitriou CH, Yannakakis M (1982) The complexity of restricted spanning tree problems. J Assoc Comput Mach 29:285309
  27. Sbihi N (1980) Algorithme de recherche d鈥檜n stable de cardinalit茅 maximum dans un graphe sans 茅toile. Discret Math 29:53鈥?6 CrossRef
  28. Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin
  29. Shmoys D (1997) Cut problems and their application to divide-and-conquer. In: Dorit SH (ed) Approximation algorithms for NP-hard problems. PWS, Boston, pp 192鈥?35
  30. Spinrad JP, Sritharan R (1995) Algorithms for weakly triangulated graphs. Discret Appl Math 59:181鈥?91 CrossRef
  31. Telle JA, Proskurowski A (1997) Algorithms for vertex partitioning problems on partial k-trees. SIAM J Discret Math 10:529鈥?50 CrossRef
  32. Williamson D (2002) The primal-dual method for approximation algorithms. Math Program Ser B 91:447鈥?78 CrossRef
  33. Yannakakis M (1981) Node-deletion problems on bipartite graphs. SIAM J Comput 10:310鈥?27 CrossRef
  34. Zuckerman D (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput 3:103鈥?38 CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

Given a vertex-weighted undirected graph \(G=(V,E,w)\) and a positive integer \(k\) , we consider the \(k\) -separator problem: it consists in finding a minimum-weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to \(k\) . We show that this problem can be solved in polynomial time for some graph classes including bounded treewidth, \(m K_2\) -free, \((G_1, G_2, G_3, P_6)\) -free, interval-filament, asteroidal triple-free, weakly chordal, interval and circular-arc graphs. Polyhedral results with respect to the convex hull of the incidence vectors of \(k\) -separators are reported. Approximation algorithms are also presented.