LEA STRUCO Kick-off meeting

December 8th and 9th, LIAFA

SCHEDULE

Thursday 8th

8h40 Welcoming (coffee)
9h Opening: presentation of the LEA STRUCO
9h20 Z. Dvořák: Algorithms for structurally sparse graphs
10h30 Coffee break
10h45 É. Balandraud: Addition Theorems via the Combinatorial Nullstellensatz
11h40 J. Sgall: Two-bounded-space bin packing revisited
12h40 Buffet at LIAFA (room 6A92 "sous-marin")
14h10 Sylvain Schmitz: Algorithmic aspects of well-quasi-orderings and applications to verification
15h Free time to meet and work
16h Coffee break

All talks and coffee breaks are in room 1C18.

Friday 9th

8h50 Morning coffee
9h15 M. Habib: Multisweep graph algorithms
10h15 Coffee break
10h40 M. Loebl: Strength of graph polynomials
11h30 L. Viennot: Graph spanners and their relation to the girth conjecture
12h30 Lunch at the restaurant l'audiernes
14h Free time to meet and work
16h Closing coffee break

All talks and coffee breaks are in room 1D06.

ABSTRACTS OF THE TALKS

Zdeněk Dvořák (KAM, Univerzita Karlova): Algorithms for structurally sparse graphs

Many graph problems which are hard in general become easier (polynomial-time solvable, or at least fixed-parameter tractable or approximable) when restricted to specific graph classes. We give an overview of results of this form, with particular attention to techniques applicable to many different problems (algorithmic metatheorems) and techniques for structurally sparse graph classes (minor closed, having bounded expansion, nowhere dense).

Éric Balandraud (Équipe combinatoire & optimisation, Université Paris 6): Addition Theorems via the Combinatorial Nullstellensatz

The polynomial method has shown itself very efficient to prove generalizations and new results in many fields of combinatorics. In this talk, we will focus on additive combinatorics. We will explain the proofs of three addition theorems; Cauchy-Davenport, Dias da Silva-Hamidoune Theorem (Erdos-Heilbronn Conjecture) and a new result, which allows to answer to a conjecture of Selfridge.

Jiří Sgall (KAM, Univerzita Karlova): Two-bounded-space bin packing revisited

We analyze approximation algorithms for bounded-space bin packing by comparing them against the optimal bounded-space packing (instead of comparing them against the globally optimal packing that does not necessarily satisfy the bounded-space constraint). For 2-bounded-space bin packing we construct a polynomial time offline approximation algorithm with asymptotic worst case ratio $3/2$, and we show a lower bound of $5/4$ for this scenario. We show that no 2-bounded-space online algorithm can have an asymptotic worst case ratio better than 4/3. (This is joint work with Marek Chrobak and Gerhard J. Woeginger.)

Sylvain Schmitz (LSV, ENS Cachan): Algorithmic aspects of well-quasi-orderings and applications to verification

The talk presents an algebraic approach to proving complexity upper bounds on the length of controlled bad sequences in well-quasi-orderings. This leads to tight multiply-recursive upper bounds for verification problems proven decidable thanks to Highman's Lemma.

Michel Habib (LIAFA, Université Paris 7): Multisweep graph algorithms

Graph searches are well-known and studied in many applications. One can consider graph search using their underlying tree structure or analyze the complexity of their implementation. Here we consider a graph search as a producer of a total ordering on the set of vertices (the order in which the vertices are visited by the search). This viewpoint has been recently very successful on classical search such as Generic, BFS, DFS, LexBFS... and their respective orderings have been characterized using a four vertices forbidden configuration.

In this talk we will present what we think is a promising direction for graph algorithms design. The main issue is to use a series of consecutive graph searches in order to solve an optimization problem on a graph. From one search to the other we only keep track of a total ordering of the vertices which can be used to break ties during the next search. Such a framework is very easy to implement and can be applied even on graphs of huge size. If the series of searches is bounded it yields a linear time algorithm but unfortunately despite its simplicity the main difficulty remains to prove such an algorithm.

Therefore this can be understood as a composition of graph searches using a kind of operator based on a tie-break rule. This leads to multi-sweep algorithms made up of a series of consecutive graph searches.

Up to my knowledge the first examples of multisweep algorithms were described for planarity testing, see Hopcroft and Tarjan (1974) and also de Fraysseix, Ossona de Mendes and Rosentiehl (2006). The 2-sweep Depth-first Search algorithm for the computation of strongly connected components by Kosaraju (1978) can also be put in this framework. Another recent interesting example is the 6 Lexicographic Breadth First Searches (LBFS) algorithm for interval graph recognition by Corneil, Olariu and Stewart (2010).

We will briefly present the tools we can play with and describe two new applications for : computing the diameter, and computing the minimum path cover of a co-comparability graph. We finish with some natural open problems.

Martin Loebl (KAM, Univerzita Karlova): Strength of graph polynomials

We discuss graph polynomials, and in particular their role in the complexity of computation, and in the graph isomorphism problem.

Laurent Viennot (LIAFA and GANG, INRIA): Graph spanners and their relation to the girth conjecture

Given a graph, a spanner is a subgraph somehow preserving distances. There is indeed a trade-off between the number of edges in the spanner and how much the distances are stretched compared to the graph. Sequential as well as parallel algorithms for computing spanners will be presented. The trade-off achieved is optimal if we admit the girth conjecture of Erdös.

PRACTICAL INFORMATION

LIAFA

The meeting takes places at LIAFA, which is situated at the corner of rue Chevaleret and Clisson, in the 13th district of Paris.

The entrance is situated at 6 rue Clisson (there is an entrance at ``175 rue du chevaleret`` but it is not available due to some reconstruction work). The address is

      LIAFA
      6 rue Clisson
      75013 Paris

The closest metro station is Chevaleret, on line 6. Other close metro stops are Bibliothèque François Mitterand on line 14 and Campo-Formio on line 5.

The bus number 27 has a stop called Clisson, which is on rue Jeanne d'Arc, slightly north to the corner of rue Jeanne d'Arc and rue Clisson.

Should you need it, the LIAFA's secretary office is situated on 7th Floor, "Plateau A", office 7A23.

Internet access

Internet access will be ensured by two wireless networks:

  1. Eduroam
  2. Paris 7 wifi network: up7d

    People without an eduroam account will be given a personal login and password to connect to up7d, valid from 7th to 9th December.

Rooms and restaurant

There shall be signs indicating the way inside the building from the entrance situated at 6 rue Clisson.

Thursday

All talks and coffee breaks are in room 1C18 (1st floor, "Plateau C"). The buffet is in room 6A92 (6th floor, "Plateau A").

For convenience, the room 5D91 (5th floor, "Plateau D") is also reserved for the whole afternoon.

Friday

All talks and coffee breaks are in room 1D06 (1st floor, "Plateau D").

The restaurant l'audiernes is situated at

      22 Rue Louise Weiss
      75013 Paris

It's a five-minute walk away from LIAFA.

In case some signs are missing inside the building

If some signs are missing, just take one of the elevators shortly after the entrance at 6 rue Clisson. Go to the first floor and then follow either "Plateau C" (on Thursday) or "Plateau D" (on Friday). It will only remain then check for the right office number.

PARTICIPANTS

  Pierre Aboulker                 (LIAFA, Université Paris 7)
  Éric Balandraud                 (Équipe combinatoire & optimisation, Université Paris 6)
  Ahmed Bouajjani                 (LIAFA, Université Paris 7)
  Patricia Bouyer                 (LSV, CNRS)
  Pierre Charbit                  (LIAFA, Université Paris 7)
  Jérémie Dusart                  (LIAFA, Université Paris 7)
  Zdeněk Dvořák                   (KAM, Univerzita Karlova)
  Peter Habermehl                 (LIAFA, Université Paris 7)
  Michel Habib                    (LIAFA, Université Paris 7)
  Frédéric Havet                  (MASCOTTE, CNRS)
  Andrea Jimenez                  (KAM, Univerzita Karlova)
  Florent Jouve                   (Département de mathématique, Université d'Orsay)
  Tomáš Kaiser                    (KMA, Západočeská Univerzita)
  František Kardoš                (MASCOTTE, Univeristé de Nice-Sophia Antipolis)
  Daniel Kráľ                     (KAM, Univerzita Karlova)
  Martin Loebl                    (KAM, Univerzita Karlova)
  Lukáš Mach                      (KAM, Univerzita Karlova)
  Antoine Mamcarz                 (LIAFA, Université Paris 7)
  Jaroslav Nešetřil               (KAM, Univerzita Karlova)
  Patrice Ossona de Mendez        (CAMS, CNRS)
  Hana Polišenska                 (KAM, Univerzita Karlova)
  Sylvain Schmitz                 (LSV, ENS Cachan)
  Jean-Sébastien Sereni           (LIAFA, CNRS)
  Jiří Sgall                      (KAM, Univerzita Karlova)
  Nicolas Trotignon               (LIP, ENS Lyon)
  Laurent Viennot                 (LIAFA, INRIA)
  Tomáš Vojnar                    (DITS, Faculty of Information Technology of Brno)
  Jan Volec                       (KAM, Univerzita Karlova)
  Zelealem Yilma                  (LIAFA, Université Paris 7)