2
$\begingroup$

Suppose we have a graph G. Say B a fundamental basis of the cycle space of G. Say LP a linear programming problem where there is a variable for each vertex of G, each variable can take value $\geq 0$, for each odd cycle of B we add to LP the constraint $x_{a} + x_{b} + x_{c} + ... + x_{i} \geq k$ where $x_{a},x_{b},x_{c},...,x_{i}$ are the verteces of the cycle and $k$ is the number of vertices of the cycle. The objective function of LP is $\min\sum\limits_{i=1}^{n}{x_{i}}$.

We say S an optimal solution of LP. Can we say that each vertex, whose variable takes a value $\gt 0$ in S, is a vertex of at least a minimum odd cycle transversal of G?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

No. Let $G$ be the graph obtained by gluing a $3$-cycle $abc$ and a $5$-cycle $cdefg$ together at vertex $c$. Then $(x_a, x_b, x_c, x_d, x_e, x_f, x_g)=(0,0,3,1,1,0,0)$ is an optimal solution of the LP. However, neither $d$ nor $e$ are contained in a minimum odd cycle transversal of $G$, since $\{c\}$ is the unique minimum odd cycle transversal of $G$.

The answer is also no to the updated question in the comment below. Here is a counterexample for both versions. Let $C_n$ be an odd cycle with $n \geq 5$. Fix $e=ab \in E(C_n)$ and let $T=C_n - e$. Let $G$ be the graph obtained from $C_n$ by adding all edges $f$ such that $T \cup f$ contains an even cycle. Then, the fundamental basis of $G$ with respect to $T$ contains exactly one odd cycle, namely $C_n$. Thus, $x=(\frac{1}{n}, \dots, \frac{1}{n})$ is an optimal solution to the revised LP (see comment below) and $x=(1, \dots, 1)$ is an optimal solution to the original LP. However, it is not true that every vertex of $G$ is in a minimum odd cycle transversal, because the only minimum odd cycle transversals of $G$ are $\{a\}$ and $\{b\}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ First of all, thank you for the answer. Then I would like to change the question just a little bit: what about if we replace the constraint x_a+x_b+x_c+...+x_i >= k with x_a+x_b+x_c+...+x_i >= 1 for each odd cycle of B? $\endgroup$
    – Mario Giambarioli
    Commented Mar 4, 2020 at 17:58
  • $\begingroup$ I am sorry, but I do not understand your counterexample: if we suppose n = 5, C_n is the odd cycle with edges ab, bc, cd, de, ea. T is the graph with edges bc, cd, de, ea. G is the graph with edges ab, ad, bc, bd, cd, ce, de, ea. G has 5 odd cycles: abcde, abd, bcd, cde, dea. Now it is not true that a is an odd cycle transversal of G, because if we remove the vertex a, the odd cycle cde is still alive (the same if we remove the vertex b). I am sorry if I have misunderstood your counterexample. $\endgroup$
    – Mario Giambarioli
    Commented Mar 5, 2020 at 7:25
  • $\begingroup$ You are supposed to add the edges $be$ and $ac$ (not $ce, bd$, and $ad$) to $C_5$. $\endgroup$
    – Tony Huynh
    Commented Mar 5, 2020 at 8:22
  • $\begingroup$ Ok, I think that if we add the constraint $x_{a} + x_{b} + x_{c} + ... + x_{i} \geq 1$ for each odd cycle of G (not only for the odd cycles of B), then we can say that each vertex, whose variable take a value $\gt 0$ in an optimal solution of LP, is a vertex of at least a minimum odd cycle transversal of G. Is it right? $\endgroup$
    – Mario Giambarioli
    Commented Mar 6, 2020 at 9:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .