×

A new graph parameter related to bounded rank positive semidefinite matrix completions. (English) Zbl 1293.05238

Summary: The Gram dimension \(\mathrm{gd}(G)\) of a graph \(G\) is the smallest integer \(k\geq 1\) such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of \(G\), can be completed to a positive semidefinite matrix of rank at most \(k\) (assuming a positive semidefinite completion exists). For any fixed \(k\) the class of graphs satisfying \(\mathrm{gd}(G) \leq k\) is minor closed, hence it can be characterized by a finite list of forbidden minors.
We show that the only minimal forbidden minor is \(K_{k+1}\) for \(k\leq 3\) and that there are two minimal forbidden minors: \(K_5\) and \(K_{2,2,2}\) for \(k=4\). We also show some close connections to Euclidean realizations of graphs and to the graph parameter \(\nu^=(G)\) of H. van der Holst [Combinatorica 23, No. 4, 633–651 (2003; Zbl 1056.05130)]. In particular, our characterization of the graphs with \(\mathrm{gd}(G)\leq 4\) implies the forbidden minor characterization of the 3-realizable graphs of M. Belk [Discrete Comput. Geom. 37, No. 2, 139–162 (2007; Zbl 1114.05066)] and M. Belk and R. Connelly [ibid. 37, No. 2, 125–137 (2007; Zbl 1114.05067)] and of the graphs with \(\nu ^=(G) \leq 4\) of van der Holst [loc. cit.].

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C83 Graph minors
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A83 Matrix completion problems
90C22 Semidefinite programming

Software:

Max-AO
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alfakih, A.Y., Anjos, M.F., Picciali, V., Wolkowicz, H.: Euclidean distance matrices, semidefinite programming and sensor network localization. Portugaliae Mathematica 68(1), 53-102 (2011) · Zbl 1223.51017 · doi:10.4171/PM/1881
[2] Alfakih, A.Y., Khandani, A., Wolkowicz, H.: Solving Euclidean distance matrix completion problems via semidefinite programming. Comput. Optim. Appl. 12, 13-30 (1999) · Zbl 1040.90537
[3] Arnborg, S., Proskurowski, A., Corneil, D.G.: Forbidden minors characterization of partial 3-trees. Discret. Math. 8(1), 1-19 (1990) · Zbl 0701.05016 · doi:10.1016/0012-365X(90)90292-P
[4] Avidor, A., Zwick, U.: Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT. In: Chekuri C. et al. (eds.) APPROX and RANDOM 2005, LNCS 3624, pp. 14-25 (2005) · Zbl 1122.90396
[5] Barahona, F.: The max-cut problem on graphs not contractible to \(K_5\). Oper. Res. Lett. 2(3), 107-111 (1983) · Zbl 0525.90094 · doi:10.1016/0167-6377(83)90016-0
[6] Barrett, W.W., Johnson, C.R., Tarazaga, P.: The real positive definite completion problem: cycle completability. Mem. Am. Math. Soc. 584, 69 (1996) · Zbl 0786.15027
[7] Barvinok, A.: A remark on the rank of positive semidefinite matrices subject to affine constraints. Discret. Comput. Geom. 25(1), 23-31 (2001) · Zbl 0969.90096 · doi:10.1007/s004540010074
[8] Belk, M.: Realizability of graphs in three dimensions. Discret. Comput. Geom. 37, 139-162 (2007) · Zbl 1114.05066 · doi:10.1007/s00454-006-1285-4
[9] Belk, M., Connelly, R.: Realizability of graphs. Discret. Comput. Geom. 37, 125-137 (2007) · Zbl 1114.05067 · doi:10.1007/s00454-006-1284-5
[10] Burer, S., Monteiro, R.D.C., Zhang, Y.: Maximum stable sets formulations and heuristics based on continuous optimization. Math. Program. 94, 137-166 (2002) · Zbl 1023.90071 · doi:10.1007/s10107-002-0356-4
[11] Colin de Verdière, Y.: Multiplicities of eigenvalues and tree-width of graphs. J. Comb. Theory Ser. B 74(2), 121-146 (1998) · Zbl 1027.05064 · doi:10.1006/jctb.1998.1834
[12] de Klerk, E.: Aspects of Semidefinite Programming - Interior Point Algorithms and Selected Applications. Kluwer, Dordrecht (2002) · Zbl 0991.90098
[13] Deza, M., Laurent, M.: Geometry of Cuts and Metrics. Springer, Berlin (1997) · Zbl 0885.52001 · doi:10.1007/978-3-642-04295-9
[14] Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10(2), 303-313 (1965) · Zbl 0128.37002 · doi:10.1016/0022-247X(65)90125-3
[15] Eisenberg-Nagy, M., Laurent, M., Varvitsiotis, A.: Complexity of the positive semidefinite matrix completion problem with a rank constraint. (2012, Preprint). Available at: arXiv:1203.6602v2 · Zbl 1272.68140
[16] Fallat, S.M., Hogben, L.: The minimum rank of symmetric matrices described by a graph: a survey. Linear Algebra Appl. 426, 558-582 (2007) · Zbl 1122.05057 · doi:10.1016/j.laa.2007.05.036
[17] Fallat, S.M., Hogben, L.: Variants on the minimum rank problem: a survey II. Preprint. Available at: arXiv:1102.5142v1 (2011) · Zbl 1122.05057
[18] Göring, F., Helmberg, C., Wappler, M.: Embedded in the shadow of the separator. SIAM J. Optim. 19(1), 472-501 (2008) · Zbl 1169.05347 · doi:10.1137/050639430
[19] Göring, F., Helmberg, C., Wappler, M.: The rotational dimension of a graph. J. Graph Theory 66(4), 283-302 (2011) · Zbl 1213.05167 · doi:10.1002/jgt.20502
[20] Göring, F., Helmberg, C., Reiss, S.: Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian. Math. Program. 131(1-2), 95-111 (2012) · Zbl 1232.05124 · doi:10.1007/s10107-010-0344-z
[21] Grone, R., Johnson, C.R., Sá, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebra Appl. 58, 109-124 (1984) · Zbl 0547.15011 · doi:10.1016/0024-3795(84)90207-6
[22] Hogben, L.: Orthogonal representations, minimum rank, and graph complements. Linear Algebra Appl. 428, 2560-2568 (2008) · Zbl 1147.05049 · doi:10.1016/j.laa.2007.12.004
[23] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
[24] Krislock, N.; Wolkowicz, H.; Anjos, MF (ed.); Lasserre, JB (ed.), Euclidean distance matrices and applications, 879-914 (2012), Berlin · Zbl 1334.90109 · doi:10.1007/978-1-4614-0769-0_30
[25] Laurent, M.: The real positive semidefinite completion problem for series parallel graphs. Linear Algebra Appl. 252, 347-366 (1997) · Zbl 0871.05043 · doi:10.1016/0024-3795(95)00741-5
[26] Laurent, M.; Floudas, CA (ed.); Pardalos, PM (ed.), Matrix completion problems, No. III, 221-229 (2001), Dordrecht
[27] Laurent, M.: Polynomial instances of the positive semidefinite and euclidean distance matrix completion problems. SIAM J. Matrix Anal. Appl. 22, 874-894 (2000) · Zbl 0981.05071 · doi:10.1137/S0895479899352689
[28] Laurent, M., Varvitsiotis, A.: The Gram dimension of a graph. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization, LNCS 7422, pp. 356-367 (2012) · Zbl 1370.05196
[29] Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT-25, 1-7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[30] Lovász, L., Vesztergombi, K.: Geometric representations of graphs. In: Halász, G., et al. (eds.) Paul Erdös and his Mathematics, pp. 471-498. Bolyai Society Mathematical Studies (2002) · Zbl 1031.05090
[31] Man-Cho So, A.: A semidefinite programming approach to the graph realization problem. PhD thesis, University of Stanford (2007) · Zbl 1169.05347
[32] Man-Cho So, A., Ye, Y.: A semidefinite programming approach to tensegrity theory and realizability of graphs. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 766-775. (2006) · Zbl 1192.90137
[33] Nie, J.: Sum of squares method for sensor network localization. Comput. Optim. Appl. 43(2), 151-179 (2009) · Zbl 1170.90510 · doi:10.1007/s10589-007-9131-z
[34] Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471-501 (2010) · Zbl 1198.90321 · doi:10.1137/070697835
[35] Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner’s conjecture. J. Comb. Theory Ser. B 92(2), 325-357 (2004) · Zbl 1061.05088 · doi:10.1016/j.jctb.2004.08.001
[36] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[37] van der Holst, H.: Topological and Spectral Graph Characterizations. Ph.D. thesis, University of Amsterdam (1996) · Zbl 0701.05016
[38] van der Holst, H.: Two tree-width-like graph Invariants. Combinatorica 23(4), 633-651 (2003) · Zbl 1056.05130 · doi:10.1007/s00493-003-0038-8
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.