Seperating Spanning Tree inequalities and equivalence to rank function of the cycle matroid

Question

The motivation of this post is to answer the question

How can I decide for a given graph $G = (V,E)$ and $x \in \mathbb{R}^E$ whether $\sum_{e \in E[X]}x_e \leq |X| -1$ for all non-empty $X \subseteq V$ (where $E[X]$ denotes the subset of edges that lie completely inside of $X$).

In my lecture, we proved the following results

• For a given graph $G=(V,E)$ the spanning tree polytope, i.e. convex hull of all incidence vectors $x \in \mathbb{R}^E$ of spanning trees, is given by the set $$ P=\{x \in [0,1]^E \mid \sum_{e \in E} x_e = n-1, \quad \sum_{e \in E[X]} x_e \leq |X| - 1 \ \forall X \subseteq V, X \neq \emptyset\}. $$

• There is a polynomial time algorithm that minimizes a submodular function $f:2^S \to \mathbb{R}$.

Now, in order to solve LPs over the polytope above, one would like to be able to seperate these inequalities. I gave this a thought and came up with the following:

Lemma. Let $G =(V,E)$ be a graph and $x \in \mathbb{R}^E_+ $. Then there is some non-empty $X \subseteq V$ such that $\sum_{e \in E[X]}x_e > |X| -1$ if and only if there is some $A \subseteq E$ such that $\sum_{e \in A} x_e > r(A)$ where $r$ denotes the rank function of the cycle matroid of $G$.

Proof. Assume that there is such a set $X$. Set $A := E[X]$. Then $$ \sum_{e \in A} x_e = \sum_{e \in E[X]} x_e > |X| - 1 \geq r(A). $$

Now suppose that there is such a set $A$. Let $A_1 , \dots , A_k \subseteq A$ be the edge sets of the connected components of $(V,A)$. Since $r(A) = r(A_1) + \dots + r(A_k)$, there is some $i \in \{1 , \dots , k \}$ such that $\sum_{e \in A_i} x_e > r(A_i)$. So assume w.l.o.g. that $A = A_i$. Set $X$ to be the set of endpoints of edges in $A$. In particular, $r(A) = |X| - 1$ (by connectivity of $A$). Using that all entries of $x$ are non-negative, we have $$ \sum_{e \in E[X]} x_e \geq \sum_{e \in A} x_e > r(A) = |X| - 1 $$ finishing the proof.

Note that by this lemma it therefore suffices to check whether there is some $A \subseteq E$ with $\sum_{e \in A} x_e > r(A)$. This can be done as the function $r(A) - \sum_{e \in A} x_e $ is submodular and hence we only need to minimize this (in poly. time).

My questions regarding this are the following:

1. Is the lemma and its proof above correct?
2. Is there an easier way to seperate these inequalities? I feel like reducing this to submodular function minimization seems a bit like an overload to me. I believe there should be an easier reduction to some other problem.

Answer 1

1. Your proof is perfectly fine! What you have shown is that the polytope of spanning trees is also described (using more concise notation) by $$P' = \{x \in [0,1]^E \, \, | \, \, x(E) = n-1, \, \, \,x(A) \leq r(A) \, \, \, \forall \varnothing \neq A \subseteq E \}.$$ This is just a special case of a much more general phenomenon: for any matroid, the polytope defined by the bases of the matroid has a similar description. (Moreover, this description is, in a sense, very nice: it is totally dually integral.)
2. There is nothing wrong with your solution using submodular function minimization. The nice thing about this approach is that it works just as well for an arbitrary matroid. But in this particular case there is indeed a short but tricky reduction to a linear number of network flow problems, which you can find here. Note that this approach uses your original description of the polytope.