AlGCo : algorithmes, graphes et combinatoire
Séminaire
Retour à la page d'accueil du séminaire Archives : 2024-... | 2021-2024 | 2018-2021 | 2014-2018 | 2013-2014 | 2012-2013 | 2011-2012 | 2010-2011 | 2009-2010 | 2008-2009 | 2007-2008 | 2006-2007 | 2005-2006 | 2004-2005 | 2003-2004 | 2002-2003 | 2001-2002 Exposés 2014/2015, 2015/2016, 2016/2017, 2017/2018
Présentation de quelques articles de WG 2018.
We study the class L of link types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4. We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimal number of crossings or edges in a projection of L ∈ L. Further, we enumerate (both exactly and asymptotically) all connected K4-minor-free link diagrams, all minimal connected K4-minor-free link diagrams, and all K4-minor-free diagrams of the unknot. Joint work with J. Rué and V. Velona
In Defective Coloring we are given a graph G=(V,E) and two integers \chi_d, \Delta^∗ and are asked if we can partition V into \chi_d color classes, so that each class induces a graph of maximum degree \Delta^∗. We present two sets of recent results regarding the complexity of the problem: first when the input graph is restricted to belong to some specific classes (split graphs, cographs and trivially perfect graphs in particular); second, when the problem is parameterized by the treewidth, pathwidth, tree-depth, or feedback vertex set of the input graph. This is a joint work with Michael Lampis and Valia Mitsou.
A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Tournaments form a mathematically rich subclass of directed graphs with interesting structural and algorithmic properties. In this talk, we explore the classical and parameterized complexity of both ATT and ACT. In particular, we focus on the NP-completeness of ATT and we give a vertex-linear kernel for this problem. This is joint work with S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh and M. Zehavi.
We are concerned with efficiently coloring sparse graphs in
I will recall the definition of homomorphisms of signed graphs.
Planar graphs are the graphs with Dushnik-Miller dimension at most three (W. Schnyder, Planar graphs and poset dimension, Order 5, 323-343, 1989). Consider the intersection graph of interior disjoint axis-parallel rectangles in the plane. It is known that if at most three rectangles intersect on a point, then this intersection graph is planar, that is it has Dushnik-Miller dimension at most three. During this talk we will this result, from the plane to $R^d$, by considering tilings of $R^d$ with axis parallel boxes, where at most $d+1$ boxes intersect on a point. Such tilings induce simplicial complexes and we will show that those simplicial complexes have Dushnik-Miller dimension at most $d+1$. This is a joint work with M.C. Francis.
In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsky et al [ESA 2013] proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a $c$-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most $c$, where $c \geq 1$ is a fixed integer. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that Vertex Cover admits a polynomial kernel on general graphs for any integer $c \geq 1$, and that Dominating Set does not for any integer $c \geq 2$ even on degenerate graphs, unless $\text{NP} \subseteq \text{coNP}/\text{poly}$. For the positive result, we build on the techniques of Jansen and Bodlaender [STACS 2011], and for the negative result we use a polynomial parameter transformation for $c\geq 3$ and an or-cross-composition for $c = 2$. As existing results imply that Dominating Set admits a polynomial kernel on degenerate graphs for $c = 1$, our result provides a dichotomy about the existence of polynomial kernels for Dominating Set on degenerate graphs with this parameter. This is a joint work with Ignasi Sau.
In an attempt to solve the Four Color Problem, Tait conjectured that every planar cubic 3-edge-connected graph is Hamiltonian. Once this statement was disproved, several other related questions of the type "every bipartite (planar) 3-edge connected cubic graph is Hamiltonian", emerged. On the other hand the conjecture of Neumann-Lara asserting that every planar oriented graph can be vertex-partitioned into two acyclic sets, can be seen as a directed version of Tait's conjecture. In this talk we explain how all these conjectures together with other similar questions fit in the same framework related to cuts in matchings. We show then a construction of 3-edge connected oriented graph satisfying the property that for every even subgraph E, the graph obtained by contracting the edges of E is not strongly connected. This disproves a recent conjecture of Hochstättler. At the end we will provide experimental evidence for Neumann-Lara's conjecture and discuss on tools that might be helpful to search for counterexamples. Joint work with Kolja Knauer.
Given a (possibly infinite) fixed set of graphs \F, we say that a graph G overlays \F on a hypergraph H if both G and H have the same set of vertices, and if for every hyperedge S of H, the subgraph of G induced by S contains a graph from \F as a spanning subgraph. The \F-Overlay Problem asks, given a hypergraph H, to find a graph G which \F-overlays H, and, if such a graph exists, to find one with the minimum number of edges. We will first discuss the possible applications of this problem, e.g. structural biology, network design or hypergraph drawing. We will then completely characterize the complexity of the \F-Overlay Problem (P or NP-hard) depending on the family \F. Finally, for the NP-hard cases, we will also give some sufficient conditions on \F leading to either FPT or W[1]-hard problems, when parameterized by the number of edges of the graph sought.
The concept of power domination emerged from the problem of monitoring electrical systems. Given a graph G and a set S \subseteq V(G), a set M of monitored vertices is built as follows: at first, M contains only the vertices of S and their direct neighbors, and then each time a vertex in M has exactly one neighbor not in M, this neighbor is added to M.
Joint work with N. Alon (Tel-Aviv U.) and J. Bang-Jensen (South-Denmark U.). We study vertex colourings of digraphs so that no out-neighbourhood is monochromatic and call such a colouring an out-colouring. The problem of deciding whether a given digraph has an out-colouring with only two colours (called a 2-out-colouring) is NP-complete. We prove that, except for the Paley tournament P7 , every semicomplete digraph of minimum out-degree at
Pour un graphe H fixé, le problème H-coloring
Cet exposé est la suite de l'exposé ci-dessous. Il sera possible de suivre celui-là sans avoir suivi le précédent. *********** The L-intersection graphs are the graphs that have a representation as intersection graphs of axis parallel shapes in the plane. A subfamily of these graphs are {L, |, -}-contact graphs which are the contact graphs of axis parallel L, |, and - shapes in the plane. We prove here two results that were conjectured by Chaplick and Ueckerdt in 2013. We show that planar graphs are L-intersection graphs, and that triangle-free planar graphs are {L, |, -}-contact graphs. These results are obtained by a new and simple decomposition technique for 4-connected triangulations. Our results also provide a much simpler proof of the known fact that planar graphs are segment intersection graphs.
Given a tournament T and a positive integer k, the C_3-Packing-T asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly C_3-Packing-T did not receive a lot of attention in the literature. We show that it does not admit a PTAS unless P=NP, even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. Focusing on sparse tournaments we provide a (1+6/(c-1)) approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have “length” at least c. Concerning kernelization, we show that C_3-Packing-T admits a kernel with O(m) vertices, where m is the size of a given feedback arc set. In particular, we derive a O(k) vertices kernel for C_3-Packing-T when restricted to sparse instances. On the negative size, we show that C_3-Packing-T does not admit a kernel of (total bit) size O(k^{2-epsilon}) unless NP is a subset of coNP / Poly. The existence of a kernel in O(k) vertices for C_3-Packing-T remains an open question. Joint work with Stéphane Bessy and Jocelyn Thiebaut.
For two positive integers $k$ and $\ell$, a $(k \times \ell)$-spindle is the union of $k$ pairwise internally vertex-disjoint directed paths with $\ell$ arcs between two vertices $u$ and $v$. In this talk we are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed $\ell \geq 1$, finding the largest $k$ such that an input digraph $G$ contains a subdivision of a $(k \times \ell)$-spindle is polynomial-time solvable if $\ell \leq 3$, and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and prove several positive and negative results. Joint work with Júlio Araújo, Victor A. Campos, Ana Karolinna Maia,
En collaboration avec Lucas Isenmann et Claire Pennarun The L-intersection graphs are the graphs that have a representation as intersection graphs of axis parallel shapes in the plane. A subfamily of these graphs are {L, |, -}-contact graphs which are the contact graphs of axis parallel L, |, and - shapes in the plane. We prove here two results that were conjectured by Chaplick and Ueckerdt in 2013. We show that planar graphs are L-intersection graphs, and that triangle-free planar graphs are {L, |, -}-contact graphs. These results are obtained by a new and simple decomposition technique for 4-connected triangulations. Our results also provide a much simpler proof of the known fact that planar graphs are segment intersection graphs.
We consider variants of a pursuit and evasion game studied independently by Britnell and Wildon as well as Haslegrave. In their game, a cat has to catch an invisible mouse that moves along the edges of some graph $G$. In one of our versions, the cat receives partial information about its distance to the mouse, and we show that the cat has a winning strategy if and only if $G$ is a forest. In a second version, we study how well the cat can localize the mouse. The results are joint work with Moritz Schneider and Dennis Dayanikli
TBA
In the talk I will discuss two related notions with regards to graph compression.
TBA
TBA
A very nice result of B\'ar\'any and Lehel asserts that every finite subset $X$ or $\mathbb R^d$ can be covered by $f(d)$ $X$-boxes (i.e. each box has two antipodal points in $X$). As shown by Gy\'arf\'as and P\'alv\H{o}lgyi this result would follow from the following conjecture : If a tournament admits a partition of its arc set into $k$ quasi orders, then its domination number is bounded in terms of $k$. This question is in turn implied by the Erd\H{o}s-Sands-Sauer-Woodrow conjecture : If the arcs of a tournament $T$ are colored with $k$ colors, there is a set $X$ of at most $g(k)$ vertices such that for every vertex $v$ of $T$, there is a monochromatic path from $X$ to $v$. We give a short proof of this statement. We moreover show that the general Sands-Sauer-Woodrow conjecture (which as a special case implies the stable marriage theorem) is valid for directed graphs with bounded stability number. This conjecture remains however open.
Abstract: The node search game against a lazy/agile (invisible) robber has been introduced as a search-game analogue of the graph parameters of treewidth/pathwidth. In the “connected” variants of the above two games, we additionally demand that, at each moment of the search, the “clean” territories are connected. The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we also demand that the clean territories are progressively increasing) of this game, corresponds to the graph parameter of connected pathwidth and has been shown that its value cannot be more than the double (asymptotically) of its non-connected counterpart. This implied that the “price of connectivity” is bounded by 2 for the case of an agile robber. In this paper we initiate the study of the connected variant of this search game where the robber is lazy, in the sense that he/she moves only when the searchers strategy threatens the location that he/she currently occupies. We introduce two alternative graph-theoretical formulations of its monotone variant, one in terms of (connected) layouts and one on terms of (connected) tree decompositions, leading to the graph parameter of connected treewidth. For this “lazy-robber” variant we prove that there is no bound in the price of connectivity, which comes in contrast to the case of an agile robber. We also observe that the corresponding parameter, i.e. connected treewidth, is closed under contractions and we study the contraction-obstruction set class of the class of graphs with connected treewidth at most k. It follows that this set is infinite for every k ≥ 2. We also provide a complete characterisation for the case where k = 2. This is joint work with Isolde Adler and Dimitrios M. Thilikos.
A mixed graph is a graph which may contain both (unoriented) edges
Réunion de lancement de l'ANR DeMoGraph
Nous commencerons par détailler la construction classique des cartes Eulériennes planaires et par proposer une variante de cette construction.
TD-Delaunay graphs, where TD stands for triangle-distance, are obtained from a variation of Delaunay triangulation consisting in replacing circles by homothetic triangles. It was noticed that every triangulation is the TD-Delaunay graph of a set of points in R^2, and conversely. It seems natural to study the generalization of this property in higher dimensions. Such a generalization is obtained by replacing equilateral triangles by regular simplexes in dimension R^d. The abstract simplicial complexes obtained from a TD-Delaunay complex in dimension d are of Dushnik-Miller dimension d + 1. The converse holds for d = 2 and 3 and it was conjectured to hold for larger d. Our work with Daniel Gonçalves is to disprove the conjecture already for d = 4.
A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both ver- tices is the same as their distance in the original graph. The Distance- Hereditary Vertex Deletion problem asks, given a graph G on n vertices and an integer k, whether there is a set S of at most k vertices in G such that G − S is distance-hereditary. This problem is impor- tant due to its connection to the graph parameter rank-width; distance- hereditary graphs are exactly graphs of rank-width at most 1. Eiben, Ganian, and Kwon (MFCS’ 16) proved that Distance-Hereditary Ver- tex Deletion can be solved in time 2O(k)nO(1), and asked whether it admits a polynomial kernelization. We show that this problem admits a polynomial kernel, answering this question positively. For this, we use a similar idea for obtaining an approximate solution for Chordal Ver- tex Deletion due to Jansen and Pilipczuk (SODA’ 17) to obtain an approximate solution with O(k3 log n) vertices when the problem is a Yes-instance, and we exploit the structure of split decompositions of distance-hereditary graphs to reduce the total size.
It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.
Un hypergraphe est une paire H=(V,A) où V est un ensemble de sommets et A est un ensemble de sous-ensembles non vides de V. Une approche classique pour représenter graphiquement un hypergraphe consiste à dessiner les sommets sous forme de points et les hyperarêtes sous forme de polygones. Le principal enjeu consiste alors à trouver un positionnement des sommets tel que les intersections des polygones dans le plan ne contienne que les sommets des hyperarêtes correspondant à ces polygones. La notion d'hypergraphe planaire a été introduite pour caractériser les hypergraphes pouvant être dessinés de cette façon. Plusieurs définitions formelles ont été proposées. La plus générale est basée sur la notion de support. Un graphe support d'un hypergraphe H=(V,A) est un graphe G=(V,E) dans lequel les sous-graphes induits par les sommets de chaque hyperarête sont connexes. Un hypergraphe est dit planaire si et seulement si il possède un graphe support planaire. Dans cet exposé, je présenterai plusieurs problèmes résolus et un ouvert liés à la planarité des hypergraphes. Plusieurs de ces résultats reposent sur une nouvelle définition des composantes bi-connexes d'un hypergraphe.
joint work with D. Rautenbach (Ulm University, Germany) Pour une séquence de degrés d: d1 >= d2 >= ... >= dn, on définit Xmax(d) (resp. Xmin(d)) le plus grand (resp. plus petit) nombre chromatique d'un graphe de séquence de degrés d. Après avoir motivé l'étude de ces invariants (d'un point de vue théorique ainsi qu'applicatif -hum...-), puis présenté les grands résultats connus sur les réalisations de séquences de degrés, je donnerai les résultats théoriques et algorithmiques que nous avons obtenus pour borner ou calculer Xmax et Xmin.
I will present six interrelated general expressions of the Tutte polynomial of a graph, that are available as soon as the set of edges is linearly ordered, and that witness combinatorial properties of such a graph: - the classical enumeration of spanning tree activities; - its refinement into a four variable expression in terms of subset activities (that corresponds to the classical partition of the set of edge subsets into boolean intervals); - the enumeration of orientation-activities for directed graphs; - its refinement into a four variable expression in terms of subset orientation-activities (that corresponds to the partition of the set of orientations into active partition reversal classes); - the convolution formula for the Tutte polynomial (that does not need the graph to be ordered); - and an expression of the Tutte polynomial using only beta invariants of minors (that refines the above expressions). I will mention that these expressions are all interrelated by the canonical active bijection between spanning trees and orientations, subject of a long-term joint work with Michel Las Vergnas.
As a generalization of proper colouring, we study vertex partitions of graphs into some graphs with particular properties, in particular independent sets, forests and forests with bounded degree. Proper colourings correspond to partitions into independent sets. We will see some sufficient conditions for sparse graphs to admit such partitions. In particular, every planar graph of girth at least 4 admits a partition into a forest and a forest of maximum degree at most 5, and every planar graph of girth at least 7, 8 and 10 admits a partition into an independent set and a forest of maximum degree at most 5, 3 and 2 respectively.
In the multicoloring problem, also known as (a:b) or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the b=1 case) is equivalent to finding a homomorphism to the Kneser graph with parameters a and b. It is tightly connected with the fractional chromatic number, and has multiple applications within computer science. We study the complexity of determining whether a graph has an (a:b)-coloring. Nederlof showed in 2008 a $(b+1)^n n^{O(1)}$-time algorithm for (a:b)-coloring. Our main result is that this is essentially optimal: there is no algorithm with running time $2^{o(log b)⋅n}$ unless the ETH fails. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström (1965), which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we also prove that the existing algorithms for the r-monomial detection problem are optimal under ETH. This is joint work with Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała and Marcin Wrochna (University of Warsaw).
Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most $2^{O(k^3 log k)}$. For our proof, we introduce the concept of a lean ordering that can be seen as the analogue of lean decompositions defined by Thomas in [A Menger-like property of tree-width: The finite case, J. Comb. Theory, Ser. B, 48(1):67–76, 1990] for the case of treewidth. As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time $2^{O(k^2 log k)} · n$, where k is the optimum width and n is the number of vertices. While being slower by a log k-factor in the exponent than the fastest known algorithm, given by Thilikos, Bodlaender, and Serna in [Cutwidth I: A linear time fixed parameter algorithm, J. Algorithms, 56(1):1–24, 2005] and [Cutwidth II: Algorithms for partial w-trees of bounded degree, J. Algorithms, 56(1):25–49, 2005], our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts. Joined work with Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, and Marcin Wrochna
Orthology relations between genes are an important part of comparaitve genomics, and a plethora of methods have been designed to infer these relations. We give the first polynomial algorithm to decide whether a partial set C of orthology/paralogy relations is consistent, even when the species tree is unknown. We also investigate a biologically meaningful optimization version of these problems, in which we wish to minimize the number of duplication events; unfortunately, we show that all these optimization problems are NP-hard and are unlikely to have good polynomial time approximation algorithms.
Dans cet exposé on fait un tour d'horizon rapide sur les outils existants pour prouver des résultats d'inapproximabilité. On a d'un côté les gap réductions, l'outil "idéal" puisque sa définition est très naturelle et qu'il permet d'obtenir des résultats forts. En effet, les nombreux résultats existants fournissent un large catalogue de problèmes pour lesquels D'un autre côté on trouve les "approximation preserving reductions". La difficulté est que derrière cette expression se cache un ensemble important de réductions (strict, S, L, E, A, AP, PTAS ..), et qu'il est donc difficile à première vue de choisir quelle réduction utiliser (en plus du problème source à choisir!). Cependant, il se trouve que certaines de ces réductions ont été introduites dans le cadre de la complexité structurelle, c'est à dire pour montrer qu'un problème, parfois artificiellement construit, est complet pour une certaine classe. Ainsi, en pratique (typiquement lorsque l'on cherche à montrer qu'un problème n'admet pas de PTAS), il *semble* que beaucoup de ces réductions ne soient pas utilisées, et que l'on cherche simplement à construire une réduction vérifiant une certaine condition suffisante plus naturelle que les définitions des réductions précédentes. Nous parlerons de ces conditions suffisantes, et illustrerons à travers les preuves (simples) des résultats suivants : Nb : cet exposé n'est pas un exposé de recherche, et le niveau technique se veut faible.
We study parameters of geodetic convexity for graph classes defined by restrictions concerning short induced paths. We show that computing the geodetic hull number of a given $P_9$-free graph is NP-hard. Similarly, we show that computing the geodetic interval number of a given $P_5$-free graph is NP-hard. On the positive side, we identify several graph classes for which the geodetic hull number can be computed efficiently.
A set $Z$ of vertices of a graph $G$ is a zero forcing set of $G$ if The zero forcing number $Z(G)$, defined as the minimum order of a zero forcing set of $G$, was proposed as an upper bound of the corank of matrices associated with $G$, and was also considered in connection with quantum physics and logic circuits. In view of the computational hardness of the zero forcing number, upper and lower bounds are of interest. We discuss such bounds and some of the corresponding extremal graphs. Joint work with M. Gentner, L.D. Penso, and U.S. Souza.
A graph of size $n$ is $\epsilon$-far from having a property P if one
A digraph is semicomplete if it has no pair of non-adjacent vertices.
The “classical” Shannon switching game is a combinatorial game invented by C. Shannon in the 1950’s. The game was completely solved by A. Lehman, shortly after, in what is considered the first application of matroid theory. In the middle 1980’s Y. O. Hamidoune and M. Las Vergnas studied and solved directed versions of the game for graphs considering their generalization to oriented matroids. Recently with some colleagues and students of Informatics we made some proptotypes of computational implementations of the games. We will do a brief review of the main results and conjectures concerning the directed case. Reference:
A graph is equimatchable if all of its maximal matchings have the same size. In this talk, I will present some recent results on equimatchable graphs such as forbidden subgraphs, stable equimatchable graphs, and the characterization of claw-free equimatchable graphs. I will then discuss about some new research directions.
TBA
Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of a set of input words. The Shortest Cyclic Cover of Strings (SCCS) problem asks, instead of a single linear superstring, for a set of cyclic strings that contain the words as substrings and whose sum of lengths is minimal. SCCS is used as a crucial step in polynomial time approximation algorithms for the notably hard Shortest Superstring problem, but it is solved in cubic time. The cyclic strings are then cut and merged to build a linear superstring. Building on recent theoretical work, I will present you a linear time algorithm for solving SCCS based on a Eulerian graph (the Superstring Graph) that captures all greedy solutions in linear space.
A graph H is an immersion of a graph G if H can be obtained by lifting incident edges of some subgraph of G. We prove that there is a polynomial function f:N×N→N, such that if H is a connected planar subcubic graph on h>0 edges, G is a graph, and k is a non-negative integer, then either G contains k vertex/edge-disjoint subgraphs, each containing H as an immersion, or G contains a set F of f(k,h) vertices/edges such that G∖F does not contain H as an immersion. This is join work with Archontia Giannopoulou (University of Warsaw), O-joung Kwon (Hungarian Academy of Sciences) and Dimitrios M. Thilikos (LIRMM). A preprint is online: http://arxiv.org/abs/1602.04042 .
Treewidth is undoubtedly one of the most fundamental parameters in modern graph theory and algorithms. Its theoretical importance is demonstrated by its crucial role in the proof of the Graph Minor theorem by Roberston and Seymour, while its algorithmic relevance is certified, for instance, by Courcelle's theorem. In this talk we focus on couting the number of labeled graphs on $n$ vertices and treewidth $k$, which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. Using a construction that exploits the fact that a graph has treewidth at most $k$ if and only if it is a partial $k$-tree, we show that $$\left(c \cdot \frac{k}{\log k} \cdot 2^k \cdot n\right)^n \cdot 2^{-k(k+1)/2} \cdot k^{-2k-2}\ \leq\ T_{n,k}\ \leq\ \left(k \cdot 2^k \cdot n\right)^n \cdot 2^{-k(k+1)/2} \cdot k^{-k},$$ for some explicit constant $c > 0$. Our results also apply to graphs of pathwidth at most $k$. Joint work with Marc Noy and Ignasi Sau.
Given n subspaces of a finite-dimensional vector space over a fixed finite field 𝔽, we wish to find a linear layout V1,V2,…,Vn of the subspaces such that dim((V1+V2+⋯+Vi)∩(Vi+1+⋯+Vn))≤k for all i, such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory and computing the path-width of an 𝔽-represented matroid in matroid theory. We present a fixed-parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over 𝔽. As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most k for an input 𝔽-represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously. It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width, a theorem by Geelen, Gerards, and Whittle (2002) implies that for each fixed finite field 𝔽, there are finitely many forbidden 𝔽-representable minors for the class of matroids of path-width at most k. An algorithm by Hliněný (2006) can detect a minor in an input 𝔽-represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.
Locally transitive tournaments (LTT) are reorientations of the transitive tournament. Despite being a simple class to describe, they have rich and deep combinatorics. Uniform oriented matroids (UOM) can be understood as collections of LTT. I will present a new characterization of LTT which has a deep impact on the theory of UOMs:
TBA
We say that two words u and v are abelian equivalent if they have the same number of occurrences of each letter (i.e., they are permutations or anagrams). I will define what it means to avoid a pattern in the abelian sense. The interest in this topic is due to Erdös asking whether the pattern AA can be avoided in the abelian sense by an infinite words over 4 letters (the answer is yes). We obtain that every binary pattern of size at least 16 can be avoided by an infinite binary word.
The Barat-Thomassen conjecture asserts that for every tree T on m edges, there exists a constant k such that every k-edge-connected graph with size divisible by m can be edge-partitioned into copies of T . The conjecture has been verified when T is a path or when T has diameter at most 4. In the talk, I will sketch a recent proof of the conjecture. This is joint work with J. Bensmail, T.-N. Le, M. Merker and S. Thomassé.
(English Below) En collaboration avec Michal Pilipczuk (MIMUW, Warsaw). Un digraphe $D = (V,E)$ est dit \emph{semi-complet} s'il est simple (pas de self-loop, pas de multi-edge) et que pour tous sommets $u,v \in V$ différents, l'arc $(u,v)$ ou l'arc $(v,u)$ est présent dans $E$. De plus, $D$ est un \emph{tournoi} si pour tous sommets $u,v \in V$ différents $(u,v)$ et $(v,u)$ ne sont pas simultanément présents. Récemment, Chudnovsky, Fradkin et Seymour ont montré que la relation d'immersion restrainte aux digraphes semi-complets était WQO en utilisant la mesure de largeur associée, appellée \emph{Cutwidth}. Ces notions ont ainsi trouvé un regain d'intérêt. Durant ce séminaire, nous nous intéresserons à la cutwidth, définie de la manière suivante. Etant donné un digraphe $D$, un ordre $\pi$ sur les sommets de $D$ et une position $i \in [n]$, la $i$-ème coupe selon $\pi$ de $D$ est l'ensemble d'arcs de retour $D(\pi,i) = \{(v,u) \in E : u \in \pi[i], v \in V \setminus \pi[i]$, avec $\pi[i]$ représentant les $i$ premiers sommets de $\pi$. La cutwidth de $\pi$ est $ctw(D,\pi) = \max_{i \in [n]} D(\pi,i)$ et la cutwidth de $D$ est $ctw(D) = \min_{\pi} ctw(D,\pi)$. Comme pour de nombreuses mesures de largeur, calculer la cutwidth est NP-Difficile dans le cas général. Nous prouverons que cela reste vrai lorsqu'on se restreint aux semi-complets mais qu'il est possible de calculer la cutwidth d'un tournoi en temps polynomial. A partir de ces résultats, nous montrerons comment approximer la cutwidth d'un semi-complet (de façon non linéaire toutefois) ou comment construire des petits tournois de cutwidth donnée. Nous montrerons aussi que tout tournoi contient un sous-tournoi induit de même cutwidth $c$ et de taille au plus linéaire en $c$. Nous étudierons également des variantes de {\sc Feedback Vertex/Edge Deletion}, à savoir {\sc Cutwidth Vertex Deletion} et {\sc Cutwidth Arc Reversal} (dans le cas restreint des semi-complets). -- A digraph $D = (V,E)$ is \emph{semi-complete} if it is simple (no self-loop, no multi-edge), and that, for all different vertices $u,v \in V$, the arc $(u,v)$or the arc $(v,u)$ is present in $E$. Moreover, $D$ is a \emph{tournament} if for all different vertices $u,v \in V$, $(u,v)$ and $(v,u)$ cannot be simultaneously present. Recently, Chudnovsky, Fradkin and Seymour proved that the immersion relation restricted to semi-complete digraphs is WQO, using the associated width measure called \emph{Cutwidth}. Hence, these notions deserve to be studied. During this seminar, we will focus on cutwidth, defined as follows. Given a digraph $D$, an ordering $\pi$ of the vertices of $D$ and a position $i \in [n]$, the cut at position $i$ of $D$ using $\pi$ is the set of feedback arcs $D(\pi,i) = \{(v,u) \in E : u \in \pi[i], v \in V \setminus \pi[i]$, with $\pi[i]$ being the first $i$ vertices of $\pi$. The cutwidth of $\pi$ is $ctw(D,\pi) = \max_{i \in [n]} D(\pi,i)$ and the cutwidth of $D$ is $ctw(D) = \min_{\pi} ctw(D,\pi)$. As for many width measures, computing the cutwidth is NP-Hard in general. We will prove it remains true even in the semi-complete case, but that computing the cutwidth of a tournament is polynomial. From these results, we will show how to approximate the cutwidth of a semi-complete digraph (in a non-linear manner, however), or how to construct small tournaments with a fixed cutwidth. We will also show that any tournament contains a sub-tournament with same cutwidth $c$ and size at most linear in $c$. Finally, we will study some generalization of {\sc Feedback Vertex/Edge Deletion}, called {\sc Cutwidth Vertex Deletion} and {\sc Cutwidth Arc Reversal} (restricted to semi-complete digraph).
Perfect graphs are graphs for which the chromatic number matches the trivial lower bound consisting in the clique number (and the same holds for every induced subgraph). After the long study that led to the Strong Perfect Graph Theorem, the main open question concerning them is about finding an optimal coloring with a combinatorial algorithm. This is joint work with Maria Chudnovsky, Paul Seymour and Sophie Spirkl.
We consider the complexity of deciding whether a graph admits a vertex partition into two parts R and B such that R is K_3-free and B is P_3-free. We show that the problem is NP-complete for 9 small graph classes, where "small" means that if we take the intersection of any two classes among these nine, the problem becomes trivial because the answer is always yes. Joint work with Marin Bougeret.
En preambule de l'abstract general, je previens qu'il s'agira d'un expose assez vaste et plus long que d'habitude (1h30), et qu'il y aura deux brefs passage type groupe de travail pour poser les questions suivantes aux algorithmiciens de l'equipe, propices pour approfondissements dans le cas particulier des graphes (cf. details dans courriel et article envoyes a l'equipe en octobre) : 1 - On s'interesse aux graphes bipolaires et on en definit une coupe optimale. Combien coute de trouver une coupe orientee de poids minimum, pour une fonction poids sur les aretes positive ou nulle ? Combien coute de trouver une coupe de poids minimum, orientee sauf pour certaines aretes d'un arbre couvrant, pour un poids qui est positif/negatif selon l'orientation de ces aretes ? (je sais repondre polynomialement mais en passant par la programmation lineaire, j'aimerais des solutions en termes de graphes) 2 - On introduit une decomposition des graphes orientes en graphes bipolaires (cycliques ou acycliques) dont les nombres sont des parametres combinatoires classiques. Cela pourrait-il etre utilise en complexite parametree ? Verriez-vous par exemple un probleme facile sur les graphes bipolaires, et resoluble en decomposant un graphe acyclique (ou fortement connexe) en de tels mineurs ? ----------- The active bijection maps any directed graph, resp. signed hyperplane arrangement or oriented matroid, defined on a linearly ordered edge set, resp. ground set, onto one of its spanning trees, resp. bases. It relates all spanning trees to all orientations of a graph, all bases to all reorientations of an hyperplane arrangement or, more generally, an oriented matroid. It preserves activities: for bases in the sense of Tutte, for orientations in the sense of Las Vergnas, yielding a bijective interpretation of the equality of two expressions of the Tutte polynomial. It preserves also some active partitions associated with orientations and bases. It can be mathematically defined in a short way, and can be built, characterized, particularized, or refined in several ways. Notably, we get a bijection between bounded regions (bipolar orientations in the case of a graph) and bases with internal activity one and external activity zero, which can be seen as an advanced refinement of real (pseudo)linear programming. We get a bijection between classes of reorientations and bases, using a decomposition into bounded regions of minors of the primal and the dual, which also has a counterpart for decomposing matroid bases, and yields an expression of the Tutte polynomial using only beta invariants of minors. We also get activity preserving bijections between all reorientations and all subsets (related to a four-variable expression of the Tutte polynomial), between regions and no-broken-circuit subsets (acyclic case), between reorientations with fixed orientations for smallest elements of positive circuits/cocircuits (directed cycles/cocycles) and bases (spanning trees), between increasing trees and permutations (complete graph case), etcetera. It is the subject of a series of papers, joint with Michel Las Vergnas.
In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph G (G may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP was known to be polynomial-time solveable on graphs containing only edges or only arcs. It was known to be fixed-parameter tractable parameterized by the number of edges using a simple argument. In this talk, I'll show that the MCPP parameterized by the number of arcs is also fixed-parameter tractable. The proof uses a well-known result of Marx, O'Sullivan and Razgon on the treewidth of torso graphs with respect to small separators. We obtain a small cut analog of this result, and use it to construct a tree decomposition which, despite not having bounded width, has other properties allowing us to design a fixed-parameter algorithm. I will also discuss structural parameterizations of the MCPP, including treewidth and treedepth.
En 2003, Kühn et Osthus ont prouvé que tout graphe sans petit sommet contient comme mineur une clique de taille exponentiellement grande par rapport à sa maille (càd la taille d'un plus petit cycle). En étendant la notion de maille, nous donnons des conditions alternatives pour qu'un graphe contienne une grande clique comme mineur. Pour tout graphe H, la H-maille d'un graphe G et la taille d'un plus petit sous-graphe de G qui se contracte en H. Cette notion généralise celle de maille qui correspond à la θ_2-maille, où θ_r est le graphe à 2 sommets et r arêtes. Nous montrons que pour tout entier r, les graphes de grand degré minimum contiennent comme mineur des cliques dont l'ordre est une fonction exponentielle de leur θ_r-maille. Ce résultat étend celui de Kühn et Osthus à la notion de H-maille. Nous donnons également des critères de connectivité garantissant la présence d'une telle clique. Ces résultats peuvent être utilisés par exemple pour obtenir des théorèmes de type Erdős-Pósa, ou pour borner la tree-width des graphes excluant certains mineurs. Travail commun avec Dimitris Chatzidimitriou (National and Kapodistrian University of Athens), Ignasi Sau (LIRMM) et Dimitrios M. Thilikos (LIRMM et National and Kapodistrian University of Athens).
The clique number is a trivial lower bound for the chromatic number of a graph. Since Erd\H{o}s showed the existence of graphs with arbitrarily high chromatic number and arbitrarily high girth (so clique number is 2), in general, the chromatic number of a graph cannot be upper bounded by a function of its clique number. A class of graphs is said to be $\chi$-bounded if such a function exists. Vertex-minor and pivot-minors are graph containment properties such as (induced) subgraphs, subdivisions, and minors. Geelen conjectured that for any fixed graph $H$, the class of graphs with no $H$-vertex-minor is $\chi$-bounded. This conjecture was known to be true only for one graph (proved by Dvo\v{r}\'ak and Kr\'al), but recently Chudnovsky, Scott, and Seymour proved it for any cycle. We add another class of graphs for which Geelen's Conjecture is true, namely, fan graphs. We also ask the following question of whether Geelen's Conjecture can be generalized to pivot-minors: for any fixed graph $H$, are the class of graphs with no $H$-pivot-minor $\chi$-bounded? We give some positive evidence to this question by proving that it is true for all cycles, which is a strengthening of the aforementioned result by Chudnovsky, Scott, and Seymour. This result can also be viewed as a partial result of the last open conjecture among the three conjectures made by Gy\'arf\'as' in 1985.
For a positive integer $c$, let $[c] = \{1, \ldots , c\}$. The $c$-Load Coloring problem is as follows: given a graph $G=(V,E)$ and an integer $k$ as parameter, decide whether there exists a coloring $q : V \to [c]$ such that for every $i$ in $[c]$, there are $k$ edges with both endvertices colored $i$ in $q$. This problem was studied when $c = 2$ inter alia for its application in broadcast WDM communication networks. It was known that 2-Load Coloring is NP-complete and has a constant ratio approximation. For this sub-case, we had a kernel with at most $7k$ vertices and a dynamic programming algorithm simple-exponential in treewidth, thus 2-Load Coloring is FPT simple-exponential. During my internship in Royal Holloway, I generalized and improved all these results by obtaining a linear-vertex and linear-edge kernel for c-Load Coloring, $c > 1$ being fixed. To prove this kernel, I described a new obstacle I called overload, and showed how to use the related reduction rules in polynomial time. These results imply that $c$-Load Coloring is FPT simple-exponential and the optimization version of $c$-Load Coloring (where $k$ is to be maximized) has an approximation algorithm with a constant ratio. It is even possible that this problem admits a sub-exponential parametrized algorithm. I proved this complexity for graphs of bounded genus, chordal graphs and $H$-free families, where $H$ is a constant forbidden minor. The team of my internship supervisor and I published a conference paper in the International Symposium on Parameterized and Exact Computation (IPEC 2015).
TBA
A fourientation of a graph is a choice for each edge whether to orient that edge in either direction, leave it unoriented, or biorient it. Fourientations can naturally be viewed as a mixture of graph orientations and subgraphs where unoriented and bioriented edges play the roles of absent and present edges, respectively. The Tutte polynomial is the most general bivariate polynomial associated to a graph which can be defined using the deletion and contraction of edges. I will describe joint work with Sam Hopkins where we investigate properties of cuts and cycles in fourientations which determine classes of fourientations which are enumerated by Tutte polynomial evaluations. Time permitting, I will illustrate how several of these classes relate to algebraic, combinatorial, and geometric topics such as Riemann-Roch theory for graphs, bigraphical arrangements, Lawrence ideals, zonotopal algebras, and the reliability polynomial.
A graph is equimatchable if all of its maximal matchings have the same size. Equimatchable graphs are extensively studied in the literature mainly from structural point of view. In this talk I will talk about, to the best of our knowledge, the fi rst family of forbidden subgraphs of equimatchable graphs. Since equimatchable graphs are not hereditary by defi nition, this task of finding forbidden subgraphs requires the use of structural results from previous works.
TBA
TBA
TBA
A matching $M$ in a graph $G$ is uniquely restricted if there is no matching $M'$ in $G$ that is distinct from $M$ but covers the same vertices as $M$. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs. Joint work with Lucia D. Penso and Uéverton dos Santos Souza.
I will present David Mazières’ “Stellar Consensus Protocol”, a decentralized agreement process. Robustness from this approach to consensus, stems from quorum slices, individual trust decisions made by each node, that together determine system-level quorums. This protocol is a Byzantine agreement which makes no assumptions about the rational behavior of attackers. Unlike prior Byzantine agreement models, which presuppose a unanimously accepted membership list, this protocol enables any node to freely join and promotes organic network growth. Study perspectives will be outlined concerning the quorum slices function which makes an interesting graph structure that is prone for an optimized implementation. A potential application of the protocol as the base for a crypto-currency will also be introduced.
Une décomposition (entière) d'un graphe en triangles est une partition de ses arêtes en triangles. Une décomposition fractionnelle d'un graphe en triangles est une assignation d'un poids positif à chaque triangle du graphe tel que, pour toute arête e, la somme des poids des triangles contenant e est égale à 1. On montre que tout graphe à n sommets de degré minimum au moins 0.9n a une décomposition fractionnelle en triangles. La preuve se fait en partant d'une affectation simple de poids aux triangles, et en l'adaptant pour obtenir une décomposition fractionnelle en triangles.
Nous présentons une méthode bijective générale pour les cartes planaires, basée sur certaines orientations, appliquée ici à deux familles de cartes $d$-angulées pour $d \geq 3$: les $d$-angulations de maille $d$ (tous les cycles ont longueur au moins $d$), et les dissections irréductibles $d$-angulées (où les seuls cycles de longueur $\leq d$ sont les contours de faces internes). Travail en commun avec Olivier Bernardi.
In this talk we consider the Maximum Independent Set problem (MIS) on $B_1$-EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) is the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class $B_k$-EPG denotes EPG-graphs where every path has at most $k$ bends. It was already known that MIS on $B_1$-EPG graphs is NP-complete and admits a $4$-approximation. In this talk we consider the approximability and the fixed parameter tractability of MIS on $B_1$-EPG. We will discuss the conditions guaranteeing the existence of a PTAS, and we will show that MIS is FPT in the standard parameterization on $B_1$-EPG restricted to only three shapes of path. As we know that MIS is W1-hard on $B_2$-EPG, the main open question is the FPT status on general $B_1$-EPG. Travail en commun avec Stéphane Bessy, Daniel Gonçalves et Christophe Paul.
We provide an exposition of the main results of the theory of bidimensionality in parameterized algorithm design. This theory applies to graph problems that are bidimensional in the sense that (i) their solution value is not increasing when we take minors or contractions of the input graph and (ii) their solution value for the (triangulated) $(k\times k)$-grid graph grows as a quadratic function of $k$. Under certain additional conditions, mainly of logical and combinatorial nature, such problems admit sub-exponential parameterized algorithms and linear kernels when their inputs are restricted to certain topologically defined graph classes. We provide all formal definitions and concepts in order to present these results in a rigorous way and in their latest update.
For two integers $r, \ell \geq 0$, a graph $G = (V, E)$ is an $(r,\ell)$-graph if $V$ can be partitioned into $r$ independent sets and $\ell$ cliques. In the parameterized $(r,\ell)$-Vertex Deletion problem, given a graph $G$ and an integer $k$, one has to decide whether at most $k$ vertices can be removed from $G$ to obtain an $(r,\ell)$-graph. This problem is NP-hard if $r+\ell \geq 1$ and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of $(r,\ell)$-Vertex Deletion was known for all values of $(r,\ell)$ except for $(2,1)$, $(1,2)$, and $(2,2)$. We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of $k$. We consider as well the version of $(r,\ell)$-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem. This is joint work with Luerbio Faria, Sulamita Klein, and Ignasi Sau.
Consider a weighted graph G where vertices are points in the plane and edges are line segments. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on G has a competitive ratio of c if the length of the path produced by the algorithm from any vertex s to any vertex t is at most c times the length of the shortest path from s to t in G. If the length of the path is at most c times the Euclidean distance from s to t, we say that the routing algorithm on G has a routing ratio of c.We present an online routing algorithm on the Delaunay triangulation with competitive and routing ratios of 5.90. This improves upon the best known algorithm that has competitive and routing ratio 15.48. The algorithm is a generalization of the deterministic 1-local routing algorithm by Chew on the L1-Delaunay triangulation. When a message follows the routing path produced by our algorithm, its header need only contain the coordinates of s and t. This is an improvement over the currently known competitive routing algorithms on the Delaunay triangulation, for which the header of a message must additionally contain partial sums of distances along the routing path.We also show that the routing ratio of any deterministic k-local algorithm is at least 1.70 for the Delaunay triangulation and 2.70 for the L1-Delaunay triangulation. In the case of the L1-Delaunay triangulation, this implies that even though there exists a path between two points x and y whose length is at most 2.61|[xy]| (where |[xy]| denotes the length of the line segment [xy]), it is not always possible to route a message along a path of length less than 2.70|[xy]|. From these bounds on the routing ratio, we derive lower bounds on the competitive ratio of 1.23 for Delaunay triangulations and 1.12 for L1-Delaunay triangulations. Joint work with Prosenjit Bose, Jean-Lou De Carufel, Ljubomir Perković, and André Van Renssen.
The $k$-restricted edge-connectivity of a graph $G$, denoted by $\lambda_k(G)$, is defined as the minimum size of an edge set whose removal leaves exactly two connected components each containing at least $k$ vertices. This graph invariant, which can be seen as a generalization of a minimum edge-cut, has been extensively studied from a combinatorial point of view. However, very little is known about the complexity of computing $\lambda_k(G)$. Very recently, in the parameterized complexity community the notion of good edge separation of a graph has been defined, which happens to be essentially the same as the $k$-restricted edge-connectivity. Motivated by the relevance of this invariant from both combinatorial and algorithmic points of view, we initiate a systematic study of its computational complexity, with special emphasis on its parameterized complexity for several choices of the parameters. We provide a number of NP-hardness and W[1]-hardness results, as well as FPT-algorithms. This is joint work with Luis P. Montejano.
Let $k,d,\lambda$ be positive integers with $d\ge\lambda$. We investigate the following two questions. What is the maximum positive integer $n$ such that every set of $n$ points in $\mathbb{R}^d$ has a (kneser) transversal $(d-\lambda)$-plane intersecting the convex hulls of all $k$-sets ? What is the minimum positive integer $n$ such that every set of $n$ points in general position in $\mathbb{R}^d$ there is no (kneser) transversal $(d-\lambda)$-plane intersecting the convex hulls of all $k$-sets ? A transversal $(d-\lambda)$-Plane in $\mathbb{R}^d$ is an affine subspace of dimension $d-\lambda$. A kneser transversal $(d-\lambda)$-plane for a set of points $S$ in $\mathbb{R}^d$ is an affine subspace of dimension $d-\lambda$ that goes through $d-\lambda+1$ points of $S$. First question is related with Kneser hypergraph and its chromatic number (when $\lambda=1$, it is equivalent to Kneser's conjecture). We will see how answering first question could give improvements to this problem.
The cyclability of a graph is the maximum integer $k$ for which every $k$ vertices lie on a cycle. The algorithmic version of the problem, given a graph $G$ and a non-negative integer $k,$ decide whether the cyclability of $G$ is at least $k,$ is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by $k,$ is W[1]-hard and that its does not admit a polynomial kernel on planar graphs, unless $NP\subseteq coNP/poly$. On the positive side, we give an FPT algorithm for planar graphs that runs in time $2^{2^{O(k^2\log k)}}\cdot n^2$. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs. The algorithm is based on combinatorial results on linkages and cyclic linkages on planar graphs. Joint work with Petr A. Golovach, Marcin Kamiński, and Spyridon Maniatis.
The main theme of this talk is card games that can be naturally reformulated as well-known graph-theoretic problems. In particular, we will focus on two different games: the game of SET, and the game of UNO. The objective of the former is to form sets of cards that match in a certain sense, while in the latter players need to discard their cards following a matching rule (for more details regarding the rules of the two games please visit the following websites: official website of SET, wikihow: how to play UNO). We will describe connections of the two games with a number of different problems such as Multidimensional Matching, Set Packing, Edge Dominating Set, and Hamiltonian Path. These connections will help us show algorithmic as well as hardness results for variations of both games in the classical and the parameterized sense. The connections described are two-fold as our results will, in several cases, imply progress for the state of the art of the corresponding graph-theoretic problems. This talk will include results from two different publications: "The computational complexity of the game of SET", joint with Michael Lampis, LATIN 2014, and "Parameterized Edge Hamiltonicity", joint with Michael Lampis, Kazuhisa Makino, and Yushi UNO, WG 2014.
Dans cet exposé, nous allons nous intéresser au problème du pompier (firefighter) qui est défini de la manière suivante: initialement un sommet particulier d'un graphe non-orienté est brûlé. À chaque pas de temps, on applique successivement les deux étapes suivantes: 1) Protéger un sommet non-brûlé du graphe, i.e. il ne peut plus brûler par la suite; 2) Tous les sommets non-protégés et adjacents à un sommet brûlé sont brûlés. Le processus se termine lorsque plus aucun nouveau sommet ne peut brûler. Un sommet est alors considéré comme sauvé s'il n'est pas brûlé. L'objectif est de trouver une stratégie de protection telle que le nombre de sommets brûlés à la fin du processus est minimum. Nous considérons ici la version plus générale du problème qui permet de protéger b sommets par étape. Nous présenterons des résultats de complexité paramétrée de ce problème par rapport à des paramètres liés à la structure du graphe. En particulier, nous montrerons que la complexité du problème est directement liée à la largeur linéaire (pathwidth) et au degré maximum du graphe. Résultats obtenus en collaboration avec Janka Chlebíková.
Most of the NP-hard problems are even hard to approximate within some super-constant ratio (Max Clique, Min Indepedent Dominating Set, Min Set Cover etc.). For each of these problems, from the known polytime $\rho(n)$-approximation to the best super-polynomial time exact algorithm, one can ask a continuum of question of the form: for $r < \rho(n)$, what is the best running time of an r-approximation algorithm? In 2013, Chalermsook, Laekhanukit, and Nanongkai answered the question for Max Independent Set/Max Clique, by showing that the previously known $r$-approximation in time $2^{n/r}$ was nearly optimal under standard complexity assumptions. However, for other problems there have been only some upper bounds (by Bourgeois et al. and Cygan et al.) without nearly matching lower bounds. We start to fill this gap by showing that Min Independent Dominating Set, Max Induced Path/Tree/Forest, and Max Minimal Vertex Cover present about the same behavior as Max Independent Set in being $\rho(r)$-approximable in time $2^{n/r}$ but not with a significantly better time. We also present some upper bounds for Min Asymmetric TSP and Max Grundy Coloring. It is still unknown whether or not these two problems are polytime constant-approximable. We conclude with some words concerning Min Set Cover. This is joint work with Michael Lampis and Vangelis Paschos.
Pour d'obscures raisons, nous définissons la notion de graphe orienté Dans cet exposé, je motiverai et présenterai ces différents résultats. J'en profiterai pour Travail commun avec J. Bang-Jensen, B. Jackson et M. Kriessell.
On s'intéresse aux graphes plongés sur des surfaces. Dès qu'on considère une surface plus compliquée que le plan ou la sphère des problèmes topologiques apparaissent. Beaucoup de travaux on été réalisés dans un cadre purement mathématiques sur le sujet y compris des travaux de nature algorithmique. Cependant les algorithmes proposés ne sont pas réellement utilisables en général. Certaines notions comme la simplicité sont problématiques. Effectivement, on obtient beaucoup plus facilement une courbe simple (sans point double) sur la surface qu'un cycle simple (sans sommet répété) dans un graphe plongé. On s'intéressera en particulier à la recherche de cycles simples (au sens du graphe) qui permettent de découper la surface sous-jacente en 2 parties non-planaires i.e. les cycles de partage.
Given a graph $G=(V,E)$, a subset $D$ of vertices is a dominating set if each vertex is either in $D$ or has at least one neighbor in $D$. A dominating set is minimal if it contains no dominating set as a proper subset. An interesting question is to determine the maximum number of minimal dominating sets in a graph. In this talk we provide upper bounds on this maximum number for various graph classes (split, cobipartite and interval graphs). These bounds are established via the running-time analysis of exponential-time algorithms which enumerates all the minimal dominating sets.
Geography and Vertex NimG are both games played on a graph. On their turn, a player moves a token along an arc and modifies the graph locally. In Geography, the player removes the vertex the token was on or the arc the token just slided along, depending on the variant. In Vertex NimG, the graph is weighted and the player decreases the weight of the vertex the token was on or the weight of the vertex the token just arrived on, depending of the variant. The game stops when a player cannot move. Under the misère convention, that player is considered the winner of the game. We see that these games are all pspace-hard in the general family of all graphs.
An edge-coloring of a graph $G$ is strong if its every color class is an induced matching. The strong chromatic index of $G$, denoted $\chi'_s(G)$, is the least number of colors in a strong edge-coloring of $G$. Greedy coloring arguments show that $\chi'_s$ is bounded above by roughly $2\Delta^2$, where $\Delta$ denotes the maximum degree of an implicit graph, though this upper bound is not reached in general. A long-standing conjecture of Erdös and Nešetřil (1989) states that the right upper bound on the strong chromatic index should actually be roughly $1.25\Delta^2$, which would be tight as confirmed by a particular family of graphs with a lot of small cycles ($C_4$'s and $C_5$'s). Excluding small cycles (i.e. with length at most $5$) in a graph is expected to make the strong chromatic index be smaller, as confirmed notably by Mahdian (2000) for $C_4$-free graphs. This observation made Faudree, Gyárfás, Schelp and Tuza (1990) conjecture that the strong chromatic index of bipartite graphs (which have no $C_3$'s and $C_5$'s) should be bounded above by $\Delta^2$. In the continuity of previous results of Steger and Yu (1993) and Nakprasit (2008), we verify this conjecture for bipartite graphs whose one part is of maximum degree at most$3$. This is a joint work with A. Lagoutte and P. Valicov.
Le problème Rankwidth-c Vertex Deletion consiste à supprimer k sommets pour obtenir un graphe de ranwkdith au plus c, où c est une constante. Ce problème est non-uniforme FPT paramétré par k. La question posée est de savoir si ce problème peut être résolu en temps FPT simple exponentiel. Le cas c=1 est intéressant pour plusieurs raisons. Il correspond au problème Distance Hereditary Graphs Vertex Deletion et est l'analogue pour la treewidth au problème Feedback Vertex Set. Nous répondons positivement à la question et montrons l’existence d’un noyau polynomial pour les graphes de rankwidth linéaire 1. Co-auteurs: M. Kanté (LIMOS), E.J. Kim (LAMSADE), O. Kwon (KAIST, Korea).
We consider an approximate version of a fundamental geometric search problem, polytope membership queries. Given a convex polytope P in d-dimensional space, presented as the intersection of halfspaces, the objective is to preprocess P so that, given a query point q, it is possible to determine efficiently whether q lies inside P subject to an allowed error ε. Previous solutions to this problem were based on straightforward applications of classic polytope approximation techniques by Dudley (1974) and Bentley et al. (1982). The former yields minimum storage, the latter yields constant query time, and a space-time tradeoff can be obtained by interpolating between the two. We present the first significant improvements to this tradeoff. For example, using the same storage as Dudley, we reduce the query time from O(1/ε^(d-1)/2) to O(1/ε^(d-1)/4) and, using a more involved analysis, to O(1/ε^(d-1)/8). Our approach is based on a very simple construction algorithm, whose analysis is surprisingly nontrivial. Both lower bounds and upper bounds on the performance of the algorithm are presented. For the same storage as Dudley, we present a lower bound of Ω(1/ε^(d-1)/18). To establish the relevance of our results, we introduce a reduction from approximate nearest neighbor searching to approximate polytope membership queries. Remarkably, we show that our tradeoff provides significant improvements to the best known space-time tradeoffs for this very well studied problem. This is joint work with Sunil Arya and David M. Mount.
Graphons are analytic objects associated with convergent sequences of graphs. Problems from extremal combinatorics and theoretical computer science led to a study of graphons determined by finitely many subgraph densities, which are referred to as finitely forcible. We show that there exists a finitely forcible graphon such that the topological space of its typical vertices has infinite Lebesgue covering dimension, disproving the conjecture by Lovasz and Szegedy. The talk is based on joint work with Roman Glebov and Dan Král'.
The CSP dichotomy conjecture is that every constraint satisfaction problem is polynomial or NP-complete. Feder and Vardi have shown that the CSP conjecture can be reduced to the case of digraph homomorphism. Hell and Nesetril settled the complexity of homomorphism to a graph G: it is polynomial if G is bipartite and NP-complete otherwise. We will show that the CSP conjecture can be reduced to the case of 2-edge-colored homomorphism and to the case of 2-vertex-colored homomorphism (also known as tropical homomorphism). It is a joint work with Nazanin Movarraei.
We first give a brief introduction of rank-width and linear rank-width. Even though rank-width has been well developed by a series of papers, only few known algorithmic or structural properties are developed for linear rank-width until recently. We list some problems related to this area, and then focus on a fixed parameter tractable algorithm using the obstruction set for bounded linear rank-width. We mainly show that the number of pivot-minor obstructions for linear rank-width at most k is doubly exponential in O(k).
In this talk we will sketch an FPT algorithm for a quite general cut problem on general graphs, which we call List Allocation. Our algorithm strongly uses the "edge contraction" technique introduced by Chitnis et al. [2012]. Besides being a natural cut problem by itself, the relevance of List Allocation is best demonstrated by the following algorithms, which we obtain by reducing in FPT time each corresponding problem to particular cases of List Allocation: (1) An FPT algorithm for a generalization of Digraph Homomorphism, which we call Arc-Bounded List Digraph Homomorphism. If time permits, we will partially discuss the above applications of our main algorithm. This is joint work with EunJung Kim, Sang-Il Oum, Christophe Paul, and Dimitrios M. Thilikos.
In this talk I will introduce two problems on edge-decompositions of graphs with bounded maximum degree. First, I will present a new approach to acyclic edge colorings of graphs with large girth. Using it, we obtain asymptotically tight results on a conjecture of Alon, Sudakov and Zaks. In the second part I will talk about the problem of partitioning the edges of a graph in different improper color classes with no monochromatic copy of a fixed graph. I will present an iterative embedding argument that allows us to transfer classical results from Extremal Graph Theory to bounded degree graphs. The common denominator of these two topics is the use of the so-called semirandom method. All the presented results are joint work with Cai, Reed and Watts (Part 1) and with Foucaud, Kang, Krivelevich and Reed (Part 2).
In this talk, we present results on the existence of paths of length 3 with given degree sequence in sparse graphs. Joint work with S. Jendrol, M. Macekova, and R. Sotak.
We propose a simple generalization of Schnyder woods to higher genus. We give a necessary and sufficient condition for an orientation to corresponds to such a Schnyder wood and we study the relations between these orientations. Unfortunately we are not able to prove the existence of these Schnyder woods in general but a new proof for the toroidal case is derived from this study.
A collection F of k unrooted phylogenetic trees on different leaf sets is said to be compatible if there exists a tree T such that each tree in F can be obtained from T by deleting leaves, suppressing degree-2 vertices, and by contracting edges. In the case of strict compatibility, the latter operation is not permitted.
Delaunay triangulations in R^d are a central object in many areas of mathematics and computational geometry. However, little is known about which combinatorial types can appear as a Delaunay triangulation. With an inverse stereographic projection, this question translates to asking which combinatorial types of polytopes admit realizations with all the vertices on a d-sphere. We will construct a large family of neighborly polytopes that are not only inscribable on the sphere, but also in every smooth strictly convex body. This provides the current best lower bound for the number of combinatorial types of Delaunay triangulations. In the second part of the talk, we will use these techniques to show that realization spaces of inscribed polytopes present Universality in the sense of Mnëv. For example, this will allow us to construct a pair of point configurations whose Delaunay triangulations are combinatorially equivalent but yet there is no continuous transformation that maps one to the other without changing the combinatorics of the Delaunay triangulation. This talk reports joint work with Karim Adiprasito, Bernd Gonska and Louis Theran.
Dans cette présentation nous nous intéresserons à des problèmes "de connexité" paramétrés par la treewidth. Tous les problèmes évoqués sont solubles par des algorithmes classiques en un temps 2^{O(tw log tw)}*poly(n). Nous nous intéresserons à l'algorithme de Cut&Count [1] réduisant ce temps de calcul pour la plupart de ces problèmes à un temps 2^{O(tw)}*poly(n) dans les graphes généraux puis examinerons les liens et les différences de complexité de ces problèmes de connexité entre les graphes généraux et les graphes planaires. [1] Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk: Solving connectivity problems parameterized by treewidth in single exponential time. FOCS 2011. Travail en commun avec Ignasi Sau.
Let A be a class of combinatorial structures equipped, for each N, with a probability distribution on the collection of objects of size N. Given a sentence S in some logical language, we are interested in the limiting probability P(S) that S is satisfied among all objects of size N, as N goes to infinity. If P(S) is either 0 or 1 for each sentence S, we say that the zero-one law holds. The first result of this kind was obtained by Glebskii et al. in 1969 for the class of labelled graphs and sentences in first order logic (FO). Compton (1987) obtained in some cases zero-one laws solely from properties of the counting function of the class A. Later he extended it to monadic second order logic (MSO), which is FO logic plus quantification over unary relations. More recently McCoy (2002) proved a zero-one law in MSO logic for labelled trees. We provide a significant extension of McCoy’s result to classes of graphs closed under taking minors. As an example, we prove the MSO zero-one law for connected planar graphs and a convergence law (every sentence has a limit, not necessarily 0 or 1) for all planar graphs. We also determine the closure of the set of all possible limiting probabilities, both in FO and MSO. For the proofs we use classical tools from combinatorial logic, in particular Ehrenfeucht-Fraïssé games, and properties of random graphs from a minor-closed class.
Let C be a graph class closed under subgraphs. We prove that all FO-definable concept classes on C allow example-efficient learnability (in the PAC model) if and only if C is nowhere dense.
Given a graph G that admits a perfect matching, the parameter eta(G) is defined as follows. Among all positive edge weight assignments, eta(G) is the minimum ratio between the maximum weight of (i) a perfect matching and (ii) any matching. In this talk we present new and previous results on the parameter eta. Among them, a characterization of graphs with eta(G)=0 and eta(G) = 1 and the exact value of eta for all grids, bipartite cylindrical grids, and bipartite toroidal grids. Joint work with: Diana Sasaki and Bernard Ries.
Deux cycles d'un graphes sont mutuellement induits s'il n'y a pas d'arêtes entre eux dans le graphe. Etant donné un graphe G et un entier r, peut-on facilement savoir si G contient r cycles 2 à 2 induits ? Ce problème, que nous appellerons Cycles-Induits, n'a pas de noyau polynomial quand il est paramétrisé par r sous des hypothèses courantes de complexité, d'après les résultats de Bodlaender, Thomassé et Yeo (2012), qui ont étudié sa version non-induite. En utilisant des arguments simples, nous montrons que Cycles-Induits a un noyau de taille O(Δ²) pour r = 2 et O(rΔ² log(rΔ)) pour r > 2. Une conséquence est que la version non-induite du problème a aussi un noyau polynomial pour cette paramétrisation. Résultats obtenus en collaboration avec Aistis Atminas (Université de Warwick) et Marcin Kamiński (Université de Varsovie).
Cet exposé sera la présentation des problèmes ouverts posés lors du workshop "Cycles and Colourings 2014".
The origin of the study of Erdős-Pósa properties comes from the celebrated Erdős-Pósa Theorem (1965), stating that there is a natural function $f$ such that for every positive integer $k$ and for every graph $G$, either $G$ contains $k$ vertex-disjoint cycles or there is a set $X$ of $f(k)$ vertices in $G$ meeting all cycles of $G$. In particular, Erdős and Pósa proved this result for $f(k)=O(k\cdot \log k)$ and showed that this bound is optimal. Given a graph $J$, we denote by ${\cal M}(J)$ the set of all graphs that can be contracted to $J$ (also called models of $J$). Robertson and Seymour proved that the class ${\cal M}(J)$ satisfies the Erdős-Pósa property if and only if $J$ is planar. Notice that this can be seen as a major extension of the Erdős-Pósa Theorem (take $J=\theta_{2}$ where, in general, $\theta_{r}$ is the graph consisting of two vertices and $r$ parallel edges between them). The emerging question is whether (and when) the function involved in the above proposition can match the (optimal) $O(k\cdot \log k)$ bound of Erdős-Pósa and whether this bound can be improved under several assumptions on the graphs it applies. Given two graphs $H$ and $G$, we denote by ${\bf pack}^{\sf v}_{H}(G)$ (resp. ${\bf pack}^{\sf e}_{H}(G)$) the maximum number of vertex (resp. edge)-disjoint models of $H$ in $G$. We also denote by ${\bf cover}^{\sf v}_{H}(G)$ resp. ${\bf cover}^{\sf v}_{H}(G)$) the minimum number of vertices (resp. edges) that intersect all models of $H$ in $G$. We give a unified proof of the following result. Theorem: For every ${\sf x}\in\{{\sf v}, Our results also imply that, for every ${\sf x}\in\{{\sf v}, (Joint work with: Dimitris Chatzidimitriou, Jean-Florent Raymond, and Ignasi Sau). |