3
$\begingroup$

A comb can be defined by a handle $H$ and a number of teeths $T_1,T_2,\dots,T_t$ such that:

  • $H,T_1,T_2,\dots,T_t \subseteq V$
  • $T_j \setminus H \neq \emptyset$ $\,\,\, \forall 1 \leq j \leq t$
  • $T_j \cap H \neq \emptyset$ $\,\,\, \forall 1 \leq j \leq t$
  • $T_i \cap T_j = \emptyset$ $\,\,\, \forall 1 \leq i < j \leq t$
  • $t \geq 3$ and odd

A comb inequality states that:

$$x(E(H)) + \sum_{j=1}^{t} x(E(T_j)) \leq |H| + \sum_{j=1}^{t} |T_j| - \frac{3t+1}{2}$$

Comb inequalities are valid inequalities for the TSP.

I'm looking for a simple explanation of why these inequalities are valid for any hamiltonian cycle. I'm not looking for a formal proof. A simple, informal and intuitive explanation will work.

Since comb inequalities generalize 2-matching inequalities, perhaps this can be better explained by showing the special case and then extending it to the general case.

$\endgroup$
2
$\begingroup$

Here $x(E(S))$ is the number of edges in the cycle whose vertices are both in set $S$ of vertices. For any set $S$ of vertices, $x(E(S)) = |S| - d(S)/2$, where $d(S)$ is the number of edges of the cycle with one vertex in $S$ and one out. Thus $$ x(E(H)) + \sum_i x(E(T_i)) = |H| + \sum_i |T_i| - \frac{1}{2} \left(d(H) + \sum_i d(T_i)\right)$$ The inequality then says $$d(H) + \sum_i d(T_i) \ge 3t + 1$$ For each $i$ let $d_i(H)$ be the number of edges with one vertex in $H \cap T_i$ and one outside $H$. Then $d(H) \ge \sum_i d_i(H)$. Now it's not hard to see that $d_i(H) + d(T_i) \ge 3$ (think of the various ways the cycle can enter and leave $H \cap T_i$ and $T_i \backslash H$), so that gives us $d(H) + \sum_i d(T_i) \ge 3t$. But $d(H)$ and $d(T_i)$ are all even and $3t$ is odd, so we can't have equality here: we must have $d(H) + \sum_i d(T_i) \ge 3t+1$.

$\endgroup$
  • $\begingroup$ Is it ok to say that teeths are a way of forcing a predefined number of enters/exits from the handle? $\endgroup$ – aromero Nov 24 '12 at 19:20
  • $\begingroup$ No, there might be just one entrance to and exit from the handle, but then the teeth get more entrances and exits. $\endgroup$ – Robert Israel Nov 25 '12 at 2:51

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.