Systems of (non-linear) Polynomial Equations in Combinatorial Optimization

Part I: Non-linear encodings of combinatorial problems
Part II: Nullstellensätze and Positivstellensätze.

Jesus De Loera, University of California, Davis

Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a problem is feasible (e.g. a graph is 3-colorable, Hamiltonian, etc.) if and only if a certain system of equations has a solution. In the first part of this talk I explain new polynomial encodings for the problems of finding in a graph its longest cycle, the largest planar subgraph, the edge-chromatic number, or the largest k-colorable subgraph.

In the second part of the talk I will explain why these encodings are quite interesting. Briefly work of M. Laurent, J. Lasserre and P. Parrilo implies that when an optimization problem is modeled by a zero dimensional radical ideal it has a finite sequence of semidefinite programs that converge to the optimal solution. This is the case even for non-linear objective functions. A special case is that of feasibility questions, then we see that the problem can be approximated by a sequence of linear algebra problems. This follows from Hilbert's Nullstellensatz.

For an infeasible polynomial system, the (complex) Hilbert Nullstellensatz gives a certificate that the associated combinatorial problem is infeasible. Thus, unless P=NP, there must exist an infinite sequence of infeasible instances of each hard combinatorial problem for which the minimal degree of a Hilbert Nullstellensatz certificate of the associated polynomial system grows.

We show that the minimum-degree of a Hilbert Nullstellensatz certifying that there is no stable set of size larger than the stability number of the graph is the stability number of the graph. Moreover, such a certificate contains at least one term per stable set in G. In contrast, for 3-colorability, we found only families with Nullstellensatz of degree four.

This is joint work with S. Margulies (UC Davis) J. Lee (IBM Research), and S. Onn (Technion Haifa).

back to EIDMA Seminar Combinatorial Theory announcements