AlGCo : algorithmique, graphes et combinatoire
Séminaire/Groupe de Travail

Hervé Hocquard LaBRI, Bordeaux
Coloration d'arêtes à distance 2
Ce travail a été réalisé en collaboration avec Pascal Ochem, André Raspaud et Petru Valicov.

Une k-coloration d'arêtes à distance 2 (ou forte) d'un graphe est une coloration d'arêtes, qui utilise au plus k couleurs, telle que deux arêtes adjacentes ou adjacentes à une même arête reçoivent des couleurs différentes. L'indice chromatique fort d'un graphe G est le nombre minimum de couleurs k tel que G admet une k-coloration forte d'arêtes. La première partie de cet exposé sera consacrée à la majoration de l'indice chromatique fort pour certaines classes de graphes. Dans la seconde partie nous présenterons des résultats de complexité (du problème de k-coloration forte d'arêtes) pour les graphes planaires.

Stéphane Bessy LIRMM
Quelques problèmes en théorie et algorithmique des graphes (Soutenance d'HDR)

Jury:

• András Gyárfás, research advisor, Computer and Automation Research Institute, Budapest, Hongrie (rapp.).
• Hajo Broersma, full professor, University of Twente, Twente, Pays-bas (rapp.).
• Michel Habib, professeur, LIAFA, Université Paris 7.
• Jean-Claude Konig, professeur, LIRMM, Université Montpellier 2.
• Christophe Paul, directeur de recherche, Université Montpellier 2.

Renseignements supplémentaires: http://www.lirmm.fr/~bessy/hdr.html

Dimitrios M. Thilikos Athène, Grèce
Algorithmic Graph Minors: turning Combinatorics to Algorithms

The main mathematical achievement of the Graph Minors Theory, developed by Robertson and Seymour, was the proof of Wagner's conjecture, now known as the Robertson & Seymour Theorem, stating that graphs are well quasi ordered under the minor containment relation. Besides its purely theoretical importance, GMT induced a series of powerful algorithmic results and techniques that had a deep influence in theoretical computer science. GMT offered the theoretical base for the understanding and the resolution of some of the most prominent graph-algorithmic problems in the design of parameterized algorithms. In this talk we give a brief presentation of the main results and techniques to this direction and we comment on their potential and their limitations.

Marcin Kaminski Bruxelle, Belgique
The Plane-Width of Graphs
This is joint work with Paul Medvedev and Martin Milanic.

Map vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least a unit distance apart. The plane-width of a graph is the minimum diameter of the image of the vertex set over all such mappings. We study this notion and establish a relation between the plane-width and the chromatic number of the graph. We also connect it to other well-known areas, including the circular chromatic number and the problem of packing unit discs in the plane.

Pinar Heggernes Bergen, Norvège
Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths
Joint work with: Rémy Belmonte, Petr Golovach, Pim van 't Hof, Marcin Kaminski, and Daniël Paulusma

The k-Disjoint Paths problem, which takes as input a graph G and k pairs of specified vertices (s_i,t_i), asks whether G contains k mutually vertex-disjoint paths P_i such that P_i connects s_i and t_i, for i = 1, ..., k. We study a natural variant of this problem, where the vertices of P_i must belong to a specified vertex subset U_i for i = 1, ..., k. In contrast to the original problem, which is polynomial-time solvable for any fixed integer k, we show that this variant is NP-complete even for k = 2. On the positive side, we prove that the problem becomes polynomial-time solvable for any fixed integer k if the input graph is chordal. We use this result to show that, for any fixed graph H, the problems H-Contractibility and H-Induced Minor can be solved in polynomial time on chordal graphs. These problems are to decide whether an input graph G contains H as a contraction or as an induced minor, respectively.

Emeric Gioan LIRMM
Chirotopes : propriétés combinatoires des orientations de triangles, tétraèdres, etc.

Cet exposé sera surtout pédagogique. Etant donnés des points en position générale (ou pas) dans le plan, dans l'espace 3D, ou plus généralement dans un espace affine, on liste les orientations des triangles, téraèdres, simplexes, formés par ces points en leur attribuant un signe + ou -. On verra quelles propriétés combinatoires simples ces signes satisfont (on verra ainsi l'une des axiomatiques des matroïdes orientés, dite des chirotopes), ainsi que quelques questions qui se posent.

Arnaud Mary LIMOS, Clermont-Ferrand
Problème de génération

Le problème de génération associé à une structure discrète finie $S$ munie d'un prédicat $P$ sur les éléments de $S$, consiste à énumérer tous les éléments de $S$ vérifiant $P$. Nous parlerons de complexité de problème de génération notamment au travers des problèmes les plus étudiés, comme les problèmes de dualisations dans des ordres partiels, la génération des éléments maximaux d'un système d'indépendants, ou encore la génération d'objets caractéristiques dans les graphes.

Stéphane Bessy LIRMM
Automates synchronisants et Conjecture de Cerny

Un mot w est synchronisant pour un automate fini et déterministe si il envoie n'importe quel état de l'automate sur un état fixé à l'avance. J. Cerny conjectura en 1964 que tout automate à n états possédant un mot synchronisant en possède un de longueur au plus (n-1)². La meilleure borne connue sur un tel mot était de (n³-n)/6 et datait du début des année 80. Récemment, A. Trahtman a amélioré cette borne d'un facteur 7/8.

Abandonnant rapidement le vocabulaire des automates pour celui des graphes orientés, je présenterai, si possible, la preuve de Trathman (que j'ai vu cet été), ainsi que le résultat de J.Kari qui a prouvé en 2001 la conjecture de Cerny pour les graphes orientés eulériens (une jolie preuve basée sur de l'algèbre linéaire...).

Rolf Niedermeier Technische Universität Berlin
Studies in Computational Aspects of Voting

Voting problems play a prominent role in the field of computational social choice. There are numerous challenges concerning the computational complexity of voting problems. In the first part of the talk, we introduce and review several NP-hard voting problems. In the second part, we describe in some more detail a recent result on the NP-hardness of manipulating the so-called Borda voting protocol and discuss the consequences of this result.

Christophe Paul LIRMM
Parameterized K-minor cover in single exponential time

Given an input graph G and an integer k, the parameterized K4 -minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K4 -minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can also be expressed as Treewidth-t Vertex Deletion problems, with t = 0 for the former and t = 1 for the latter. It follows from the celebrated Courcelle's theorem or from the Graph Minor Theorem, that for every constant t, Treewidth-t Vertex Deletion is FPT. A single-exponential FPT algorithm for Feedback Vertex Set was developed only (somewhat) recently, while a simple branching algorithm for Vertex Cover is a folklore result. It is unlikely that Treewidth-t Vertex Deletion can be solved in subexponential time. But whether the K4 -minor cover can be solved in single-exponential FPT time was open. We prove that such an algorithm does exist. We first use the iterative compression paradigm to reduce our problem to the parameterized disjoint K4 -minor cover, which given a K4 -minor cover S of size k of a graph G seeks for a smaller K4 -minor cover S' disjoint from S. Based on the structure of K4 -free graphs (i.e. graphs whose blocks are series-parallel graphs) we describe a reduce-or-branch process which computes a set of so-called "independent" instances such that one of these independent instances is positive iff the original instance was positive. The reduce-or-branch process involves some protrusion based reduction rules. It turns out that the disjoint K4 -minor cover problem on an independent instance is equivalent to the vertex cover problem on a circle graphs, which is known to be polynomial time tractable.

Pascal Ochem LIRMM
Problèmes ouverts de coloration et NP-complétude

Une conjecture bien connue dit notamment que les graphes planaires de maille 8 ont un homomorphisme vers le cycle de taille 5. On montre que si la conjecture est fausse, alors decider si un graphe planaire de maille 8 admet un homomorphisme vers le cycle de taille 5 est un problèmes NP-complet. On donnera aussi des résultats de ce genre ("pas tous colorable" implique "NP-complet") pour des problèmes ouverts de coloration acyclique et de coloration impropre. En collaboration avec Louis Esperet, Mickael Montassier et Alexandre Pinlou.

Marthe Bonamy LIRMM
Graph recolouring

Given two proper vertex k-colourings of a graph G, is there a way to recolour G from one colouring to the other while recolouring one vertex at a time and ensuring that G is alway properly coloured? In how many steps? After a small introduction, we will present a method that can help prove such results on some graph classes, and sketch the resulting proofs concerning cographs, chordal graphs and distance-hereditary graphs.

Bình Minh Bùi Xuân LIP6, Paris 6
Largeur de graphes denses: peut on parler d'optimisation ?

La décomposition arborescente est une théorie riche qui a aussi connu beaucoup de succès d'un point de vue d'optimisation pratique. Ceci est vrai à la fois pour l'étape consistant à trouver un arbre de décomposition de bonne largeur, voir p.e. [Amir], et l'étape consistant à résoudre un problème précis connaissant un tel arbre, voir p.e. [van Rooij et Bodlaender]. Cependant, l'approche paramétrée (Fixed Parameter Tractability, FPT, en anglais) par larguer arborescente se révèle peu efficace face aux graphes denses, où la valeur de la largeur, même optimale, est souvent de l'ordre du nombre de sommets du graphe.
Nous allons présenter des travaux récentes visant à étendre une telle approche pour les graphes denses. Nous allons brièvement nous fixer un cadre théorique commun à ces travaux, puis présenter des implémentations connues à ce sujet: état des lieux pour largeur de clique [Durand et Courcelle], calcul exacte et approché pour largeur de rang [Adler et Krause] [Bui-Xuan, Trébuchet et Raymond], heuristique pour largeur booléenne [Hvidevold, Sharmin,Telle et Vatshelle]. Nous poserons la question donnée dans le titre de l'exposé et proposons quelques pistes de discussion.

Sylvain Guillemot
Patterns in matchings and permutations

A linear matching consists of 2n vertices ordered linearly, and of n vertex-disjoint edges joining these vertices. These objects are encountered in combinatorics and in computational biology, where they represent the base pairings in RNA secondary structures. In this talk, we will focus on a pattern matching problem for these objects, where we have to decide if a given object (the pattern) is a substructure of another object (the target). We will describe some results on the parameterized complexity of this problem, by presenting two simple FPT algorithms and a W[1]-hardness result. We will then consider a similar pattern matching problem for permutations, and formulate a conjecture which could lead to the fixed-parameter tractability of this problem when the pattern size is chosen as parameter.

Mathew C. Francis LIRMM
Intersection graphs of paths on a grid

Two subgraphs of a graph are said to intersect if they share at least one common vertex. Given a family F of subgraphs of some particular graph, a graph G is said to be an intersection graph of F if there is a mapping f:V(G)->F such that (u,v) is an edge in G if and only if f(u) and f(v) intersect. We look at a class of graphs called VPG, which was introduced by Asinowski et. al., and are defined to be the intersection graphs of subpaths in a rectangular grid. This class turns out to be exactly the class of STRING graphs (intersection graphs of curves in the plane). When each path is restricted to have at most k bends, the resulting subclass of VPG is denoted as B_k-VPG. Clearly, B_i-VPG is contained in B_{i+1}-VPG and thus we have a hierarchy of subclasses of STRING. The question of whether each containment in this hierarchy is strict is still open. In this direction, it was shown by Asinowski et. al. that B_1-VPG is a strict subclass of STRING by constructing a string graph that cannot be represented as the intersection of one bend paths on a grid. We show some finer separation results for small number of bends. In particular, we show that B_1-VPG is a strict subclass of B_2-VPG and also show that within the class of B_1-VPG, restrictions on the kinds of bends that can be used leads to different, sometimes mutually incomparable, subclasses.

Daniel Gonçalves LIRMM
On Exact Algorithms for Permutation CSP
(joint work with Eun Jung Kim)

In this talk we will consider the Permutation Constraint Satisfaction Problem (Permutation CSP). In this problem you are given a set of variables V and a set of constraints, which constraints are tuples of elements of V. The goal is to find a total ordering of the variables, p : V --> [1 ... |V|], that satisfies as many constraints as possible. A constraint (a,b,c,d) is satisfied by an ordering p when p(a)<p(b)<p(c)<p(d). An instance of this problem has arity k if all the constraints are k-tuples.

This problem expresses a variety of permutation problems including Feedback Arc Set and Betweenness problems. A naive algorithm for this problem (listing all the orderings) requires 2^O(n log n) time. Interestingly, Permutation CSP for arity 2 or 3 can be solved by Held-Karp type algorithms in time 2^O(n), but no algorithm is known for arity at least 4 with running time significantly better than 2^O(n log n). We will prove that assuming ETH (the Exponential Time Hypothesis: "There is no 2^(en) algorithm for 3-SAT, for any e>0"), such improvement for arity >=4 is impossible.