Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares

DOI10.1016/J.JSC.2021.01.003zbMATH Open1465.05128arXiv2003.04021OpenAlexW3010147380WikidataQ113869824 ScholiaQ113869824MaRDI QIDQ2029005FDOQ2029005

Authors: Elisabeth Gaar, Daniel Krenn, Susan Margulies, Angelika Wiegele 

Publication date: 3 June 2021

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Vizing's conjecture (open since 1968) relates the product of the domination numbers of two graphs to the domination number of their Cartesian product graph. In this paper, we formulate Vizing's conjecture as a Positivstellensatz existence question. In particular, we select classes of graphs according to their number of vertices and their domination number and encode the conjecture as an ideal/polynomial pair such that the polynomial is non-negative on the variety associated with the ideal if and only if the conjecture is true for this graph class. Using semidefinite programming we obtain numeric sum-of-squares certificates, which we then manage to transform into symbolic certificates confirming non-negativity of our polynomials. Specifically, we obtain exact low-degree sparse sum-of-squares certificates for particular classes of graphs. The obtained certificates allow generalizations for larger graph classes. Besides computational verification of these more general certificates, we also present theoretical proofs as well as conjectures and questions for further investigations.

Full work available at URL: https://arxiv.org/abs/2003.04021

Recommendations

• An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture
• Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases
• scientific article
• scientific article; zbMATH DE number 2197881
• Vizing's conjecture for graphs with domination number 3 -- a new proof

zbMATH Keywords

semidefinite programming[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+basis&go=Go Gr��bner basis]Vizing's conjecturealgebraic modelsum-of-squares problems

Mathematics Subject Classification ID

Semidefinite programming (90C22) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Title not available (Why is that?)
• Semidefinite Programming
• Title not available (Why is that?)
• Stable sets and polynomials
• Sums of squares, moment matrices and optimization over polynomials
• Semidefinite Optimization and Convex Algebraic Geometry
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial interpolation in several variables
• Colorings and orientations of graphs
• Vizing's conjecture: a survey and recent results
• Theta bodies for polynomial ideals
• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Control Applications of Sum of Squares Programming
• An improved bound in Vizing's conjecture
• An algebraic exploration of dominating sets and Vizing's conjecture
• Title not available (Why is that?)
• Algebraic characterization of uniquely vertex colorable graphs
• Nowhere-zero flow polynomials
• A result on Vizing's conjecture
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Complexity of Null- and Positivstellensatz proofs
• Symmetric polynomials and Hall's theorem
• Quantum entanglement, sum of squares, and the log rank conjecture
• An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture

Cited In (7)

• The 2-domination number of cylindrical graphs
• Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
• Sum-of-squares certificates for Vizing's conjecture via determining Gröbner bases
• High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
• An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture

Uses Software

• Mosek

This page was built for publication: Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029005)