## AlGCo : algorithmes, graphes et combinatoire
Séminaire En général (sauf exception), le séminaire/groupe de travail AlGCo a lieu le jeudi
de 10h à 11h
(et quelques) en salle de séminaire bât. 4 (en période covid).
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é
Poset dimension is an important measure of structural complexity for posets and studying the cover graph of a poset has proven particularly useful when working with this parameter. Bounds on the dimension have for example been established by excluding particular (topological) minors from the cover graph, or by only considering cover graphs with treewidth at most two. In fact, if the cover graph is planar, a host of other important structural parameters for posets bound their dimension, even if this is not the case in general. Along these lines, Felsner et al. in 2014 proved that posets with outerplanar cover graphs have dimension at most 4. Motivated by this result, we give a cubic bound for the dimension of posets with k-outerplanar cover graphs. As a consequence, we also improve the bound on the dimension of planar posets with height h from $O(h^6)$ to $O(h^3)$. Exposés (à venir)- 20/05/21 - Maximilian Gorsky : k-Outerplanarity and Poset Dimension
- 27/05/21 - Stéphane Bessy : TBA
- 03/06/21 - Julien Baste : Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
- 10/06/21 - Euiwoong Lee : The Karger-Stein Algorithm is Optimal for $k$-cut
- 17/06/21 - Fedor V. Fomin : Paths, cycles and beyond
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)- 06/05/21 - Christophe Paul : Arrow’s theorem and impossibility theorems in computational social choice
- 15/04/21 - Giannos Stamoulis : Parameterized Algorithms for Vertex Deletion to Minor-closed Graph Classes
- 08/04/21 - Dimitrios M. Thilikos : Bounding the Obstructions for Apices of Minor-closed Graph Classes
- 01/04/21 - Stéphane Bessy : Exponential Independence in Subcubic Graphs
- 25/03/21 - Ignasi Sau : Kernelization of Maximum Minimal Vertex Cover
- 18/03/21 - Marin Bougeret : On the complexity of computing Maximum Minimal Blocking Sets
- 11/03/21 - Daniel Gonçalves : On the colorability of rectangle intersection graphs
- 04/03/21 - Sebastian Wiederrecht : A matching theoretic approach to structural digraph theory
- 18/02/21 - François Pirot : Complexity thresholds for fractional distributed colouring
- 11/02/21 - Alexandre Vigny : Query enumeration and nowhere dense classes of graphs
- 04/02/21 - Thomas Bellitto : Connectivity and routing in forbidden-transition graphs
- 28/01/21 - Archontia C. Giannopoulou : Excluding a Planar Matching Minor in Bipartite Graphs
- 21/01/21 - William Lochet : A polynomial time algorithm for the k-disjoint shortest path problem
- 17/12/20 - Hoang La : Déchargement assisté par ordinateur : application à la coloration à distance 2
- 10/12/20 - Ivan Rasskin : Construction d'entrelacs avec des empilements de boules à l'aide de la géométrie Lorentzienne discrète
- 03/12/20 - Petr Golovach : Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration
- 19/11/20 - Júlio Araújo : Some results on (circular) backbone colorings
- 12/11/20 - Fabien Jacques : Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets
- 05/11/20 - Florian Hoersch : Reachability in arborescence packings
- 08/10/20 - Matthieu Rosenfeld : A new Approach to Non-Repetitive Colorings of Graphs of Bounded Degree
- 01/10/20 - Ignasi Sau : Reducing graph transversals via edge contractions
- 24/09/20 - Marin Bougeret : Kernelization of Vertex Cover under structural parameterizations
- 10/09/20 - Dieter Rautenbach : Reconfiguring dominating sets in minor-closed graph classes
- 02/07/20 - EunJung Kim : Twin-width I: tractable FO model checking
- 18/06/20 - Ignasi Sau : On the complexity of finding large odd induced subgraphs and odd colorings
- 11/06/20 - Ana Karolinna Maia : Characterizing networks admitting multiple arc-disjoint branching flows
- 04/06/20 - Dimitrios M. Thilikos : A Detaild Exposition of The Flat Wall theorem
- 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
I will speak about old and new parameterized algorithms for finding long paths and cycles in graphs. In particular, we discuss problems of finding paths and cycles whose lengths are beyond some ``trivial'' bounds.
In the $k$-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into $k$ connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum $k$-cut in time approximately $O(n^{2k-2})$. The best lower bounds come from conjectures about the solvability of the $k$-clique problem and a reduction from $k$-clique to $k$-cut, and show that solving $k$-cut is likely to require time $\Omega(n^k)$. Our recent results have given special-purpose algorithms that solve the problem in time $n^{1.98k + O(1)}$, and ones that have better performance for special classes of graphs (e.g., for small integer weights).
When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which automatically converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter. Joint work with: Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond
TBA
Est-il possible de proposer un système de vote qui soit à la fois démocratique et non manipulable ? Plus formellement, Arrow montre que si un vote d’au moins deux électeurs porte sur au moins 3 options que chaque électeur doit La preuve de ce résultat a fait l’objet de simplifications successives pour devenir relativement simple et élégante. Nous
Let ${\cal G}$ be a minor-closed graph class. We provide an algorithm that, given a graph $G$ on $n$ vertices, runs in time $2^{{\sf poly}(k)}\cdot n^3$ and either returns a set $S$ such that $G\setminus S$ belongs to ${\cal G}$, or reports that such a et does not exist. Here ${\sf poly}$ is a polynomial function whose degree depends on the maximum size of a minor-obstruction of ${\cal G}.$ In the special case where ${\cal G}$ excludes some apex graph as a minor, we give an alternative algorithm running in $2^{{\sf poly}(k)}\cdot n^2$-time. Joint work with Ignasi Sau and Dimitrios M. Thilikos
Let ${\cal G}$ be a minor-closed graph class. We say that a graph $G$ is a Joint work with Ignasi Sau and Giannos Stamoulis
A set $S$ of vertices of a graph $G$ is exponentially independent if, for every vertex $u$ in $S$, $\sum_{v∈S\setminus \{u\}}(1/2)^{{\rm dist}(G,S) (u,v)−1} < 1$, where ${\rm dist}(G,S)(u, v)$ is the distance between $u$ and $v$ in the graph $G − (S \setminus \{u, v\})$. The exponential independence number $αe(G)$ of $G$ is the maximum order of an exponentially independent set in $G$. In this work we present several bounds on this parameter and highlight some of the many related open problems. In particular, we prove that subcubic graphs of order n have exponentially independent sets of order $Ω(n/\log^2 (n))$, that the infinite cubic tree has no exponentially independent set of positive density, and that subcubic trees of order n have exponentially independent sets of order $(n + 3)/4$. Joint work with D. Rautenbach and J. Pardey, Ulm University
In the Joint work with Júlio Araújo, Marin Bougeret, and Victor A. Campos.
A blocking set in a graph $G$ is a subset of vertices that intersects every maximum independent set of $G$. Let 𝗆𝗆𝖻𝗌($G$) be the size of a maximum (inclusion-wise) minimal blocking set of $G$. This parameter has recently played an important role in the kernelization of Vertex Cover parameterized by the distance to a graph class ${\cal F}$. Indeed, it turns out that the existence of a polynomial kernel for this problem is closely related to the property that 𝗆𝗆𝖻𝗌$({\cal F})=sup_{G∈F}$𝗆𝗆𝖻𝗌$(G)$ is bounded by a constant, and thus several recent results focused on determining 𝗆𝗆𝖻𝗌$(F)$ for different classes $F$. We consider the parameterized complexity of computing 𝗆𝗆𝖻𝗌 under various parameterizations, such as the size of a maximum independent set of the input graph and the natural parameter. We provide a panorama of the complexity of computing both 𝗆𝗆𝖻𝗌 and 𝗆𝗆𝗁𝗌, which is the size of a maximum minimal hitting set of a hypergraph, a closely related parameter. Finally, we consider the problem of computing 𝗆𝗆𝖻𝗌 parameterized by treewidth, especially relevant
Chalermsook and Walczak proved that rectangle intersection graphs with clique number $w$, are $O(w\cdot\log w)$-colorable. This improves on the $O(w^2)$ bound dating from 1960. They also designed a deterministic polynomial-time $O(\log \log n)$-approximation algorithm for the same problem. This improves on previous known algorithms. This talk will be devoted to the description of these results.
The theory of butterfly minors in digraphs which is closelinked to the notion of directed treewidth has become an active field of research in the past years. Many great advancements have been made such as a directed version of the famous Grid Theorem and several other generalisations of great results from the Graph Minors Series of Robterson and Seymour.
In the domain of distributed algorithms, the complexity is considered in terms of rounds, during which the nodes of a graph can exchange data with their neighbours. Moreover, in the LOCAL model, the nodes are assumed to have infinite computational power, so any problem can be solved within D rounds, if D is the diameter of the graph. When considering distributed colourings of graphs of fixed maximum degree Δ on n vertices, an interesting complexity threshold appears. There exists a deterministic distributed algorithm for finding a colouring with Δ+1 colours within O(log* n) rounds. If the graph is neither complete nor an odd cycle, Brooks' Theorem tells us that there exists a colouring with Δ colours. It turns out that any distributed algorithm constructing such a colouring requires Ω(log n) rounds if it is deterministic, or Ω(log log n) rounds if it is probabilistic. In this talk, I will present a similar sharp threshold for the complexity of distributed fractional colourings of graphs of fixed maximum degree, and of d-dimensional grids. Finally, I will present a distributed algorithm for constructing a fractional colouring of weight 2+ε of graphs of maximum average degree 2+ε' and sufficiently large girth, within O(log n) rounds. Joint work with Nicolas Bousquet and Louis Esperet.
Given a query q and a graph G the enumeration of q over G consists in computing, one element at a time, the set q(G) of all solutions to q on G. The delay is the maximal time between two consecutive output and the preprocessing time is the time needed to produce the first solution. Ideally, we would like to have constant delay enumeration after linear preprocessing. Since this it is not always possible to achieve, we need to add restriction to the classes of graphs and/or queries we consider. In this talk I will talk about some restrictions for which such algorithms exist: graphs with bounded degree, tree-like structures, conjunctive queries...
Graphs have proved to be an extremely useful tool to model routing problems in a very wide range of applications. However, in some of them, we sometimes need to express constraints on the permitted walks that are stronger than what the standard graph model allows for. For example, in a road network, there can be a crossroad where drivers are not allowed to turn right and in this case, many walks in the underlying graph would correspond to routes that a driver is not allowed to use. To overcome this limitation, Kotzig introduced the stronger model of forbidden-transition graphs. A transition is a pair of adjacent edges (or consecutive arcs in the directed case) and a forbidden-transition graph is therefore a graph defined together with a set of pairs of adjacent edges that one may not use consecutively.
A matching minor of a graph G with a perfect matching is a graph H obtained from a subgraph H' of G, where G-H' has a perfect matching, by repeatedly contracting both edges incident with some vertex of degree two. We generalise basic ideas from the graph minor series by Robertson and Seymour to the setting of bipartite graphs with perfect matchings. In doing so we show that every bipartite, planar, and matching covered graph has the Erdős-Pósa property for matching minors.
The disjoint paths problem is a fundamental problem in
On ne considère ici que des graphes simples sans boucles. Une $k$-coloration propre de $G = (V, E)$ est une coloration des sommets de $G$ avec des couleurs de 1 à $k$ telle que deux sommets adjacents reçoivent des couleurs différentes. Une $k$-coloration des sommets à distance 2, est une $k$-coloration propre telle que toute paire de sommets à distance au plus 2 reçoivent des couleurs différentes. Le nombre chromatique à distance 2 de $G$, noté $χ^2(G)$, est le plus petit entier $k$ tel que $G$ admet une $k$-coloration à distance 2. Dans le cas général, $χ^2(G) ≤ ∆^2(G)$ où $∆(G)$ est le degré maximum du graphe. Un exemple atteignant la borne est le graphe de Petersen. L’étude des graphes épars est devenu un sujet de recherche actif, motivé par le passage de la borne quadratique à $χ^2(G) ≤ ∆(G) + c$ pour une petite constante $c$. Travail conjoint avec Petru Valicov Téléseminaire: https://bbb.lirmm.fr/b/dim-ajj-ddd
Grâce au célèbre théorème de Koebe-Andreev-Thurston on sait que tout graphe planaire peut être représenté comme le graphe de contact d'un empilement de disques dans le plan. Cependant, aucune caractérisation complète a été donnée pour les graphes de contact des empilements de boules dans l'espace. Une de famille de graphes qui se pourrait se porter comme candidat naturel est la famille des graphes qui ne sont pas intrinsèquement noués ou intrinsèquement entrelacés, i. e., les graphes que l'on peut plonger dans l'espace sans que aucun de ses cycles forment un entrelacs non-trivial. Réciproquement, on pourrait se demander si pour un entrelacs L donné quel est le nombre minimal de boules dans un empilement dont le graphe de contact contient une collection de cycles formant L. Ce nombre, appelé le ball number de L, est un invariant de noeuds introduit par Maheara qui a été peu exploré. Dans cette exposé je mettrai en évidence comment on peut utiliser la géométrie Lorentzienne discrète pour montrer d'une part que la famille des graphes intrinsèquement entrelacés et la famille des graphes de contact des empilement de boules ne sont pas comparables et d'autre part que le ball number d'un entrelacs à n croisements est au plus de 5n. Ceci est un travail en collaboration avec J. Ramírez. Téléseminaire: https://bbb.lirmm.fr/b/dim-ajj-ddd
An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions. joint work with Christian Komusiewicz, Dieter Kratsch, and Van Bang Le Téléseminaire: https://bbb.lirmm.fr/b/dim-ajj-ddd
A proper $k$-coloring of a simple graph $G$ is a function $c: V(G)\to \{1,...,k\}$ such that, for each edge $uv\in E(G)$, we have $1≤|c(u)-c(v)|$. Given a graph $G$ and a spanning subgraph $H$ of $G$, a $q$-backbone $k$-coloring of the pair $(G,H)$ is a proper $k$-coloring $c$ of $G$ such that $q≤|c(u)-c(v)|$ for each edge $uv$ in $E(H)$. A $q$-backbone $k$-coloring of $(G,H)$ is circular if $|c(u)-c(v)|≤k-q$. In their seminal paper Broersma et al. (2007) conjectured that if $G$ is planar and $T$ is a spanning tree of $G$, then $(G,T)$ admits a 2-backbone 6-coloring. They also conjectured that if $G$ is planar and $M$ is a spanning subgraph of maximum degree one, then $(G,M)$ admits a 2-backbone 5-coloring. Similar conjectures for the circular case have been proposed (with one extra color). In this talk, we present some results related to these conjectures and their corresponding circular versions obtained in distinct works coauthored by Frédéric Havet, Matthieu Schmitt, Ana Silva, Fabricio Benevides, Alexandre Cezar and Camila Araujo. Téléseminaire: https://bbb.lirmm.fr/b/dim-ajj-ddd
An (m,n)-colored-mixed graph G=(V,A Téléseminaire: https://bbb.lirmm.fr/b/dim-ajj-ddd
An $r$-arborescence $B$ is an orientation of a tree in which all arcs are directed away from a given root $r$ and the arborescence is said to This is joint work with Zoltán Szigeti. Téléseminaire: https://bbb.lirmm.fr/b/dim-ajj-ddd
We propose a new proof technique that applies to the same problems as the Lovasz Local Lemma or the entropy-compression method. In terms of upper-bounds our approach seems to be as strong as entropy-compression, but the proofs are more elementary and shorter. A path $(v_1,,,..., v_{2n})$ is repetitively colored by a coloring $C$ if for all $t$, $C(v_t)= C(v_{t+n})$. A coloring is non-repetitive if none of the paths is repetitively colored. I will present the proof technique in the context of non-repetitive colorings and use it to improve upper-bounds relating different non-repetitive chromatic numbers to the maximal degree of a graph.
For a graph parameter $\pi$, the Joint work with Paloma T. Lima, Vinicius F. dos Santos and Uéverton S. Souza, available at arXiv:2005.01460.
We consider here the area of Parameterized Complexity called «structural parameterization». The idea is to analyze the computational complexity of a problem taking into account a structural property of the input graph, which captures, informally speaking, its inherent "complexity" according to some measure. There is a whole ecology of structural parameters, cf. for instance [1]. For example, for 1) understand the link between Minimal Blocking Sets and Structural Kernelization of This talk is based on joint work with Bart M. P. Jansen and Ignasi Sau References: [1] Michael Fellows, Bart M. P. Jansen, and Frances Rosamond: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European Journal of Combinatorics, 2013. [2] Bart M. P. Jansen and Hans L. Bodlaender: Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter. Theory of Computing Systems, 2013. [3] Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Elimination distances, blocking sets,and kernels for vertex cover. [4] Marin Bougeret, Bart M. P. Jansen, and Ignasi Sau: Bridge-depth characterizes which structural parameterizations of Vertex Cover admit a polynomial kernel. ICALP 2020 [5] Marin Bougeret and Ignasi Sau. How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? Algorithmica, 2018
For a graph G, two dominating sets D and D' in G, and a non-negative integer k, the set D is said to k-
Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, Kt-free unit d-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of d-contractions, witness that the twin-width is at most d. We show that FO model checking, that is deciding if a given first-order formula ϕ evaluates to true for a given binary structure G on a domain D, is FPT in |ϕ| on classes of bounded twin-width, provided the witness is given. More precisely, being given a d-contraction sequence for G, our algorithm runs in time f(d,|ϕ|)⋅|D| where f is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS '15]. Joint work with Édouard Bonnet, Stéphan Thomassé, and Rémi Watrigant
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 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.
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. |