  


Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
Jesus A. De Loera(deloeramath.ucdavis.edu) Abstract: Systems of polynomial equations over an algebraicallyclosed field K can be used to concisely model many 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 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 largescale linearalgebra computations over K. We report on experiments based on the problem of proving the non 3colorability 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  