Seminar of Theoretical Computer Science - Robert Lukoťka (31.3.2017)

Friday 17.3.2017 at 11:00, Lecture room M/213

---

Róbert Lukoťka:
Travelling salesman problem on cubic and subcubic graphs

Abstract: 
Dvořák, Kráľ, and Mohar [Z. Dvořák, D. Kráľ, B. Mohar: Graphic TSP in cubic graphs, arXiv:1608.07568] proved that every bridgeless simple $2$-connected cubic graph on $n$ vertices with $n_2$ vertices of degree $2$ contains a spanning closed walk of length at most $9/7 cdot n+2/7 cdot n_2 -1$. We provide a significantly shorter proof of this statement.

Our analysis of $6$-circuits is sufficiently strong, so that limiting aspect for further improvement is the (lack of) analysis of the $7$-circuits. To demostrate this, we provide a basic analysis to slightly improve the constants in the result of Dvořák, Kráľ, and Mohar.

Focusing on circuits of length $6$, we show that a bridgeless cubic graph of girth $6$ has a $2$-factor $F$ that contains $9/13 cdot n$ vertices that are not in $6$-circuits of $F$. The ideas from the proof might provide clues how to further improve the analysis of TSP tours in subcubic graphs.

 

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php

---