## AlGCo : algorithmes, graphes et combinatoire
Séminaire Le séminaire/groupe de travail AlGCo a lieu le jeudi
de 10h à 11h
(et quelques) en salle E.323 (généralement).
Abonnement à la liste de diffusion algocomb :
ici (annonces des exposés du LIRMM et de l'IMAG en algorithmique, combinatoire et mathématiques discrètes).Fichier ICalendar (pour avoir l'information du séminaire AlGCo directement dans son agenda) : ici. La page ci-dessous est générée automatiquement à partir de la page du séminaire sur collorg. Prochain exposé
The Flat Wall theorem was proved by Roberston and Seymour as part of their Graph Minors series (GM XIII). This theorem reveals that every graph excluding a clique as a minor and having sufficiently big treewidth contains a "flat wall", that is subdivision of a wall that is arranged inside the graph in a "flat manner''. In the same paper, this theorem was used as a key graph-structural ingredient of an algorithm for the celebrated Disjoint Paths Problem. GM XIII was published in J. Comb. Theory Ser. B in 1995 and since then, this theorem was used in numerous applications both in combinatorics and in algorithmic design. The purpose of this seminar is to give a detailed and precise statement of the Flat Wall Theorem, accompanied with a comparative study of its various alternative forms, optimizations, and applications. Exposés (à venir)- 04/06/20 - Dimitrios M. Thilikos : A Detaild Exposition of The Flat Wall theorem
- 11/06/20 - Ana Karolinna Maia : Characterizing networks admitting multiple arc-disjoint branching flows
- 18/06/20 - Ignasi Sau : On the complexity of finding large odd induced subgraphs and odd colorings
Archives :
2018-... |
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 (passés depuis 09/2018)- 28/05/20 - Christophe Paul : A linear fixed parameter tractable algorithm for connected pathwidth
- 14/05/20 - Júlio Araújo : Weighted proper orientations of trees and graphs of bounded treewidth
- 09/01/20 - Andreas Schmid : A New Approach for the Maximum Planar Subgraph Problem
- 19/12/19 - Marc Heinrich : Counting independent sets in strongly orderable graphs
- 12/12/19 - Dimitrios Thilikos : Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
- 06/11/19 - Uéverton S. Souza : Computing the largest bond of a graph
- 26/09/19 - Petr A. Golovach : Parameterized Low-Rank Binary Matrix Approximation
- 06/06/19 - Kolja Knauer : Generating k-connected orientations
- 23/05/19 - Stéphan Thomassé : Computing Maximum Independent Set in Graph Classes
- 16/05/19 - Archontia Giannopoulou : Braces of Perfect Matching Width 2
- 28/03/19 - Jayakrishnan Madathil : Connecting the Dots (with Minimum Crossings)
- 21/03/19 - Rémy Belmonte : Token Sliding on Split Graphs
- 07/02/19 - Guilherme Gomes : On the complexity of finding cuts of bounded degree
- 17/01/19 - Ana Silva : Graphs with small fall-spectrum
- 06/12/18 - Mohammed SENHAJI : Neighbour-distinguishing decompositions of graphs
- 29/11/18 - Alan Diego Aurélio Carneiro : Complexity Analysis of Deadlock Resolution Graph Problems.
- 22/11/18 - Victor A. Campos : Free Lula Trees
- 25/10/18 - Raul Lopes : Disjoint paths, grids and tree-width: the directed case.
- 18/10/18 - Aniket Basu Roy : Effectiveness of Local Search for Geometric Packing and Covering Problems
- 11/10/18 - Tom Kelly : On the density of critical graphs without large cliques
- 27/09/18 - Vinicius Fernandes dos Santos : Characterization, probe and sandwich problems on a generalization of threshold graphs
- 20/09/18 - Lucia Penso : Dynamic monopolies and Vaccination
- 13/09/18 - Guilherme Gomes : Parameterized Complexity of Equitable Coloring and Intersection Graphs of maximal stars
- 06/09/18 - Dieter Rautenbach : On the maximum number of minimum dominating sets, minimum total dominating sets, and maximum independent sets
This talk is about the problems of finding, given a graph $G$, a largest induced subgraph of $G$ with all degrees odd (called an \emph{odd} subgraph), and the smallest number of odd subgraphs that partition $V(G)$. We call these parameters $mos(G)$ and $\chi_{odd}(G)$, respectively. We will discuss (some of) the following results: - Deciding whether $\chi_{odd}(G) \leq q$ is polynomial-time solvable if $q \leq 2$, and NP-complete otherwise. Joint work with Rémy Belmonte
An $s$-branching flow $f$ in a network $N = (D,c)$ (where $c$ is the capacity function) is a flow that reaches every vertex in $V(D) \setminus \{s\}$ from $s$ while loosing exactly one unit of flow in each vertex other than $s$. In other words, the difference between the flow entering a vertex $v$ and a flow leaving a vertex $v$ is one whenever $v \neq s$.It is known that the hardness of the problem of finding $k$ arc-disjoint $s$-branching flows in network $N$ is linked to the capacity $c$ of the arcs in $N$: the problem is solvable easy to compute if every arc has capacity $n - \ell$, for fixed $\ell$, and hard in most other cases, with very few cases open. We further investigate a conjecture by Costa et al. from 2019 that aims to characterize networks admitting $k$ arc-disjoint $s$-branching flows, generalizing a result by Bang-Jensen and Bessy that provides such characterization when all arcs have capacity $n-1$. Joint work with: C. Carvalho, J. Costa, C. Linhares Sales, R. Lopes, N. Nisse
The graph parameter of Joint work with Mamadou Moustapha Kanté and Dimitrios M. Thilikos
Given a simple graph $G$, a weight function $w:E(G)\rightarrow \mathbb{N} \setminus \{0\}$, and an orientation $D$ of $G$, we define $\mu^-(D) = \max_{v \in V(G)} w_D^-(v)$, where $w^-_D(v) = \sum_{u\in N_D^{-}(v)}w(uv)$. We say that $D$ is a \emph{weighted proper orientation} of $G$ if $w^-_D(u) \neq w^-_D(v)$ whenever $u$ and $v$ are adjacent. We introduce the parameter {\em weighted proper orientation number} of $G$, denoted by $\overrightarrow{\chi}(G,w)$, which is the minimum, over all weighted proper orientations $D$ of $G$, of $\mu^-(D)$. When all the weights are equal to 1, this parameter is equal to the {\em proper orientation number} of $G$, which has been object of recent studies and whose determination is NP-hard in general, but polynomial-time solvable on trees. We prove that the equivalent decision problem of the weighted proper orientation number (i.e., $\overrightarrow{\chi}(G,w) \leq k?$) is (weakly) NP-complete on trees but can be solved by a pseudo-polynomial time algorithm whose running time depends on $k$. Furthermore, we present a dynamic programming algorithm to determine whether a general graph $G$ on $n$ vertices and treewidth at most $tw$ satisfies $\overrightarrow{\chi}(G,w) \leq k$, running in time ${\cal O}(2^{tw^2}\cdot k^{3tw}\cdot tw \cdot n)$, and we complement this result by showing that the problem is $W[1]$-hard on general graphs parameterized by the treewidth of $G$, even if the weights are polynomial in $n$.
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph G contains a cactus subgraph C where C contains at least a 1/6 fraction of the triangular faces of G. We also show that this ratio cannot be improved by showing a tight lower bound. Together with an algorithm for linear matroid parity, our bound implies two approximation algorithms for computing "dense planar structures" inside any graph: (i) A 1/6 approximation algorithm for, given any graph G, finding a planar subgraph with a maximum number of triangular faces; this improves upon the previous 1/11-approximation; (ii) An alternate (and arguably more illustrative) proof of the 4/9 approximation algorithm for finding a planar subgraph with a maximum number of edges. Our bound is obtained by analyzing a natural local search strategy and heavily exploiting the exchange arguments. Therefore, this suggests the power of local search in handling problems of this kind.
We are interested in counting problems which consists in computing the number of solutions to a given instance of the problem. This kind of question has strong connexions, in particular in the case of independent sets, with problems from statistical physics and what is called the hard core distribution. As many counting problems, counting exactly the number of independent sets of a graphs is difficult (i.e., #P-complete) even on bipartite graphs, and even difficult to approximate for general graphs. On the other hands, it was shown to be polynomial time solvable for more restricted classes of graphs such as chordal graphs, cographs or monotone bipartite graphs. We show that the number of independent sets can also be computed in polynomial time for strongly orderable graphs which is a super-class of chordal bipartite and strongly chordal graphs. This is joint work with Haiko Muller.
For a finite collection of graphs ${\cal F}$, the ${\cal F}$-TM-Deletion problem has as input an $n$-vertex Joint work with Petr A. Golovach and Giannos Stamoulis
A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [S, V \ S] of G such that G[S] and G[V \ S] are both connected. Given s,t \in V(G), an st-bond of G is a bond whose removal disconnects s and t. Contrasting with the large number of studies related to maximum cuts, there are very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond and the largest st-bond of a graph. Although cuts and bonds are similar, we remark that computing the largest bond of a graph tends to be harder than computing its maximum cut. We show that Largest Bond remains NP-hard even for planar bipartite graphs, and it does not admit a constant-factor approximation algorithm, unless P = NP. We also show that Largest Bond and Largest st-Bond on graphs of clique-width w cannot be solved in time f(w) × n^{o(w)} unless the Exponential Time Hypothesis fails, but they can be solved in time f(w) × n^{O(w)}. In addition, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, but they do not admit polynomial kernels unless NP \subseteq coNP/poly. Joint work with Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa, and Rafael C. S. Schouery.
(joint work with Fedor V. Fomin and Fahad Panolan) We provide a number of algorithmic results for the following family of problems: For a given binary m\times n matrix A and integer k, decide whether there is a ``simple'' binary matrix B which differs from A in at most k entries. For an integer r, the ``simplicity'' of B is characterized as follows. - Binary r-Means: Matrix B has at most r different columns. This problem is known to be NP-complete already for r=2. We show that the problem is solvable in time 2^{O(k\log k)}(nm)^{O(1)} and thus is fixed-parameter tractable parameterized by k. We prove that the problem admits a polynomial kernel when parameterized by r and k but it has no polynomial kernel when parameterized by k only unless NP\subseteq CoNP/ poly}. We also complement these result by showing that when being parameterized by r and k, the problem admits an algorithm of running time 2^{O( \sqrt{kr\log{(k+r)\log r}})}(nm)^{O(1)}, which is subexponential in k. - Low GF(2)-Rank Approximationt: Matrix B is of GF(2)-rank at most r. This problem is known to be NP-complete already for r=1. It is also known to be W[1]-hard when parameterized by k. Interestingly, when parameterized by r and k, the problem is not only fixed-parameter tractable, but it is solvable in time 2^{O(r\sqrt{k\log{kr}})}(nm)^{O(1)}, which is subexponential in k.
We present a simple algorithm, that given a graph G generates Another nice thing is, that our algorithm actually consists of two Joint work with Sarah Blind and Petru Valicov
Computing MIS in graph classes is often the right approach for many optimization problems. For instance finding a near maximal set of pairwise intersecting disks in the plane can be done in polytime, just by considering the intersection graph structure. While this approach is appealing, the general problem "Decide which classes C of graphs are easy for MIS" seems a very difficult task. A first and more modest step is to restrict ourselves to classes C defined by a finite list of forbidden induced subgraphs. Here we could show with M. Chudnowsky, M. Pilipczuk and M. Pilipczuk that MIS in Pt-free graphs admits a QPTAS, and this led to a general dichotomy: MIS is either APX-hard or has a QPTAS. Strenghtening QPTAS for these classes to PTAS, QP or even P seems however hard, as a very fine understanding is needed. A much more difficult problem is to characterize these classes C for which MIS is FPT. Sadly, even if we can now decide if MIS is FPT in H-free graphs, where H has at most 5 vertices, we have neither a candidate for a general characterization, nor a general type of algorithm. Instead we face many different aspects of computing an independent set, which makes this question a very exciting playground (Joint work with E. Bonnet, N. Bousquet, P. Charbit and R. Watrigant).
A graph G is called matching covered
We study a prototype "crossing minimization" problem. Consider a graph G embedded in the Euclidean plane as follows: the vertices are in distinct points in the plane, and the edges are embedded as line segments between their endpoints. A crossing in G is a pair of edges that intersect (at a point other than their possibly common endpoints). As a starting point, we consider the special case when G is a two-layered graph, i.e., a bipartite graph with the following embedding. Let V(G)=X union Y be the vertex bipartition; the vertices of X are embedded on a line L_1, and the vertices of Y on a different line L_2 that is parallel to L_1. In this case, the crossings in G are uniquely determined by the relative ordering of vertices of X and Y on the lines L_1 and L_2, respectively. 1. Crossing Minimizing Perfect Matching: The problem is to test whether G has a perfect matching with at most k crossings. We show that this problem is NP-hard, but admits a 2^{O(sqrt(k))} poly(n) algorithm and a kernel with O(k^2) vertices. 2. Crossing Minimizing Hamiltonian Path: The problem is to test whether G has a Hamiltonian path with at most k crossings. We show that this problem is NP-hard, but admits a 2^{O(sqrt(k) log k)} poly(n) algorithm and a kernel with O(k^2) vertices. 3. Crossing Minimizing (s,t)-path: The problem is to test whether G has a path (between two given vertices s and t) with at most k crossings. We show that this problem is W[1]-hard, but admits an n^{O(k)} algorithm. The talk will focus mainly on the Crossing Minimizing Perfect Matching problem. This is joint work with Akanksha Agrawal, Grzegorz Guśpiel, Saket Saurabh and Meirav Zehavi.
We consider the complexity of the Independent Set Joint work with Eun-Jung Kim, Michael Lampis, Valia Mitsou, Yota
A matching cut is a partition of the vertices of a graph in two sets A and B such that each vertex has at most one neighbor on the other side of the cut. The Matching Cut problem asks whether or not a graph has a matching cut, and has been intensively studied in the literature. In this talk, we introduce a natural generalization of this problem, which we call d-Cut: for a positive integer d, a d-cut is a bipartition of the vertices of a graph into two sets A and B such that each vertex has at most d neighbors across the cut. We generalize (and in some cases, improve) a number of results for the Matching Cut problem. Namely, we begin with an NP-hardness reduction for d-Cut on (2d+2)-regular graphs and a polynomial algorithm for graphs of maximum degree at most d+2. We then give FPT algorithms when parameterizing by: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to co-cluster; in particular, the treewidth algorithm improves upon the running time of the best known algorithm for Matching Cut. Our main technical contribution is a polynomial kernel for d-Cut, for every positive integer d, parameterized by the distance to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. We conclude with an exact exponential algorithm slightly faster than the naive brute force approach running in time O(2^n). Joint work with Ignasi Sau.
Given a proper coloring $f$ of a graph $G$, a b-vertex in $f$ is a vertex that is adjacent to every color class but its own, and $f$ is a fall-coloring if every vertex is a b-vertex. The fall-spectrum of $G$ is the set $\F(G)$ of all values $k$ for which $G$ admits a fall-coloring with $k$ colors. Some authors have found that some subclasses of perfect graphs have the property that: (*) $\F(G)\neq\emptyset$ if and only if $\chi(G)=\delta(G)+1$. This has led Kaul and Mitilos to conjecture that (*) holds for every perfect graph. We prove that this is not true by showing a chordal graph on which (*) does not hold. Nevertheless, we investigate what is the "good property" that these graphs have and, among other results, we have found some interesting aspects that led us to introduce perfectness classes related to this kind of coloring.
The main question taht we explore was introduced by Karonski, Luczak and In this presentation we explore several variants of the 1-2-3 Conjecture, and We also present a 2 -player game version of neighbour-sum-distinguishing edge-weightings and exhibit sufficient conditions for each player to win the game. References
A deadlock occurs in a distributed computation if a group of processes wait indefinitely for resources from each other. We study actions to be taken after deadlock detection, especially the action of searching for a small deadlock-resolution set. More precisely, given a “snapshot” graph G representing a deadlocked state of a distributed computation governed by a certain deadlock model M, we investigate the complexity of vertex/arc deletion problems that aim at finding minimum vertex/arc subsets whose removal turns G into a deadlock-free graph (according to model M). We present a computational complexity mapping considering the particular combination of deletion operations and deadlock models. A special attention is given to Vertex–Deletion(OR), which consists of determining whether G has a subset S ⊆ V(G) of size at most k such that G[V∖S] contains no knot. A knot in a directed graph G is a strongly connected subgraph Q of G with size at least two, such that no vertex in V(Q) is an in-neighbor of a vertex in V(G)∖V(Q). Our main contributions is a parameterized complexity analysis of the Vertex–Deletion(OR) problem. Vertex–Deletion(OR) is a graph problem with natural applications in deadlock resolution, and it is closely related to Directed Feedback Vertex Set. We prove that: Vertex–Deletion(OR) is W[1]-hard when parameterized by the size of the solution; it can be solved in time, but assuming SETH it cannot be solved in time, where φ is the size of the largest strongly connected subgraph of G; it can be solved in time, but assuming ETH it cannot be solved in time, where Ф is the number of vertices with out-degree at most k; unless , Vertex–Deletion(OR) does not admit polynomial kernel even when φ=2 and k is the parameter. Authors : Alan Carneiro, Fábio Protti and Uéverton Souza.
In this talk, we introduce Free Lula Trees. Free Lula Trees are balanced binary search trees based on Red-Black Trees that can implement the usual Search/Insert/Delete/Successor/Predecessor operations in O(log n) time. Although never published, this data structure was developed in 2000 to implement efficient priority queues for branch-and-bound applications. A Split Tree is a Data Structure that contains a set of nodes and can search for and delete a given node x and split itself into two split trees in O(1) amortized time, one containing all nodes with key less than x and the other with all nodes with key greater than x. Split trees were studied by Demaine et. al. in 2009, but few details were given on how to do it in the BST model of computation. We show how an implementation of Split Trees can be made in the BST model of computation using Free Lula Trees. To motivate Split Trees, we will spend some time presenting the Dynamic Optimality Conjecture and its Geometric View to relate it to an interesting problem in Graph Theory. The Geometric View of the Dynamic Optimality Conjecture is based on a work by Demaine et. al. This talk will be adapted for people who do not usually work with Data Structures. Tree naming: Luiz Inácio Lula da Silva is a political prisoner in Brasil since April 7th 2018. He was jailed without reasonable evidence to prevent him from running for the 2018 election. The authors would like to plant a tree in solidarity for him, but a physical tree would probably be cut down in the current situation of political turmoil that Brazil lives in. Therefore, we will plant a symbolic theoretical tree which can resist such hatred. Joint work with Ricardo Corrêa (Universidade Federal Rural do Rio de Janeiro - UFRRJ).
Width parameters in graphs can be seen as an estimation to how similar a graph is a to a typical structure. Graphs with bounded width parameters are usually decomposed into small parts, which in turn are placed under a set of rules and relations between them. Therefore, we can make use of classical algorithm construction techniques exploring those properties, like dynnamic programming, to efficiently solve many hard problems in graphs with bounded width parameters. The focus of this work is on tree-width for directed graphs. This parameter is used to estimate how close a directed graph is to a directed acyclic graph. In particular, we show a parameterized algorithm, under parameter k, which either finds a directed tree decomposition of width at most 3k-2 or generates a certificate that the width of the given graph is at least k-1. We hope to apply this result as a first step to show that the recent Directed Grid Theorem, a result analogous to the Grid Theorem for directed graphs, can be done in FPT time.
In the words of Papadimitriou and Steiglitz, “local search is based on what is perhaps the oldest optimization method — trial and error.” In this talk, we are going to discuss a local search framework for geometric optimization problems that yields a polynomial time approximation scheme (PTAS) which was introduced independently by two different papers in 2009. Then we are going to see its effectiveness in packing non-piercing regions and guarding orthogonal art galleries with mobile guards.
A graph is k-critical if it has chromatic number k and every proper subgraph is (k - 1)-colorable. The density of critical graphs has been extensively studied. We present an improvement on the best known lower bound for the density of critical graphs without large cliques. We also discuss a connection to list-coloring and generalizations of Reed's Conjecture. Joint work with Luke Postle.
A cograph is a graph without induced paths of size 4. A graph G is (k,l) if its vertex set can be partitioned into at most k independent sets and l cliques. Cographs-(k,l) have been studied on the literature, but no structural characterization is was known, except for cographs-(1,1), i.e threshold graphs. In this talk, we present a structural characterization for cographs-(2, 1). We show some applications of this characterization on two generalizations of the recognition problem, namely the recognition of probe cographs-(2,1) and the sandwich problem. Joint work with Fernanda Couto, Luerbio Faria, Sylvain Gravier and Sulamita Klein.
TBA
A n-vertex graph is equitably k-colorable if it admits a proper k-coloring such the size of any two color classes differ by at most one. We present some results on parameterized complexity of the problem for subclasses of chordal graphs, showing that even if we parameterize by the number of colors, treewidth and maximum degree, equitably coloring a K_1,4-free interval graph is W[1]-Hard. This generalizes a result by Fellows et al. (2014) through a much simpler reduction. Together with a theorem due to de Werra (1985), we establish a dichotomy for the parameterized complexity of equitably coloring chordal graphs based on the size of the largest induced star. Finally, we give an FPT algorithm for equitable coloring parameterized by the treewidth of the complement graph, which has optimal running time (up to polynomial factors) unless ETH fails. Outside parameterized complexity, we investigate a problem in intersection graph theory, namely the characterization and recognition of the intersection graphs of maximal stars. We provide a Krausz-type characterization for the class by showing that a small set of natural conditions is both necessary and sufficient.
We consider the stated numbers mainly in trees, forests, and connected graphs. Among others we give a very simple proof of Zykov's generalization of Turán's theorem, and verify a conjecture of Derikvand and Oboudi. The presented results are joint work with J. Alvarado, S. Dantas, M.A. Henning, and E. Mohr. |