×

List matrix partitions of chordal graphs. (English) Zbl 1084.05026

Summary: It is well known that a clique with \(k+1\) vertices is the only minimal obstruction to \(k\)-colourability of chordal graphs. A similar result is known for the existence of a cover by \(\ell\) cliques. Both of these problems are in fact partition problems, restricted to chordal graphs. The first seeks partitions into \(k\) independent sets, and the second is equivalent to finding partitions into \(\ell\) cliques. In an earlier paper we proved that a chordal graph can be partitioned into \(k\) independent sets and \(\ell\) cliques if and only if it does not contain an induced disjoint union of \(\ell+1\) cliques of size \(k+1\). (A linear time algorithm for finding such partitions can be derived from the proof.)
In this paper we expand our focus and consider more general partitions of chordal graphs. For each symmetric matrix \(M\) over \(0,1,*\), the \(M\)-partition problem seeks a partition of the input graph into independent sets, cliques, or arbitrary sets, with certain pairs of sets being required to have no edges, or to have all edges joining them, as encoded in the matrix \(M\). Moreover, the vertices of the input chordal graph can be equipped with lists, restricting the parts to which a vertex can be placed. Such (list) partitions generalize (list) colourings and (list) homomorphisms, and arise frequently in the theory of graph perfection. We show that many \(M\)-partition problems that are NP-complete in general become solvable in polynomial time for chordal graphs, even in the presence of lists. On the other hand, we show that there are \(M\)-partition problems (without lists) that remain NP-complete for chordal graphs. It is not known whether or not each list \(M\)-partition problem is NP-complete or polynomial, but it has been shown that each is NP-complete or quasi-polynomial \((n^{O(\log n)})\). For chordal graphs even this ‘quasi-dichotomy’ is not known, but we do identify large families of matrices \(M\) for which dichotomy, or at least quasi-dichotomy, holds.
We also discuss forbidden subgraph characterizations of graphs admitting an \(M\)-partition. Such characterizations have recently been investigated for partitions of perfect graphs, and we focus on highlighting the improvements one can obtain for the class of chordal, rather than just perfect, graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bodlaender, H. L.; Kloks, T., Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms, 21, 358-402 (1996) · Zbl 0861.68036
[2] Brandstädt, A., Partitions of graphs into one or two stable sets and cliques, Discrete Math., 152, 47-54 (1996) · Zbl 0853.68140
[3] A. Brandstädt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs, DIMACS TR 2002-44.; A. Brandstädt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs, DIMACS TR 2002-44.
[4] K. Cameron, E.M. Eschen, C.T. Hoang, R. Sritharan, The list partition problem for graphs, SODA 2004, 2004.; K. Cameron, E.M. Eschen, C.T. Hoang, R. Sritharan, The list partition problem for graphs, SODA 2004, 2004. · Zbl 1318.05072
[5] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, eprint arXiv:math/0212070.; M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, eprint arXiv:math/0212070.
[6] Chvátal, V., Star-cutsets and perfect graphs, J. Combin. Theory B, 39, 189-199 (1985) · Zbl 0674.05058
[7] de Figueiredo, C. M.H.; Klein, S.; Kohayakawa, Y.; Reed, B. A., Finding skew partitions efficiently, J. Algorithms, 37, 505-521 (2000) · Zbl 0964.68107
[8] J. Diaz, M. Serna, D.M. Thilikos, Recent results on parametrized \(H\); J. Diaz, M. Serna, D.M. Thilikos, Recent results on parametrized \(H\) · Zbl 1060.05030
[9] T. Feder, P. Hell, Full constraint satisfaction problems, manuscript.; T. Feder, P. Hell, Full constraint satisfaction problems, manuscript. · Zbl 1111.68115
[10] T. Feder, P. Hell, Matrix partitions of perfect graphs, Special Issue of Discrete Math., in Memory of Claude Berge, 2005.; T. Feder, P. Hell, Matrix partitions of perfect graphs, Special Issue of Discrete Math., in Memory of Claude Berge, 2005.
[11] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048
[12] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033
[13] Feder, T.; Hell, P.; Klein, S.; Motwani, R., Complexity of list partitions, (Proc. 31st Annu. ACM Symp. on Theory of Computing (1999)), 464-472 · Zbl 1345.68171
[14] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 449-478 (2003) · Zbl 1029.05143
[15] T. Feder, P. Hell, S. Klein, L. Tito Nogueira, F. Protti, List matrix partitions of chordal graphs, LATIN 2004, Lecture Notes in Computer Science, Vol. 2976, 2004, pp. 100-108.; T. Feder, P. Hell, S. Klein, L. Tito Nogueira, F. Protti, List matrix partitions of chordal graphs, LATIN 2004, Lecture Notes in Computer Science, Vol. 2976, 2004, pp. 100-108. · Zbl 1196.05060
[16] T. Feder, P. Hell, S. Klein, L. Tito Nogueira, F. Protti, Chordal obstructions to \(M\) www.cs.sfu.ca/\( \sim;\); T. Feder, P. Hell, S. Klein, L. Tito Nogueira, F. Protti, Chordal obstructions to \(M\) www.cs.sfu.ca/\( \sim;\)
[17] T. Feder, P. Hell, D. Král’, J. Sgall, Two algorithms for general list matrix partitions, SODA 2005, 2005.; T. Feder, P. Hell, D. Král’, J. Sgall, Two algorithms for general list matrix partitions, SODA 2005, 2005. · Zbl 1297.68091
[18] T. Feder, P. Hell, K.M. Tucker-Nally, Digraph matrix partitions and trigraph homomorphisms, manuscript.; T. Feder, P. Hell, K.M. Tucker-Nally, Digraph matrix partitions and trigraph homomorphisms, manuscript. · Zbl 1106.05060
[19] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[20] Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Appl. Math., 141, 185-194 (2004) · Zbl 1043.05097
[21] Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Packing \(r\)-cliques in weighted chordal graphs, Ann. Oper. Res., 138, 179-187 (2005) · Zbl 1091.90073
[22] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press: Oxford University Press Oxford · Zbl 1062.05139
[23] McConnel, R. M.; Spinrad, J. P., Linear time modular decomposition and efficient transitive orientation of comparability graphs, (Proc. ACM-SIAM Symp. on Discrete Algorithms (1994)), 536-545 · Zbl 0867.05068
[24] A. Proskurowski, S. Arnborg, Linear time algorithms for NP-hard problems restricted to partial \(k\); A. Proskurowski, S. Arnborg, Linear time algorithms for NP-hard problems restricted to partial \(k\) · Zbl 0666.68067
[25] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039
[26] Tucker, A., Coloring graphs with stable sets, J. Combin. Theory Ser. B, 34, 258-267 (1983) · Zbl 0498.05028
[27] Whitesides, S., An algorithm for finding clique cutsets, Inform. Process. Lett., 12, 31-32 (1981) · Zbl 0454.68078
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.