×

zbMATH — the first resource for mathematics

Partitioning perfect graphs into stars. (English) Zbl 1365.05238
Summary: The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-complete cases, for example, on grid graphs and chordal graphs.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C17 Perfect graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Asdre, NP-completeness results for some problems on subclasses of bipartite and chordal graphs, Theor Comput Sci 381 (1-3) pp 248– (2007) · Zbl 1188.68208 · doi:10.1016/j.tcs.2007.05.012
[2] Berman, Generalized planar matching, J Algorithms 11 (2) pp 153– (1990) · Zbl 0731.68041 · doi:10.1016/0196-6774(90)90001-U
[3] Bevern, Network-based vertex dissolution, SIAM J Discrete Math 29 (2) pp 888– (2015a) · Zbl 1327.68139 · doi:10.1137/140978880
[4] R. van Bevern C. Komusiewicz H. Moser R. Niedermeier Measuring indifference: Unit interval vertex deletion Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’10) LNCS Berlin Heidelberg 2010 232 243
[5] Bevern, Interval scheduling and colorful independent sets, J Scheduling 18 (5) pp 449– (2015b) · Zbl 1328.90065 · doi:10.1007/s10951-014-0398-5
[6] Brandstädt, Graph Classes: A Survey, volume 3 of SIAM Monographs on Discrete Mathematics and Applications (1999) · Zbl 0919.05001 · doi:10.1137/1.9780898719796
[7] Chalopin, Packing bipartite graphs with covers of complete bipartite graphs, Discrete Appl Math 168 pp 40– (2014) · Zbl 1285.05146 · doi:10.1016/j.dam.2012.08.026
[8] Cohen, NP-completeness of graph decomposition problems, J Complexity 7 (2) pp 200– (1991) · Zbl 0741.68055 · doi:10.1016/0885-064X(91)90006-J
[9] Corneil, The LBFS structure and recognition of interval graphs, SIAM J Discrete Math 23 (4) pp 1905– (2009) · Zbl 1207.05131 · doi:10.1137/S0895480100373455
[10] Corneil, A linear recognition algorithm for cographs, SIAM J Comput 14 (4) pp 926– (1985) · Zbl 0575.68065 · doi:10.1137/0214065
[11] Cornuéjols, General factors of graphs, J Combin Theory B 45 (2) pp 185– (1988) · Zbl 0607.05053 · doi:10.1016/0095-8956(88)90068-8
[12] Dahlhaus, Matching and multidimensional matching in chordal and strongly chordal graphs, Discrete Appl Math 84 (1-3) pp 79– (1998) · Zbl 0902.68146 · doi:10.1016/S0166-218X(98)00006-7
[13] Bontridder, Approximation algorithms for the test cover problem, Math Program 98 (1-3) pp 477– (2003) · Zbl 1160.90646 · doi:10.1007/s10107-003-0414-6
[14] Dyer, On the complexity of partitioning graphs into connected subgraphs, Discrete Appl Math 10 (2) pp 139– (1985) · Zbl 0562.68030 · doi:10.1016/0166-218X(85)90008-3
[15] Dyer, Planar 3DM is NP-complete, J Algorithms 7 (2) pp 174– (1986) · Zbl 0606.68065 · doi:10.1016/0196-6774(86)90002-7
[16] Garey, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)
[17] Golumbic, Algorithmic Graph Theory and Perfect Graphs (2004) · Zbl 1050.05002
[18] Kirkpatrick, On the complexity of general graph factor problems, SIAM Journal on Computing 12 (3) pp 601– (1983) · Zbl 0525.68023 · doi:10.1137/0212040
[19] Kolen, Interval scheduling: A survey, Naval Res Log 54 (5) pp 530– (2007) · Zbl 1143.90337 · doi:10.1002/nav.20231
[20] A. Kosowski M. Małafiejski P. \.Zyĺinski Parallel processing subsystems with redundancy in a distributed environment Proceedings of the 6th International Conference on Parallel Processing and Applied Mathematics (PPAM ’05) LNCS Springer Berlin Heidelberg 2006 1002 1009
[21] Lovász, Nowhere-zero 3-flows and modulo k-orientations, J Combin Theory B 103 (5) pp 587– (2013) · Zbl 1301.05154 · doi:10.1016/j.jctb.2013.06.003
[22] M. Małafiejski P. \.Zyliński Weakly cooperative guards in grids Proceedings of the International Conference on Computational Science and Its Applications (ICCSA ’05) LNCS Springer Berlin Heidelberg 2005 647 656
[23] Monnot, The path partition problem and related problems in bipartite graphs, Oper Res Lett 35 (5) pp 677– (2007) · Zbl 1129.05034 · doi:10.1016/j.orl.2006.12.004
[24] Panda, A linear time recognition algorithm for proper interval graphs, Inform Proc Lett 87 (3) pp 153– (2003) · Zbl 1161.68855 · doi:10.1016/S0020-0190(03)00298-9
[25] Rooij, Partition into triangles on bounded degree graphs, Theory Comput Syst 52 (4) pp 687– (2013) · Zbl 1286.68214 · doi:10.1007/s00224-012-9412-5
[26] Rosenstiehl, Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput Geom 1 (1) pp 343– (1986) · Zbl 0607.05027 · doi:10.1007/BF02187706
[27] Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (2003)
[28] Spinrad, Bipartite permutation graphs, Discrete Appl Math 18 (3) pp 279– (1987) · Zbl 0628.05055 · doi:10.1016/S0166-218X(87)80003-3
[29] Steiner, On the k-path partition problem in cographs, Congr Numer 147 pp 89– (2000) · Zbl 0976.05053
[30] Steiner, On the k-path partition of graphs, Theor Comput Sci 290 (3) pp 2147– (2003) · Zbl 1044.68134 · doi:10.1016/S0304-3975(02)00577-7
[31] Takamizawa, Linear-time computability of combinatorial problems on series-parallel graphs, J ACM 29 (3) pp 623– (1982) · Zbl 0485.68055 · doi:10.1145/322326.322328
[32] Thomassen, The weak 3-flow conjecture and the weak circular flow conjecture, J Combin Theory B 102 (2) pp 521– (2012) · Zbl 1239.05083 · doi:10.1016/j.jctb.2011.09.003
[33] Yan, k-path partitions in trees, Discrete Appl Math 78 (1-3) pp 227– (1997) · Zbl 0890.68101 · doi:10.1016/S0166-218X(97)00012-7
[34] Yan, Quasi-threshold graphs, Discrete Appl Math 69 (3) pp 247– (1996) · Zbl 0857.05082 · doi:10.1016/0166-218X(96)00094-7
[35] Yuster, Combinatorial and computational aspects of graph packing and graph decomposition, Comput Sci Rev 1 (1) pp 12– (2007) · Zbl 1302.05149 · doi:10.1016/j.cosrev.2007.07.002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.