AlGCo séminaire

Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for t-interval graphs when t>=3 and polynomial-time solvable when t=1. The problem is also known to be NP-complete in t-track graphs (which form a subclass of t-interval graphs) when t>=4 and polynomial-time solvable when t<=2. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called t-circular interval graphs and t-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time t-approximation algorithm for WEIGHTED MAXIMUM CLIQUE on t-interval graphs, improving earlier work with approximation ratio 4t.

Random geometric graphs constitute an important family of random graphs in which vertices are scattered at random over some domain and edges are placed between any two vertices within a given distance. These graphs have recently attracted the attention of many researchers, as they provide a theoretical model for some types of wireless networks. In particular, there have been several authors studying the existence of Hamilton cycles in the random geometric graph. In this talk, we describe some of these works along with some related results. We also survey the basic properties of the random geometric graph, and compare them to other families of random graphs.

Power domination in graphs was birthed from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A set of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set following a set of rules (according to Kirschoff laws) for power system monitoring. Last year, we proposed some common generalization to domination and power domination. Whereas the definition of a power dominating set implies some propagating behavior of the set of monitored vertices, a phenomenon very different from the standard domination parameter, this generalization revealed some common properties of the two problems. After a rather general introduction on power domination and its generalization, we will show some recent bounds on the generalized power domination number of regular graphs.

Classical theorem of Barany states that there exists c_d > 0 such that for every n-set P of points in R^d in general position, there exists a point of R^d contained in at least c_d * {{n} \choose {d+1}} d-simplices with vertices at the points of P. Gromov improved the known lower bound on c_d by topological means. Using methods from extremal combinatorics, we improve one of the quantities appearing in Gromov's approach and thereby provide a new stronger lower bound on c_d for arbitrary d. In particular, we improve the lower bound on c_3 from 0.06332 to more than 0.07480; the best upper bound known on c_3 being 0.09375.

This talk is meant as an extended bibliography to the recent result by Chudnovsky, Edwards and Seymour stating that an 8-regular planar graph is 8-edge colorable iff every odd subset of vertices has at least 8 outgoing edges. We will recall a few theorems on simple graphs, most notably Vizing's, and highlight the similitudes between Golbderg's conjecture and Vizing's theorem.

La plupart des problèmes classiques de coloration sur les graphes sont connus pour être NP-complets, même lorsque le nombre maximum de couleurs est fixé. De ce fait, dès lors que l'on étudie un nouveau problème de coloration, il est naturel de se demander si celui-ci est également NP-complet, en particulier pour un nombre de couleurs fixé.

Matamala et Zamora ont récemment introduit une nouvelle variante de problème de coloration, appelée Coloration Additive. Ce problème demande de trouver une coloration (quelconque) des sommets du graphe, de telle sorte que la coloration induite sur les arêtes soit une coloration propre (chaque arête reçoit comme couleur la valeur absolue de la différence des couleurs de ses deux extrémités).
Ce problème de coloration de graphes a notamment la particularité d'être étroitement lié à un problème encore ouvert en théorie des nombres : étant donné un entier n, on cherche le plus grand sous-ensemble d'entiers parmi {1,2,...,n} ne contenant pas de 3-progression arithmétique. En effet, ce problème de théorie des nombres est équivalent au problème de la coloration additive sur une clique.

Dans cet exposé, je parlerai de la complexité du problème de Coloration Additive. Je montrerai que ce problème est NP-complet, même lorsque la couleur maximale autorisée est fixé et au moins égale à 3, à l'instar des problèmes classiques de coloration. Je montrerai également que l'on peut résoudre ce problème en temps polynomial sur les arbres, par un algorithme non trivial ; une extension aux graphes de largeur arborescente bornée ne semble toutefois pas triviale.

Pour un ensemble de terminaux T dans le plan, un réseau de Manhattan est un réseau dans lequel il existe un plus court chemin rectilinéaire entre chaque paires de terminaux. Un réseau de Manhattan minimal est un réseau de Manhattan de longueur minimale.
Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés dont la boule unitaire est un polygone convexe central symétrique. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire.
Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.

In this talk, we discuss constraint satisfaction problems (CSPs) with counting quantifiers. These can be defined as the problems of model checking of first-order formulas where
-- we allow only conjunction among connectives
-- variables are quantified using so-called "counting quantifiers" which assert the existence of at least j elements satisfying the property (for various values of j).

For a finer control of the complexity, we write X-CSP(H) for the above problem where the template (model) is H and the values of j are restricted to be taken from X.

For instance, for X={1} we obtain the usual CSP (only existential quantification) while X={1,|H|}, where |H| is the size of the domain of H, yields precisely QCSP (quantifiers are existential and universal) While CSP problems are in NP, QCSP problems are in PSPACE (some are PSPACE-complete) much like all X-CSPs.

As our main result, we study the cases when the template is an undirected cycle or a clique. For cycles, we prove a complete trichotomy (LOGSPACE, NP-complete, PSPACE-complete) for all possible cases of X. For cliques, we prove such a trichotomy for all but one open case.

We also consider the problem {1,2}-CSP(H) for graph templates H. Such problems are a simplest generalization of the standard CSP={1}-CSP. We seek a dichotomy distinguishing beween P and NP-hard. For non-bipartite H, all such problem are NP-hard by the celebrated result of Hell-Nesetril. Thus we focus on bipartite H and provide evidence for the dichotomy. Namely, we conjecture that {1,2}-CSP(H) is in P for all forests and all bipartite graphs containing a 4-cycle, and is NP-hard otherwise. As evidence for this, we prove the hardness direction, discuss the case when bipartite H contains a 4-cycle (all such problems are in LOGSPACE), and propose an algorithm for forests.

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.

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

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.

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.

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.

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.

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.

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...).

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.

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.

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.

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.

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.

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.

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.

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.

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

Département Informatique - LIRMM

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

Département Informatique - LIRMM

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