Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares
From MaRDI portal
(Redirected from Publication:2029005)
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.
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; zbMATH DE number 140092
- scientific article; zbMATH DE number 2197881
- Vizing's conjecture for graphs with domination number 3 -- a new proof
Cites work
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1124600 (Why is no real title available?)
- scientific article; zbMATH DE number 1515218 (Why is no real title available?)
- scientific article; zbMATH DE number 3284071 (Why is no real title available?)
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A result on Vizing's conjecture
- Algebraic characterization of uniquely vertex colorable graphs
- An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture
- An algebraic exploration of dominating sets and Vizing's conjecture
- An improved bound in Vizing's conjecture
- Colorings and orientations of graphs
- Complexity of Null- and Positivstellensatz proofs
- Control Applications of Sum of Squares Programming
- Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
- Handbook of semidefinite programming. Theory, algorithms, and applications
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Nowhere-zero flow polynomials
- Polynomial interpolation in several variables
- Quantum entanglement, sum of squares, and the log rank conjecture
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite Programming
- Stable sets and polynomials
- Sums of squares, moment matrices and optimization over polynomials
- Symmetric polynomials and Hall's theorem
- Theta bodies for polynomial ideals
- Vizing's conjecture: a survey and recent results
Cited in
(8)- An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture
- The 2-domination number of cylindrical graphs
- An algebraic exploration of dominating sets and Vizing's conjecture
- High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts
- 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
- Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
- High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
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)
