Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleComputing infeasibility certificates for combinatorial problems through Hilbertís Nullstellensatz
Author(s) Jesús A., Jon Lee, Peter N. Malkin, S. Margulies
TypeArticle in Journal
AbstractSystems of polynomial equations with coefficients over a field K can be used to concisely model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over the algebraic closure of the field K . In this paper, we investigate an algorithm aimed at proving combinatorial infeasibility based on the observed low degree of Hilbertís Nullstellensatz certificates for polynomial systems arising in combinatorics, and based on fast large-scale linear-algebra computations over K . We also describe several mathematical ideas for optimizing our algorithm, such as using alternative forms of the Nullstellensatz for computation, adding carefully constructed polynomials to our system, branching and exploiting symmetry. We report on experiments based on the problem of proving the non-3-colorability of graphs. We successfully solved graph instances with almost two thousand nodes and tens of thousands of edges.
KeywordsCombinatorics, Systems of polynomials, Feasibility, Non-linear optimization, Graph 3-coloring
URL http://www.sciencedirect.com/science/article/pii/S0747717111001192
JournalJournal of Symbolic Computation
Pages1260 - 1283
Translation No
Refereed No