4
$\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.

1 Answers 1

3

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$.

  • 0
    No, there might be just one entrance to and exit from the handle, but then the teeth get more entrances and exits.2012-11-25