Primal-dual inequalities for the approximate maximum-cut value of graphs in homogeneous coherent configurations
Palavras-chave:
Graphs, Maximum-cut, Primal-dual inequalities, Coherent configurationsResumo
Let G be a simple undirected graph with vertex set V and edge set E. We say that a subset K of V is a clique if its induced subgraph is a complete graph on |K| vertices, and similarly we say that a subset C of V is a coclique if its induced subgraph has no edges. Denote by ω(G) and α(G) the size of the largest clique and the largest coclique of G, respectively. In general, computing these two parameters for a given graph is NP-hard, and there doesn’t seem to be any correlation between the existence of large cliques and the nonexistence of large cocliques for an arbitrary graph, and vice-versa. However, for graphs with enough structural regularity, one can find a strong relationship between such parameters, known as the clique-coclique inequality. In this work, we seek to study ways of generalizing such inequality for primal-dual formulations of problems related to the maximum-cut of highly regular graphs.
Downloads
Referências
C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin. “Invariant Semidefinite Programs”. In: Handbook on Semidefinite, Conic and Polynomial Optimization. Ed. by M. F. Anjos and J. B. Lasserre. New York, NY: Springer US, 2012, pp. 219–269. doi: 10.1007/978-1-4614-0769-0_9.
M. K. de Carli Silva, G. Coutinho, C. Godsil, and D. E. Roberson. “Algebras, Graphs and Thetas”. In: Electronic Notes in Theoretical Computer Science 346 (2019). The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019), pp. 275–283. doi: 10.1016/j.entcs.2019.08.025.
C. Godsil and K. Meagher. Erdos-Ko-Rado Theorems: Algebraic Approaches. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2015. doi: 10.1017/CBO9781316414958.
M. X. Goemans and D. P. Williamson. “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”. In: J. ACM 42.6 (Nov. 1995), pp. 1115–1145. doi: 10.1145/227683.227684.
D. G. Higman. “Coherent algebras”. In: Linear Algebra and its Applications 93 (1987), pp. 209–239. doi: 10.1016/S0024-3795(87)90326-0.
D. G. Higman. “Coherent configurations”. In: Geometriae Dedicata 4.1 (May 1975), pp. 1–32. doi: 10.1007/BF00147398.
S. Lang. Algebra. New York, NY: Springer, 2002. doi: 10.1007/978-1-4613-0041-0.
L. Lovasz. “On the Shannon capacity of a graph”. In: IEEE Transactions on Information Theory 25.1 (1979), pp. 1–7. doi: 10.1109/TIT.1979.1055985.
N. B. Proença, M. K. de Carli Silva, C. M. Sato, and L. Tunçel. A Primal-Dual Extension of the Goemans–Williamson Algorithm for the Weighted Fractional Cut-Covering Problem. 2023. arXiv: 2311.15346 [math.OC].
