User sergey - MathOverflow

Answer by Sergey for Maximal clique intersection graphs

2011-02-10T10:25:51Z

Hi,

It is not an answer, just a comment. This site may be relevant: http://www.eprisner.de/Journey/CliqueGraphs.html

Everything changes drastically if you manage to use not clique intersection but clique incidence matrix in your decomposition. Then you immediately fall into the realm of perfect graphs.

The rows of clique-incidence matrix $A$ of a graph $G$ are incidence vectors of (maximal) cliques and vertices. For perfect graphs (that are graphs not containing induced odd cycles of the length greater than three or their complement) these matrices have several nice properties with respect to packing and covering the vertices by the subsets --- maximal cliques. Formally, the polytope ${x : Ax\leq e, x\geq 0}$ ($e$ is a vector of all $1$') is integral iff $G$ is perfect. In particular, a lot of NP-hard in general problems (e.g. chromatic number) are polynomial for perfect graphs. But coumting is a more subtle matter.

Answer by Sergey for How to prove that a set of facets are all the facets of a convex polytope.

2011-01-21T13:06:37Z

Hi,

The question itself and all answers seem to be "practice-oriented" but as far as the complexity status of the problem is concerned then you are speaking about famous L.Lovasz's "polytope- polyhedron question". Namely, to check whether a polytope given by vertices coincides with a polyhedron given by facets. Note, that the lengths of the vertex and, respectively, the facet descriptions may differ exponentially and thus we should speak about incremental polynomial algorithms. Say, if a polyhedron is given by facets you should find a new vertex in polynomial time with respect to the input and the length of the list of already calculated vertices. In this format the question is still open for (bounded) polytopes but is proved to be NP-hard for (unbounded) polyhedrons (see, http://portal.acm.org/citation.cfm?id=1109640 and references therein)

Answer by Sergey for Condition number for Ellipsoid method matrix

2010-11-07T15:52:09Z

Hi,

As far as I understand your question, a partial answer may be recovered from the Khachiyan's original covergence proof of the ellipsoid algorithm. Namely, Khachiyan used the volume as an intermadiate parameter and expressed it via, what he called, the thickness $r(E)$ that is equal to $\lambda_{min}$ of the current ellipsoid $E$. The following inequality holds $r(E_{next})\geq \frac{d}{d+1} r(E_{previous})$. And $\lambda_{max}$ can be upperbounded by the inequality $\lambda_{max-next}\leq 2^{\frac1{d^2}}\lambda_{max-previous}$. Thus, the condition number increases not faster than $[\frac{d}{d+1} 2^{\frac1{d^2}}]^n$. It seems that you can check this exponential rate in your toy example (just consider the plane case $d=2$ to simplify the computations). By the way, precisely the fact that the ellipsoid algorithm USUALLY operates according to the theoretical estimates is a main reason for claims of it's ``practical'' impracticallity. But it's another story.

Sergey