The Strongest Facets of the Acyclic Subgraph Polytope are Unknown
(Extended Abstract)
Michel X. Goemans and
Leslie A. Hall
Abstract
We consider the acyclic subgraph polytope and define the notion of
strength of a relaxation as the maximum improvement obtained by
using this relaxation instead of the most trivial relaxation of the
problem. We show that the strength of a relaxation is simply the
maximum of the strengths of the relaxations obtained by simply
adding to the trivial ality separately. We derive from the
probabilistic method that the maximum strength of any inequality
is 2. We also consider all (or almost all) the known valid
inequalities for the polytope and compute their strength. The
surprising observation is that their strength is at most slightly
more than 3/2, implying that the strongest inequalities are yet
unknown. We then consider a pseudo-random construction due to
Alon and Spencer based on quadratic residues to obtain new
facet-defining inequalities for the polytope. These are also
facet-defining for the linear ordering polytope.
A full version of this extended abstract is in preparation. If
you are interested in seeing it once it is complete, please send
email to lah@jhu.edu.