Semidefinite Programming Bounds on Fractional Cut-Cover and Maximum 2-SAT for Highly Regular Graphs

References

• [1] Austrin P (2007) Balanced max 2-sat might not be the hardest. STOC ‘07 Proc. 39th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 189–197.Google Scholar
• [2] Bachoc C, Gijswijt DC, Schrijver A, Vallentin F (2012) Invariant semidefinite programs. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer US, New York), 219–269.Crossref, Google Scholar
• [3] Bailey R (2004) Association Schemes: Designed Experiments, Algebra, and Combinatorics, Cambridge Studies in Advanced Mathematics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [4] Bannai E (1999) An introduction to association schemes. Löwe S, Mazzocca F, Melone N, Ott U, eds. Methods of Discrete Mathematics, Quaderni di Mathematica, vol. 5 (Seconda Università di Napoli, Naples, Italy), 1–70.Google Scholar
• [5] Biggs N (1993) Algebraic Graph Theory, Cambridge Mathematical Library (Cambridge University Press, Cambridge, UK).Google Scholar
• [6] Brakensiek J, Huang N, Zwick U (2023) Tight approximability of MAX 2-SAT and relatives, under UGC. Preprint, submitted October 19, https://arxiv.org/abs/2310.12911.Google Scholar
• [7] Brouwer A, Cohen A, Neumaier A (2011) Distance-Regular Graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge/A Series of Modern Surveys in Mathematics (Springer, Berlin).Google Scholar
• [8] Cameron PJ (2003) Coherent configurations, association schemes and permutation groups. Ivanov AA, Liebeck MW, Saxl J, eds. Groups, Combinatorics and Geometry: Durham 2001 (World Scientific, Singapore), 55–71.Crossref, Google Scholar
• [9] Cohen N, Pasechnik DV (2016) Implementing Brouwer’s database of strongly regular graphs. Designs Codes Cryptography 84(1–2):223–235.Crossref, Google Scholar
• [10] Dalfó C, Fiol MA, Garriga E (2009) On k-walk-regular graphs. Electronic J. Combin. 16(1):R47.Crossref, Google Scholar
• [11] de Carli Silva MK, Coutinho G, Godsil C, Roberson DE (2019) Algebras, graphs and thetas. Electronic Notes Theoret. Comput. Sci. 346:275–283.Crossref, Google Scholar
• [12] de Klerk E, Dobre C, Pasechnik DV (2011) Numerical block diagonalization of matrix *-algebras with application to semidefinite programming. Math. Programming 129(1):91–111.Crossref, Google Scholar
• [13] Delsarte P (1973) An Algebraic Approach to the Association Schemes of Coding Theory. Philips Journal of Research/Supplement (N.V. Philips’ Gloeilampenfabrieken, Eindhoven, Netherlands).Google Scholar
• [14] Fulkerson DR (1971) Blocking and anti-blocking pairs of polyhedra. Math. Programming 1(1):168–194.Crossref, Google Scholar
• [15] Garey MR, Johnson DS, Stockmeyer L (1974) Some simplified NP-complete problems. STOC ‘74 Proc. 6th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 47–63.Google Scholar
• [16] Godsil C, McKay B (1980) Feasibility conditions for the existence of walk-regular graphs. Linear Algebra Appl. 30:51–61.Crossref, Google Scholar
• [17] Goemans MX, Rendl F (1999) Semidefinite programs and association schemes. Computing 63(4):331–340.Crossref, Google Scholar
• [18] Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• [19] Higman DG (1975) Coherent configurations. Geometriae Dedicata 4:1–32.Crossref, Google Scholar
• [20] Ho T-Y, Hsu L-H (1994) A note on the minimum cut cover of graphs. Oper. Res. Lett. 15(4):193–194.Crossref, Google Scholar
• [21] Lewin M, Livnat D, Zwick U (2002) Improved rounding techniques for the max 2-sat and max di-cut problems. Cook WJ, Schulz AS, eds. Integer Programming and Combinatorial Optimization (Springer, Berlin), 67–82.Crossref, Google Scholar
• [22] Loulou R (1992) Minimal cut cover of a graph with an application to the testing of electronic boards. Oper. Res. Lett. 12(5):301–305.Crossref, Google Scholar
• [23] Motwani R, Naor JS (1994) On exact and approximate cut covers of graphs. Technical report, Stanford University, Stanford, CA.Google Scholar
• [24] Neto J, Ben-Ameur W (2019) On fractional cut covers. Discrete Appl. Math. 265:168–181.Crossref, Google Scholar
• [25] Proença NB, de Carli Silva MK, Coutinho G (2021) Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming. SIAM J. Discrete Math. 35(4):2880–2907.Crossref, Google Scholar
• [26] Proença NB, de Carli Silva MK, Sato CM, Tunçel L (2025) A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem: Primal-dual Goemans-Williamson for weighted fractional cut covers. Math. Programming 215(1–2):1–56.Crossref, Google Scholar
• [27] Rockafellar RT (1997) Convex Analysis (Princeton University Press, Princeton, NJ).Google Scholar
• [28] Rowlinson P (1997) Linear algebra. Beineke LW, Wilson RJ, eds. Graph Connections: Relationships between Graph Theory and Other Areas of Mathematics (Oxford University Press, Oxford, UK), 86–99.Crossref, Google Scholar
• [29] Šámal R (2005) Fractional covering by cuts. Electronic Notes Discrete Math. 22:455–459.Crossref, Google Scholar
• [30] The Sage Developers (2022) SageMath, the sage mathematics software system (version 9.5), https://www.sagemath.org.Google Scholar
• [31] van Dam ER, Sotirov R (2014) Semidefinite programming and eigenvalue bounds for the graph partition problem. Math. Programming 151(2):379–404.Crossref, Google Scholar