Odd cycle transversal and linear programming

Question

Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ we add to LP the constraint $x_a+x_b+x_c+\dots +x_i≥1$ where $x_a,x_b,x_c,...,x_i$ are the vertices of the cycle. The objective function of LP is $\min \sum\limits_{1}^{n}{x_i}$.

Suppose $S$ is an optimal solution of LP. If a variable $x_v$ takes on a value $>0$ in $S$, is it guaranteed that there exists a minimum odd cycle transversal that contains $v$? By minimum odd cycle transversal, I mean an odd cycle transversal with the fewest number of vertices.

Answer 1

No, $v$ does not have to belong to any minimum odd cycle transversal.

Consider the following undirected graph. The vertices are split into eight groups: $C_i$ for $i \in [0, 3]$, each of them containing $4$ vertices and $F_i$ for $i \in [0, 3]$, each containing $3$ vertices. The following edges (and only them) are present in the graph:

1. All edges between $C_i$ and $C_{(i + 1) \bmod 4}$ for every $i \in [0, 3]$
2. All edges between $C_i$ and $F_i$ for every $i \in [0, 3]$
3. All edges between $F_0$ and $F_2$, all edges between $F_1$ and $F_3$

Let's prove the following statements:

1. Any OCT that contains a vertex from one of the $C_i$'s has size at least $7$, but there are OCT's of size $6$ (for example, $F_0 \cup F_1$).
2. In any optimal solution to the LP relaxation, the variables corresponding to vertices from $F_i$'s are set to zero. Moreover, there is only one optimal solution to the LP relaxation: set all variables corresponding to vertices of $C_i$ to $1/3$.

If both are true, then, for every nonzero variable in the optimal solution to the LP, there is no minimal OCT that passes through the corresponding vertex. Because the graph is small enough, you can verify both these statements on a computer. But I will give a short "human" proof to both.

For the minimum OCT part, it is clear that we should either delete each of the vertex group either fully, or not touch it at all (because just a single vertex from the group is "good enough representative" for the whole group). Moreover, we can see that deleting one $C_i$ group is not enough. If we delete, say, the group $C_0$, there is still an odd cyle $F_1 \to C_1 \to C_2 \to C_3 \to F_3 \to F_1$. Hence, we still have to delete at least one other group, for $7$ vertices in total. On the other hand, $F_0 \cup F_1$ is an OCT with size $6$.

Now let's deal with LP part. It can be seen that all odd cycles in the graph pass through at least $3$ vertices from $C_i$. Hence, assigning weight $1/3$ to each vertex of each $C_i$ yields a solution with total cost $16/3$. On the other hand, consider all cycles of length $5$ in our graph. It can be proven that all vertices from $C_i$'s lie on exactly $3/16$ fraction of them, but all vertices from $F_i$'s lie on exactly $1/6$ fraction of them (the proof is a bit tedious to write down, so I will add it only by request). Then, by averaging the inequalities $x_a + x_b + \ldots + x_\ell \geqslant 1$ over all these cycles, we get $\frac{1}{6} \sum\limits_{v \in \bigcup F_i} x_v + \frac{3}{16} \sum\limits_{v \in \bigcup C_i} x_v \geqslant 1$, implying $\sum\limits_{v \in V} x_v \geqslant \frac{16}{18} \sum\limits_{v \in \bigcup F_i} x_v + \sum\limits_{v \in \bigcup C_i} x_v = \frac{16}{3} \left(\frac{1}{6} \sum\limits_{v \in \bigcup F_i} x_v + \frac{3}{16} \sum\limits_{v \in \bigcup C_i} x_v \right) \geqslant \frac{16}{3}$. Moreover, the inequality is strict if some $x_v$ with $v \in F_i$ is not zero. Hence, in each optimal LP solution, non-zero weights are assigned only to vertices from $C_i$'s. Moreover, it is possible to prove that there is only one optimal solution, with all weights of $C_i$'s set $1/3$. It is not too important, though, because we already proved that all optimal LP solutions are pairwise disjoint from all optimal OCT's.

Answer 2

Wouldn't that imply one could solve odd cycle transversal simply by solving the LP finding a positive vertex removing it from the graph and repeating?