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
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