Shorter Tours by Nicer Ears
András Sebö, Jens Vygen · 2012
1 Extremely Nice Ears Suppose we have a graph G = (V,E) with an ear decomposition with the following properties (after deleting the trivial ears): 1. all short (consisting of 3 edges or less) ears are pendant (having no other ear attached to an interior node of the ear). 2. all ears are odd (have an odd number of edges) 3. the graph induced by all short ears is acyclic 4. all ears are open. Then we can find a tour of length at most 75 |V |. Proof. We take the best result of two algorithms. The first algorithm is the following: 1. take the edges of all short ears 2. add a minimal set of edges so that all nodes not in the interior of pending ears are connected 3. add all edges of remaining pendant ears 4. find a minimal T -join, where T is the set of nodes that have odd degree in current solution. The number of edges in the solution for each step is: 1. 3 2 |V3|, where V3 is the set of nodes that are interior nodes of 3-ears, since 3 edges are added for every 3-ear, and each 3-ear has 2 interior nodes 2. |V0| − π3 − 1, where π3 is the number of 3-ears, and V0 is the set of nodes that is not in the interior of pending ears, since we can view this as the number of edges in a tree connecting |V0| − π3 nodes, after contracting the 3-ears of the first step; the fact that the graph induced by all short pendant ears is acyclic means that every contraction reduces the number of nodes by 1 3. ≤ 54 |Vp,≥5|, where Vp,≥5 is the set of nodes that are interior nodes of pendant ears of size 5 or larger, since x edges are added for every x− 1 nodes in the interior, and x ≥ 5 1To do: add subsection explaining how the case with closed ears can be handled, add algorithms for 2-connected subgraph problem and connected T -join problem, add section about notation and terminology in paper, which I don’t follow here.