JGD_Margulies/wheel_601
Combinatorial optimization as polynomial eqns, Susan Margulies, UC Davis
Name 
wheel_601 
Group 
JGD_Margulies 
Matrix ID 
2169 
Num Rows

902,103 
Num Cols

723,605 
Nonzeros

2,170,814 
Pattern Entries

2,170,814 
Kind

Combinatorial Problem 
Symmetric

No 
Date

2008 
Author

S. Margulies 
Editor

J.G. Dumas 
Structural Rank 
723,005 
Structural Rank Full 
false 
Num Dmperm Blocks

604 
Strongly Connect Components

1 
Num Explicit Zeros

0 
Pattern Symmetry

0% 
Numeric Symmetry

0% 
Cholesky Candidate

no 
Positive Definite

no 
Type

binary 
Download 
MATLAB
Rutherford Boeing
Matrix Market

Notes 
Combinatorial optimization as polynomial eqns, Susan Margulies, UC Davis
From JeanGuillaume Dumas' Sparse Integer Matrix Collection,
http://ljk.imag.fr/membres/JeanGuillaume.Dumas/simc.html
http://arxiv.org/abs/0706.0578
Expressing Combinatorial Optimization Problems by Systems of Polynomial
Equations and the Nullstellensatz
Authors: J.A. De Loera, J. Lee, Susan Margulies, S. Onn
(Submitted on 5 Jun 2007)
Abstract: Systems of polynomial equations over the complex or real
numbers can be used to model 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. In the first part of this paper, we construct
new polynomial encodings for the problems of finding in a graph its
longest cycle, the largest planar subgraph, the edgechromatic number,
or the largest kcolorable subgraph. 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 minimum degree of a
Hilbert Nullstellensatz certificate of the associated polynomial system
grows. We show that the minimumdegree of a Nullstellensatz
certificate for the nonexistence of a stable set of size greater 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
of G. In contrast, for non3 colorability, we found only graphs with
Nullstellensatz certificates of degree four.
Filename in JGD collection: Margulies/wheel_601.sms
