AlGCo homepage

A graph G is an EPG-graph if there is a set P of paths in the plane grid representing the vertices of G such that two vertices are adjacent iff the corresponding paths share a grid edge. Similarly, G is a VPG-graph if for a set P vertex-intersection of paths in P corresponds to adjacency in G.

It is easy to see, that all graphs are EPG-graphs and that VPG-graphs are exactly STRING-graphs. This motivates the search for representations by 'simple' paths. In particular, given a graph one wishes to bound the number of bends per path in a representation. This parameter is called the edge and vertex bend number, respectively. E.g. graphs with edge bend number 0 are exactly interval graphs.

I will give a survey over results and open questions in the area. In the end I will focus on graphs with vertex bend number at most 1 and their relation to segment graphs.

An NP-hard graph problem P is said to be FPT (Fixed Parameter Tractable) w.r.t. to a given parameter if every instance can be reduced in polynomial time to an equivalent instance of P with size bounded by a function of that parameter (that instance is called a kernel). A typical way of designing such a pre-processing algorithm is through so-called reduction rules, where for example vertices of degree 1 are deleted, vertices of degree 2 replaced with an edge, etc. Once a nice candidate (i.e. nice set of reduction rules) is obtained, it remains to bound the size of the output as a function of the parameter. The existence of a function is good but not enough: we would like the function to be polynomial, then cubic, then quadratic, then linear, and even improve the constant factors.

On the other hand, discharging methods are used in order to obtain structural lemmas in graph theory. In general, the point is to prove by contradiction that a graph with some properties (planarity, bounded density...) must contain an element of a given list as a subgraph. In short, it is a counting argument that takes strong advantage of the graph structure. The existence of a subgraph from this given list can then be used for example for coloring purposes. In particular, this proof technique is decisive for the Four Colour Theorem.

Why not use the second as tools for the first? Kowalik introduced in 2011 a kernelization proof where a discharging argument yielded a more refined bound. In the same spirit, we prove that when restricting to planar graphs the benchmark problem of Feedback Vertex Set (how many vertices do you need to remove in your graph, for it to become a forest?) parameterized by the size of the solution (is removing k vertices enough?), a 13k kernel can be obtained instead of the previous 97k.

This talk is meant as an outsider's point of view on FPT, in an attempt to highlight some similarities with discharging and advocate for more permeability between the two fields. This is based on joint work with \Lukasz Kowalik (University of Warsaw).

Henri Perret du Cray : Un algorithme FPT amélioré pour le problème du stable dans les graphes sans taureau. (encadré par Ignasi Sau)

L'étude de problèmes paramétrés sur les graphes définis par exclusion de sous-graphe(s) induit(s) n'en est encore qu'à ses débuts. Des résultats récents de Chudnovsky sur la décomposition des graphes sans taureau ont permis de trouver un algorithme FPT pour le problème du stable dans cette classe de graphes [Thomassé, Trotignon, Vuskovic. 2013].

Nous présenterons quelques résultats de complexité paramétrée sur la classe des graphes sans taureau. Plus précisément, nous parlerons principalement d'un algorithme FPT amélioré pour le problème du stable. Nous nous intéresserons également à ce même problème sur une sous-classe des graphes sans taureau, pour laquelle nous présentons un algorithme FPT qui est asymptotiquement optimal en supposant l'ETH. Finalement, nous évoquerons aussi quelques résultats de W-difficulté.

--------------------------------------------------------------------------------------------------------

Clément Requilé : Complexité paramétrée et complétion plane à diamètre borné. (encadré par Dimitrios M. Thilikos)

Un problème mentionné par Chung en 1987 : étant donné un graphe plan, peut-on réduire son diamètre (au plus un entier d) en lui ajoutant des arêtes tout en conservant la planarité ? Fellows et Dejter ont montré en 1993 que le cas orienté était NP-Complet puis que les cas orienté et non-orienté étaient FPT (paramétré par d), via une preuve non constructive utilisant le théorème de Robertson et Seymour. Reste à trouver un algorithme FPT satisfaisant. Nous nous intéressons à une variante de ce problème, dans le cas non-orienté où le nombre d'arêtes par face à ajouter est borné par un entier k. Et nous donnons un algorithme FPT (paramétré par d et k) pour ce problème basé sur une programmation dynamique.

Florian Barbero : Tournois et cutwidth. (encadré par Christophe Paul)

Contrairement aux graphes non-orientés pourvus de la Treewidth, les digraphes ne disposent pas encore d'une mesure connue permettant d'améliorer efficacement beaucoup d'algorithmes. Ce n'est pas le cas de tous les graphes orientés : il est possible de calculer une Cutwidth pour les tournois. Je m'intéresse actuellement à un problème particulier, une extension de Feedback Arc Set in Tournaments [FAST]. Je présenterai durant ce séminaire quel est l’intérêt de ce problème, une partie de l'état de l'art, ainsi que des ébauches des résultats que nous espérons.

------------------------------------------------------------------------

François Dross : Large induced forests in sparse planar graphs. (encadré par Alexandre Pinlou et Mickael Montassier)

Albertson and Berman conjectured that every planar graph has an induced subgraph on at least one half of its vertices that is a forest. Akiyama and Watanabe later conjectured that this lower bound can be inproved to at least five eighths of the vertices in the case of bipartite planar graphs. Salavatipour partially answered the conjecture of Akiyama and Watanabe by showing that every triangle-free planar graph (and thus every bipartite planar graph) of order n admits an induced forest of order at least (17n + 24)/32. We will show that this bound can be improved to (24n + 28)/44. We will also consider the case of planar graphs of higher girth.

We will talk about the superconnectivity and restricted connectivity on graphs. The notion of superconnectivity roughly speaking means how connected a graph is in the family of maximally connected graphs. The restricted connectivity is an appropriate parameter to quantify the superconnectivity of a graph. Since the classical connectivity may not be sufficient to measure accurately how connected a graph is after deleting some edges, one might be interested in more refined indices of reliability. Even two graphs with the same connectivity, may be considered to have different reliabilities.

One classical problem in connectivity and restricted connectivity, is to find sufficient conditions for guaranteeing high connectivity of a graph. In this sense, conditions on the diameter, on the order, on the girth, and on the maximum and the minimum degree have been given in the literature.

The purpose of this talk is to present some results on the k-restricted edge-connectivity in triangle-free graphs. We could give sufficient conditions on the minimum degree and give an Ore-type condition for triangle-free graphs to guarantee high restricted connectivities.

We design the first linear-time algorithm for computing the prime decomposition of a digraph G with regard to the cartesian product. A remarkable feature of our solution is that it computes the decomposition of G from the decomposition of its underlying undirected graph, for which there exists a linear-time algorithm. First, this allows our algorithm to remain conceptually very simple and in addition, it provides new insight into the connexions between the directed and undirected versions of the cartesian product of graphs.

The celebrated Lovasz Local Lemma (LLL) is a probabilistic tool with many applications, particularly in graph coloring. The Entropy Compression Method (ECM) was introduced by Moser and Tardos in 2009 as an algorithmic version of the LLL. Many of the results previously obtained by LLL were recently slightly improved using ECM. Moreover ECM seems to be easier than LLL to handle: some of the results obtained using ECM, could have been obtained earlier with LLL.

Here we propose a general framework for graph coloring problems based on ECM. This framework is similar to the one of Esperet and Parreau, but it yields to tighter bounds. In particular, we derive that every graph with maximum degree D has an acyclic vertex-coloring using at most 1.5D^(4/3) + O(D) colors, and a non-repetitive vertex-coloring using at most D^2 + 1.89 D^(5/3) + O(D^(4/3)) colors.

This is joint work with M. Montassier, and A. Pinlou.

An on-line coloring game is a two-person game, played in (a finite number of) rounds by Presenter and Algorithm. In each round Presenter introduces a new vertex of a graph with its adjacency status to all vertices already presented. Algorithm colors the incoming vertex in a way to keep a proper coloring of the presented graph. The color is assigned before Presenter reveals the next vertex and is assigned irrevocably.

We investigate the strategies for Presenter in on-line graph coloring games. We give three strategies: The first one constructs bipartite graphs and forces any on-line coloring algorithm to use (2-o(1))\log_2 n colors (where n is the number of vertices in the constructed graph), the second one constructs triangle-free graphs and forces Omega(n^{1/2}) colors, and the third one constructs graphs that contain neither C_3 nor C_5 as a subgraph and forces Omega((n/logn)^{1/3}) colors. The first result matches the previously known strategy for Algorithm.

Joint work with Grzegorz Gutowski, Jakub Kozik and Xuding Zhu

Numerous approximation algorithms for unit disk graphs have been proposed in the literature, exhibiting sharp trade-offs between running times and approximation ratios. We propose a method to obtain linear-time approximation algorithms for unit disk graph problems. Our method yields linear-time (4+eps)-approximations to the maximum-weight independent set and the minimum dominating set, as well as a linear-time approximation scheme for the minimum vertex cover, improving upon all known linear- or near-linear-time algorithms for these problems.

Travail en collaboration avec V.G. Pereira de Sá et C.M.H. de Figueiredo.

Un graphe G est dit k-intervallaire si G est le graphe d'intersection d'ensembles de k intervalles de la droite réelle. Le nombre intervallaire (ou interval number) de G, noté par i(G), est le plus petit nombre entier i tel que G est un graphe i-intervallaire. Le nombre local de piste (ou local track number) d'un graphe G, noté par l(G), est le plus petit nombre entier l tel que G est le graphe d'intersection d'ensembles de l intervalles, au maximum, appartenant à différentes pistes. Le nombre de piste (ou track number) d'un graphe G, est le plus petit nombre entier t tel que G est l'union de t graphes d'intervalle.

On présente un résultat sur l'existence de représentations 2-local track pour tout graphe planaire de maille 7 et un résultat de NP-Complétude sur la classe des graphes G tels que t(G)<=d ou i(G)>d pour d fixé.

Ces résultats font partie d'un papier soumis avec Pascal Ochem, et d'un papier en préparation avec Pascal Ochem, Daniel Gonçalves, Guillame Guégan et Valentin Garnero.

Il n'est pas necessaire d'avoir suivi les deux exposes precedents pour suivre celui-ci. Precedemment nous avons vu des relations avec l'algebre lineaire et la topologie (configurations de points, programmation lineaire, arrangements d'hyperplans et de pseudospheres). Cette fois-ci nous verrons les axiomatiques combinatoires generales, et brièvement les arrangements de pseudodroites, puis nous détaillerons le cas particulier des graphes orientés, en insistant sur les propriétés de dualité (orientations acycliques / totalement cycliques, lemme de Farkas, polynome de Tutte).

Well-quasi-ordering is a deep and fruitful theory which lies at the heart of the influential Graph Minors project. Formally, a partially ordered set is said to be well-quasi-ordered if it contains no infinite decreasing sequence, nor infinite sequence of non-comparable elements. Research about well-quasi-orderings spans about 60 years, from the first results of Higman and Kruskal in the 50's to the recent results of Thomas and Liu. In Graph Minors, Robertson and Seymour proved that graphs are well-quasi-ordered by minors and by weak immersions; however such a result is not true for other common containment relations. An interesting line of research initiated in the early 90's by Damaschke and Ding is to study which graph classes defined by excluded substructure are well-quasi-ordered by some containment relation. In this direction, our main result is a complete characterization of these classes for the induced minor relation. After an introduction to the classic results and techniques related to well-quasi-orderings, I will present our contribution and the main parts of the proof. This is joint work with Jarosław Błasiok (University of Warsaw), Marcin Kamiński (idem) and Théophile Trunck (ENS de Lyon).

Introduit en 1990 par Yannakakis, on s’intéresse au problème suivant, où une coupe est une bipartition des sommets du graphe : est-ce qu’il existe une famille F ayant un nombre polynomial de coupes telle que, pour tous stable S et clique K ne s’intersectant pas, il existe une coupe (U, W) dans F qui sépare K et S, c’est-à-dire K ⊆ U et S ⊆ W ? Une telle famille de coupes séparant toutes les cliques de tous les stables est appelée un Clique-Stable séparateur (noté CS-séparateur).

Une première série de résultat est l’obtention d’un CS-séparateur polynomial pour les graphes aléatoires, pour les graphes sans H induit où H est un graphe split, et pour les graphes sans Pk ni Pk induits. Ces derniers seront l’occasion de voir les liens entre la propriété d’Erdős-Hajnal et la Clique-Stable séparation.

Ensuite, le théorème fort des graphes parfaits nous incite a utiliser son résultat de décomposition : tout graphe de Berge est soit dans une classe dite basique, soit il admet une décomposition répertoriée. Cependant, la décomposition dite balanced skew partition est connue pour être difficile à manipuler. On s’intéressera à la construction un CS-séparateur de taille O(n^2) dans les graphes de Berge qui n’ont justement pas de balanced skew partition, et donc se décomposent par 2-join (grâce aux résultats de Chudnovsky, Trotignon, Trunck, et Vuskovic).

Travail en collaboration avec Nicolas Bousquet, Stéphan Thomassé et Théophile Trunck.

Un matroïde - mot dérivé de "matrice" - peut être défini comme une structure combinatoire obtenue en retenant les principales propriétés ensemblistes de la dépendance linéaire dans les espaces vectoriels. Un matroïde est ainsi naturellement associé à un ensemble fini de points, ou à un ensemble fini (arrangement) d'hyperplans. Cependant les propriétés définissant les matroïdes ne caractérisent pas les espaces vectoriels : les matroïdes constituent une classe d'objets beaucoup plus vaste. Alors qu'un matroïde capture les relations d'incidence (alignement, coplanarité, etc.) entre des points de l'espace, un matroïde orienté est une structure combinatoire proche qui capture - en plus - les relations de convexité entre ces points, en prenant cette fois en compte les signes dans les relations de dépendance linéaire. Les matroïdes orientés forment ainsi un langage naturel pour décrire les positions relatives de points dans l'espace, ou de faces délimitées par des hyperplans, les relations entre cycles et cocyles dans les graphes orientés, etc Un théorème majeur indique que les propriétés définissant les matroïdes orientés caractérisent cette fois des objets topologiques : les arrangements de pseudohyperplans. Ce cours d'introduction (en deux parties, d'environ 2 heures au total) présentera les matroïdes orientés dans leur généralité (combinatoire et topologique) et dans leur rôle en termes de configurations de points, d'arrangements d'hyperplans, de programmation linéaire, de polynôme de Tutte, et de graphes orientés. Il ne reposera que sur des notions classiques d'algèbre linéaire et de théorie des graphes.

The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks for a graph G, non-negative integers d,k and a function \delta:V(G)->{1,...,d}, whether it is possible to obtain a connected graph G' from G such that the degree of v is \delta(v) for any vertex v by at most k edge editing operations. As the problem is NP-complete even if \delta(v)=2, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d+k. For the special case \delta(v)=d, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only.

The on-line graph coloring problem is modeled by a game between two players: Presenter and Algorithm. Presenter constructs a graph of some fixed class presenting new vertices one by one, while Algorithm colors the vertices right after they are presented without the possibility of changing the color afterwards. The goal of Algorithm is to use as few colors as possible, while Presenter tries to force Algorithm to use many colors. Any game of this kind gives rise to a new class of graphs, so-called game graphs, which "encode" strategies of Presenter in the game. The number of colors that Algorithm is forced to use playing against such a strategy is equal to the chromatic number of the corresponding game graph.

On the one hand, the game graphs of appropriately chosen on-line coloring games can be naturally represented as intersection graphs of geometric objects. This allows us to construct geometric intersection graphs with large chromatic number based on Presenter's strategies forcing the use of many colors. The first result obtained with the help of this approach is a construction of triangle-free segment intersection graphs with large chromatic number due to Pawlik et al. On the other hand, many natural geometric intersection graphs are game graphs or can be decomposed into game graphs of appropriately defined on-line coloring games. This allows us to use on-line coloring algorithms for bounding the chromatic number of geometric intersection graphs. This way we can obtain upper bounds of the form O((log log n)^c) on the chromatic number of rectangle overlap graphs or subtree overlap graphs with n vertices and bounded clique number.

I will present several applications of the on-line method in providing lower and upper bounds on the chromatic number of geometric intersection graphs with bounded clique number, including the above-mentioned construction of Pawlik et al. and a double logarithmic bound for rectangle overlap graphs.

Je vais montrer quelques idées simples mais efficaces qui ont conduit à l'amélioration de la garantie d'approximation pour le problème du voyageur commerce avec des métriques qui sont les longueurs de plus court chemins de graphes (garantie d'approximation 1.4, résultat 2012 commun avec Jens Vygen), et de la 'version chemin' avec des métriques quelconques (garantie 1.6, 2013). Partant du résultat classique de Christofides, les nouvelles méthodes utilisent une combinaison de résultats polyédraux et combinatoires classiques (intersections de matroïdes) et nouveaux (théorèmes structurels sur les graphes 2-connexes) concernant les couplages (matchings) et leurs généralisations, les "T-joins", très proches du problème du postier. Les arguments de convexité sont simplifiés par un language de probas élémentaires.

Un graphe est 2-track si l'ensemble de ses aretes est l'union de 2 graphes d'intervalle.
Avec Daniel Gonçalves, on a montré il y a quelques années que déterminer si un graphe planaire de maille 6 est 2-track est NP-complet. Aussi, tous les graphes planaires de maille 10 sont 2-track.
Cette année, on sait en plus que pour tout g fixé, on a une des deux possibilités suivantes:
- déterminer si un graphe planaire de maille g est 2-track est NP-complet.
- tous les graphes planaires de maille g sont 2-track.
La preuve utilise des techniques de réduction polynomial, du déchargement, et aussi un ordre ad-hoc sur les graphes.

Ce résultat fait partie d'un papier en préparation avec Aquiles Braga de Queiroz, Valentin Garnero, Daniel Gonçalves et Guillame Guégan.

Récemment plusieurs méta-théorèmes algorithmiques sur la kernelization ont été proposés dans le contexte des graphes peu denses (genre borné) -- voir par exemple Bodlaender et al. [FOCS'09]. Ces résultats garantissent l'existence de noyaux linéaires (ou polynomiaux) sur les graphes peu denses pour des problèmes satisfaisant des conditions génériques. La généralité de ces résultats a pour conséquence qu'ils ne portent que sur l'existence de tels noyaux. Nous montrons comment en utilisant la programmation dynamique, il est possible pour certains problèmes de rendre ces noyaux constructifs et d'obtenir une analyse explicite des constantes impliquées dans la taille des noyaux obtenus. Parmi ces problèmes, nous parlerons de r-dominating set, r-Scattered Set, Planar-F-Deletion et Planar-F-Packing sur différentes classes de graphes.

On dit qu'une classe de graphes satisfait la propriété d'Erdos-Hajnal si tout graphe de la classe a une clique ou un stable de taille polynomiale. En particulier toute classe dont le nombre chromatique est borné par un polynôme en la clique maximale a la propriété d'Erdos-Hajnal. Erdos et Hajnal ont conjecturé en 1989 que toute classe sans copie induite de H (quelque soit H) avait la propriété d'Erdos-Hajnal. La conjecture est toujours ouverte pour les graphes sans chemins induits de longueur au moins k (pour k au moins 4). Mais aussi pour les graphes sans cycles induits de longueur au moins k (pour k au moins 5). Nous montrerons dans cette présentation que, pour tout k, si on interdit les chemins de longueur au moins k et leur complémentaire, puis les cycles de longueur au moins k et leur complémentaire, la propriété d'Erdos Hajnal est vérifiée.

M.A. Henning and A. Yeo conjectured in [1] that a digraph of minimum out-degree at least 4, contains 2 vertex disjoint cycles of different lengths. In this paper we prove this conjecture. The main tool, is a new result (to our knowledge) asserting that in a digraph D of minimum out-degree at least 4, there exist 2 vertex-disjoint cycles C1 and C2, a path P1 from a vertex x of C1 to a vertex z not in V(C1) ∪ V(C2), and a path P2 from a vertex y of C2 to z, such that V(P1) ∩ (V(C1) ∪ V(C2)) = {x}, V(P2) ∩ (V(C1) ∪ V (C2)) = {y}, and V(P1) ∩ V(P2) = {z}. In the last section, a conjecture will be proposed.

[1] M. A. Henning, A. Yeo, Vertex disjoint cycles of different length in digraphs, SIAM J. Discrete Math, 26(2) (2012), 687-694.

On retrouve dans la littérature plusieurs caractérisations différentes du polynôme de Tutte d'un graphe. Tutte l'a notamment défini grâce à une notion d'activité basée sur un étiquetage ordonné des arêtes. Plus tard, Bernardi a donné une notion non équivalente de l'activité en plongeant le graphe dans une surface. On verra que d'autres notions d'activité peuvent être ainsi imaginées et qu'elles se regroupent toutes en une seule et même définition. On en profitera pour comprendre macroscopiquement le lien entre les différentes caractérisations du polynôme de Tutte.

We can generalise the well known class of interval graphs in three ways, each one refining the preceding: t-interval graphs, t-interval local graphs and t-track graphs

We note i(G) for the smallest number such that G admits a t-interval representation, and analog parameters t(G) and il(G) for t-track and t-interval local representations. We have the inequalities i(G) <= il(G) <= t(G).

For planar graphs it is known that i(G)<=3 and t(G)<=4. I will present our work on those three parameters, and will explain the proofs of two of our results : that for a planar graph G we have il(G)<=3 and that deciding whether i(G)<=2 (resp. il(G)<=2) is NP-complete for the class of planar graphs. The former result answer a recent question of Knauer and Ueckerdt, the latter a 1984 question of West and Shmoys.

This is joint work with Aquiles Braga de Queiroz, Valentin Garnero, Daniel Gonçalves and Pascal Ochem.

Fixed-parameter algorithms, approximation algorithms and moderately exponential algorithms are three major approaches to algorithms design. While each of them being very active in its own, there is an increasing attention to the connection between these different frameworks. In particular, whether Independent Set would be better approximable once allowed with subexponential-time or FPT-time is a central question. Recently, three independent results appeared regarding this question, implying negative answer toward the conjecture. They state that, for every 0 < r < 1, there is no r-approximation which runs in better than certain subexponential-function time. We outline the results in these papers and overview the important concepts used in these results.

Bounded spectrum list coloring is an intermediary notion between standard coloring and list coloring. We say that a graph is (k,p)-choosable if for every assignment L of k colors to each vertex that involves at most p different colors on the whole, the graph is L-colorable. This corresponds to standard coloring when k=p, and to list coloring when p is infinite. Does there exist some function C such that every (k,p)-choosable graph is C(k,p)-choosable? If so, what does it look like? This talk is meant as a discussion of counter-intuitive facts on bounded spectrum list coloring, including our recent result answering a 2005 question of Kral and Sgall.

This is joint work with Ross Kang (Utrecht University).

The dichromatic number of a digraph D is the smallest k such that the vertex set of D can be partitioned into k sets each of which induces an acyclic subdigraph. We will survey some results which provide evidence that this digraph invariant is a natural extension of the notion of the chromatic number of (undirected) graphs. In particular, we will show analogs of Brooks' Theorem and Gallai's Theorem for digraphs, discuss some extremal resultsand planar digraphs.

This is joint work with Bojan Mohar.

AlGCo : algorithmes, graphes et combinatoire

Responsable : Emeric Gioan

Département Informatique - LIRMM