Online Event: Open Problem Session (Dec 14)

Another successful open problem session! 🙂 Thank you to everyone who attended and a special thank you to our presenters. The slides are posted below.

Date: Tuesday, December 14
Time: 1:30-4:00pm EST (6:30-9:00pm GMT, 7:30-10:00am Wed NZDT)

Schedule:
Session 1: 1:30-2:30pm EST
Session 2: 3:00-4:00pm EST
Social Time: 4:00pm EST – ??

Format:
In each session, several open problems will be presented. For each problem, we’ll have ~5 minutes for the presentation followed by ~5 minutes for discussion. There may be time at the end of each session for more discussion or unplanned open problem contributions.

Session 1:
1. Nathan Bowler – slides
2. Rose McCarty – slides
3. James Davies – slides
4. MichaÅ‚ Pilipczuk – slides
5. Nicholas Anderson – slides
6. Ben Moore – slides

Session 2:
1. Bruce Richter – slides
2. Michael Wigal – slides
3. Dillon Mayhew – slides
4. Zach Walsh – slides
5. Jorn van der Pol – slides
6. Jim Geelen – slides

Online Talk: Michael Wigal

Tuesday, Dec 7, 3pm ET (8pm GMT, 9am Wed NZDT)
Michael Wigal, Georgia Tech
Approximating TSP walks in subcubic graphs

 
Abstract:
We will show that if $G$ is a $2$-connected simple subcubic graph on $n$ vertices with $n_2$ vertices of degree $2$, then $G$ has a TSP walk of length at most $5n/4 + n_2/4 -1$, establishing a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible. In particular, there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have length $5n/4 + n_2/4 -1$ (respectively, $5n/4 – 2$). Our proof implies a quadratic-time algorithm for finding such a TSP walk, thereby giving a $5/4$ approximation algorithm for the graphic TSP on simple cubic graphs and improving on the previously best known approximation ratio of $9/7$.

Joint work with Youngho Yoo and Xingxing Yu.