Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz |
| |
Authors: | Jesús A De Loera Jon Lee |
| |
Affiliation: | a Department of Mathematics, University of California, Davis, Davis, CA, United Statesb Industrial and Operations Engineering Department, University of Michigan, Ann Arbor, MI, United Statesc Computational and Applied Math Department, Rice University, Houston, TX, United States |
| |
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 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. |
| |
Keywords: | Combinatorics Systems of polynomials Feasibility Non-linear optimization Graph 3-coloring |
本文献已被 ScienceDirect 等数据库收录! |
|