Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

Jesus A. De Loera(deloeramath.ucdavis.edu)
Jon Lee(jonleeus.ibm.com)
Peter Malkin(malkinmath.ucdavis.edu)
Susan Margulies(smarguliesucdavis.edu)

Abstract: Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many 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 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 on large-scale linear-algebra computations over K. We report on experiments based on the problem of proving the non 3-colorability of graphs. We successfully solved graph problem instances having thousands of nodes and tens of thousands of edges.

Keywords: coloring, polynomial system, Nullstellensatz

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: IBM Research Report RC24472, January 2008

Download: [PDF]

Entry Submitted: 01/29/2008
Entry Accepted: 01/29/2008
Entry Last Modified: 01/29/2008

Modify/Update this entry