Optimization Online


Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

Jesus A. De Loera(deloera***at***math.ucdavis.edu)
Jon Lee(jonlee***at***us.ibm.com)
Peter Malkin(malkin***at***math.ucdavis.edu)
Susan Margulies(smargulies***at***ucdavis.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society