Details:
Title  Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz  Author(s)  Jesús A., Jon Lee, Peter N. Malkin, S. Margulies  Type  Article in Journal  Abstract  Systems 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 3colorable, 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 largescale linearalgebra 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 non3colorability of graphs. We successfully solved graph instances with almost two thousand nodes and tens of thousands of edges.  Keywords  Combinatorics, Systems of polynomials, Feasibility, Nonlinear optimization, Graph 3coloring  ISSN  07477171 
URL 
http://www.sciencedirect.com/science/article/pii/S0747717111001192 
Language  English  Journal  Journal of Symbolic Computation  Volume  46  Number  11  Pages  1260  1283  Year  2011  Edition  0  Translation 
No  Refereed 
No 
