6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This should be false, because it would, according to Hao S's answer below, yield a polynomial algorithm for OCT, assuming that we can solve the LP somehow. The LP subproblem does have an exponential number of constraints, but there are methods to solve LP's like that, if a so called separation oracle exists (see more here: cs.princeton.edu/~smattw/Teaching/521fa17lec15.pdf or search by "linear programming", "separation oracle" keywords). For odd cycle transversal a polynomial-time separation oracle is known, hence a counterexample to your statement should be known. $\endgroup$ – Kaban-5 Aug 3 '20 at 19:07
  • $\begingroup$ A polynomial-time separation oracle is mentioned in the section 3.1 of this paper: arxiv.org/abs/1702.06969 . The linked paper considers an edge-version of odd cycle transversal (but with different edges having different costs), but I think that you can reduce the vertex version to the edge vertex by carefully splitting each vertex into three. $\endgroup$ – Kaban-5 Aug 3 '20 at 19:12
  • $\begingroup$ The paper arxiv.org/abs/1702.06969 in 3.1 says that it is possible solve MinUncut in polynomial time. Because MinUncut is NP-hard, this means that P=NP (if the paper is right!!). $\endgroup$ – Mario Giambarioli Aug 4 '20 at 2:26
  • $\begingroup$ I don't think it does. As far as I undersand, the section 3.1 says that it is possible to solve linear relaxation (take the natural integer linear program for the problem and replace it with a real linear programming by removing requirement that all variables should be integers) of MInUncut in polynomial time. Then, they use the exact solution of the relaxed problem to obtain an approximate solution of the original problem and prove some results about the quality of approximation. $\endgroup$ – Kaban-5 Aug 4 '20 at 12:19
  • $\begingroup$ I think that I found an explicit counterexample to your conjecture, I will post it as an answer in a short time. $\endgroup$ – Kaban-5 Aug 4 '20 at 12:20
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Kaban-5, I am sorry, but $F_0\cup F_1$ is not a OCT, in fact, for example, we have the odd cycle $C_{0a}, C_{1a}, C_{0b}, C_{1b}, C_{0a}$ (each group $C_i$ has 4 vertices that we say $C_{ia}, C_{ib}, C_{ic}, C_{id}$). $\endgroup$ – Mario Giambarioli Aug 4 '20 at 14:34
  • $\begingroup$ I think that this cycle has four vertices ($C_{0a}$, $C_{1a}$, $C_{0b}$ and $C_{1b}$). Did I misunderstand something? $\endgroup$ – Kaban-5 Aug 4 '20 at 14:45
  • $\begingroup$ Kaban-5, I am sorry, you are right. But I have a doubt: do you say that the optimal value of the objective function of LP relaxation is $\frac{1}{3} \times 4\times 4 = \frac{16}{3}$ (that is all the variables of $C_i$ for $i \in \left\{0; 1; 2; 3\right\}$ take value $\frac{1}{3}$)? $\endgroup$ – Mario Giambarioli Aug 4 '20 at 15:38
  • $\begingroup$ Yes, I think that this is the optimal value. $\endgroup$ – Kaban-5 Aug 4 '20 at 15:44
  • $\begingroup$ If I did not misunderstand your example, the solution of LP where the variables of $C_1$ take value $1$ and all the other variables of LP take value $0$, is a solution where the objective function value is $4$ ($4\lt \frac{16}{3}$). It is a solution of LP because every odd cycle of the graph contains a vertex of $C_1$. $\endgroup$ – Mario Giambarioli Aug 4 '20 at 15:55
0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 1. This should be a comment. 2. No, because the returned vertices in step 1, 2, and so forth might be from different minimal traversals, and if you combine them you now have a non-minimal traversal. $\endgroup$ – orlp Jul 30 '20 at 17:37
  • 2
    $\begingroup$ @orlp Why? Suppose the statement is true. If I solve and find a positive vertex v, I remove v and reduce the problem to finding a min odd cycle transversal on G-v which is equivalent since v is in an optimal solution and recursively find an optimal solution. $\endgroup$ – Hao S Jul 30 '20 at 17:48
  • $\begingroup$ The odd cycle transversal doesn't have to be unique. You can get different vertices from different odd cycle transversals. $\endgroup$ – orlp Jul 30 '20 at 17:53
  • 1
    $\begingroup$ setting i=t yields that OPT_G= c(v_1)+c(v_2)+...c(v_t) the cost of our output solution @orlp sorry OPT should denote the minimum cost of any odd cycle transversal $\endgroup$ – Hao S Jul 30 '20 at 18:07
  • 2
    $\begingroup$ Hao S is right, if my statement is right, it implies that one could solve odd cycle transversal by solving the LP, finding a positive vertex, removing it from the graph and repeating. But this does not mean that P=NP (odd cycle transversal is NP-hard) because in general the number of odd cicles in a graph is exponential with the number of vertices. $\endgroup$ – Mario Giambarioli Jul 30 '20 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.