WG 2013 in Lübeck

Many people might be at the Copacabana SoCG these days. I, however, went to Lübeck to this year's Workshop on Graph-Theoretic Concepts in CS. Today is already the last day of the conference.  I have never been in Lübeck before. The city is really nice, definitely worth a visit. The conference site is a hotel, which I usually don't like that much. However, this time it is really well-managed by the hotel.

Let me start with the invited talks. I have seen only two of the three talks. The last talk by Feodor Dragan will be given later today. I enjoyed the invited talks very much. The first was given by Ola Svensson about graph-TSP. Ola has received the best paper award at last year's FOCS for its paper and the result is indeed very nice. The Christofides heuristic is still the best known approximation algorithm for general (symmetric) TSP. This classic approach gives an 1.5-approximation, however, it is widely believed that the Held-Karp LP-relaxation gives a 4/3-approximation. A special version of TSP is graph-TSP, that is TSP with a distance function that is defined via distances in a graph. Not long ago, nothing special was known about approximating graph-TSP. The first (slight) improvement was due to Oveis et al. (2010). The idea here was to modify Christofides approach, such that the the spanning tree is cleverly sampled, instead of taking the MST. Completely other ideas were used by Ola and his co-author to get a better approximation. The key idea is that one can find a set of matchings in a subcubic graph, such that every edge is contained in the same number of matchings. The tour is then obtained by taking a matching and combine it with a spanning tree. The crucial idea is now, that instead of adding edges, sometimes edges can be deleted in the "combination" part. Moreover, instead of a spanning tree one can work with a sparser structure that certifies the connectedness of the tour. This gives rise to a 1.461-approximation. This technique was recently refined by Mucha (1.44-approximation). The current best approximation algorithm is due to Sebö and Vygen (2012) (1.4-approximation) it uses also some other ideas. In particular, it uses  ear decompositions. It doesn't seem likely that this is the end of the story for graph-TSP.

The second invited talk was given by Berthold Vöcking about online algorithms. Since I don't know much about online algorithms, I learned a lot about this interesting topic. The talk was dealing with graphs with bounded inductive independence. This is a very natural condition for graph classes, it basically says that when you add the vertices of the graph in some order one after another, then every newly added vertex will have bounded vertex degree when added. Many graph classes have bounded inductive independence (disk graphs, interval graphs, planar graphs, etc. ). Berthold presented an online algorithm for the independent-set problem that gives a O(\rho^2) approximation for graphs with inductive independence \rho in the unweighted case. For the weighted case you have to add a factor of \log n. This algorithm was analyzed in the secretary model, but the bounds also hold in other stochastic models.

I also want to highlight two of the regular talks. The first was about "Tight Upper Bounds for Minimum Feedback Arc Sets of Regular Graphs" given by Kathrin Hanauer. Beside other things she showed that every (sub)cubic graph with n vertices contains a feedback-arc-set of size at most n/3. There is also a related result for graphs with maximum degree 4. In order to get the results new techniques were developed that guaranteed the existence of a "nice" ordering induced by the DAG after taking out the feedback-arc set. "Nice" means here that one can assume that several helpful properties for the linear ordering hold.

Another interesting talk was given by Steve Chaplick. Steve presented a result about representing graphs as contact representation of "L-shapes". Very recently, new results about these representations were obtained. The talk was about tweaking some of the known techniques such that a representation with equilateral L-shapes can be obtained. In particular, it was shown that everything that can be represented with an L-representation can also be represented with an equilateral L-representation. Little is known about representation with L-shapes allowing 90°rotations.

The next WG is in close to Orléans, France. I think I have heard that in 2015 it will be in Munich.

Leave a Reply