×

Matrix partitions of perfect graphs. (English) Zbl 1143.05035

Authors’ abstract: Given a symmetric \(m\times m\) matrix \(M\) over 0,1,*, the \(M\)-partition problem asks whether or not an input graph \(G\) can be partitioned into \(m\) parts corresponding to the rows (and columns) of \(M\) so that two distinct vertices from parts \(i\) and \(j\) (possibly with \(i=j\)) are non-adjacent if \(M(i,j)=0\), and adjacent if \(M(i,j)=1\). These matrix partition problems generalize graph colourings and homomorphisms, and arise frequently in the study of perfect graphs; example problems include split graphs, clique and skew cutsets, homogeneous sets, and joins.
In this paper we study \(M\)-partitions restricted to perfect graphs. We identify a natural class of ‘normal’ matrices \(M\) for which \(M\)-partitionability of perfect graphs can be characterized by a finite family of forbidden induced subgraphs (and hence admits polynomial time algorithms for perfect graphs). We further classify normal matrices into two classes: for the first class, the size of the forbidden subgraphs is linear in the size of \(M\); for the second class we only prove exponential bounds on the size of forbidden subgraphs. (We exhibit normal matrices of the second class for which linear bounds do not hold.)
We present evidence that matrices \(M\) which are not normal yield badly behaved \(M\)-partition problems: there are polynomial time solvable \(M\)-partition problems that do not have finite forbidden subgraph characterizations for perfect graphs. There are \(M\)-partition problems that are NP-complete for perfect graphs. There are classes of matrices \(M\) for which even proving ‘dichotomy’ of the corresponding \(M\)-partition problems for perfect graphs – i.e., proving that these problems are all polynomial or NP-complete – is likely to be difficult.

MSC:

05C17 Perfect graphs
05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Les problemes de coloration en theorie des graphes, Publ. Inst. Statist. Univ. Paris, 9, 123-160 (1960) · Zbl 0103.16201
[2] A. Brandstadt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs, DIMACS TR 2002-44.; A. Brandstadt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs, DIMACS TR 2002-44.
[3] K. Cameron, E.M. Eschen, C.T. Hoang, R. Sritharan, The list partition problem for graphs, SODA 2004.; K. Cameron, E.M. Eschen, C.T. Hoang, R. Sritharan, The list partition problem for graphs, SODA 2004. · Zbl 1318.05072
[4] 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.
[5] Chvátal, V., Star-cutsets and perfect graphs, J. Combin. Theory, Ser. B, 39, 189-199 (1985) · Zbl 0674.05058
[6] 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
[7] T. Feder, P. Hell, On realizations of point determining graphs, and obstructions to full homomorphisms, manuscript.; T. Feder, P. Hell, On realizations of point determining graphs, and obstructions to full homomorphisms, manuscript. · Zbl 1135.05042
[8] T. Feder, P. Hell, Full constraint satisfaction problems, SIAM J. Comput. 36 (2006) 230-246.; T. Feder, P. Hell, Full constraint satisfaction problems, SIAM J. Comput. 36 (2006) 230-246. · Zbl 1111.68115
[9] T. Feder, P. Hell, S. Klein, R. Motwani, List partitions. SIAM J. Discrete Math. 16 (2003) 449-478.; T. Feder, P. Hell, S. Klein, R. Motwani, List partitions. SIAM J. Discrete Math. 16 (2003) 449-478. · Zbl 1029.05143
[10] T. Feder, P. Hell, S. Klein, L.T. Nogueira, F. Protti, List matrix partitions of chordal graphs, Theoret. Comput. Sci. 349 (2005) 52-66.; T. Feder, P. Hell, S. Klein, L.T. Nogueira, F. Protti, List matrix partitions of chordal graphs, Theoret. Comput. Sci. 349 (2005) 52-66. · Zbl 1084.05026
[11] Feder, T.; Vardi, M., The computational structure of monotone monadic SNP and constraint satisfactiona study through Datalog and group theory, SIAM J. Comput., 28, 236-250 (1998)
[12] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[13] Hell, P., Algorithmic aspects of graph homomorphisms, (Wensley, C. D., Surveys in Combinatorics, 2003, London Mathematical Society, Lecture Note Series, vol. 307 (2003), Cambridge University Press: Cambridge University Press Cambridge), 239-276 · Zbl 1035.05089
[14] 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
[15] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory, Ser. B, 48, 92-110 (1990) · Zbl 0639.05023
[16] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press: Oxford University Press Oxford · Zbl 1062.05139
[17] Ladner, R. E., On the structure of polynomial time reducibility, J. ACM, 22, 155-171 (1975) · Zbl 0322.68028
[18] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253-267 (1972) · Zbl 0239.05111
[19] McConnel, R. M.; Spinrad, J. P., Linear time modular decomposition and efficient transitive orientation of comparability graphs, (Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (1994)), 536-545 · Zbl 0867.05068
[20] Sumner, D., Point determination in graphs, Discrete Math., 5, 179-187 (1973) · Zbl 0265.05124
[21] Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039
[22] 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.