AlGCo : algorithmes, graphes et combinatoire

Responsable : Mickael Montassier

Département Informatique - LIRMM

Accueil | Annonces | Membres | Projets | Visiteurs | Publications | 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).

Contact : Marin Bougeret

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é
04 juin 2020 (salle : Téléseminaire)
Dimitrios M. Thilikos (Équipe AlGCo)
A Detaild Exposition of The Flat Wall theorem

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)

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)

18 juin 2020 (salle : Téléseminaire)
Ignasi Sau (Équipe AlGCo)
On the complexity of finding large odd induced subgraphs and odd colorings

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.
- FPT algorithms in time $2^{O(rw)}poly(n)$ and $2^{O(q \cdot rw)}poly(n)$ to compute $mos(G)$ and to decide whether $\chi_{odd}(G) \leq q$ on an $n$-vertex graph $G$ of rank-width at most $rw$, respectively. The dependency on rank-width is asymptotically optimal under the ETH.
- Some tight bounds for these parameters on restricted graph classes or in relation to other parameters.

Joint work with Rémy Belmonte

11 juin 2020 (salle : Téléseminaire)
Ana Karolinna Maia (Universidade Federal do Ceará, Fortaleza, Ceará, Brazil)
Characterizing networks admitting multiple arc-disjoint branching flows

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

04 juin 2020 (salle : Téléseminaire)
Dimitrios M. Thilikos (Équipe AlGCo)
A Detaild Exposition of The Flat Wall theorem

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.

28 mai 2020
Christophe Paul (Équipe AlGCo)
A linear fixed parameter tractable algorithm for connected pathwidth

The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy is to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable, in particular we design a $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connected pathwidth of $G$ is at most $k.$ This resolves an open question by [Dereniowski, Osula, and Rzążewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85–100, 2019}]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358–402, 1996}] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a «global» demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a $2^{O(k^2)}\cdot n$ time algorithm for the monotone and connected version of the edge search number.

Joint work with Mamadou Moustapha Kanté and Dimitrios M. Thilikos

14 mai 2020
Júlio Araújo (Universidade Federal do Ceará, Fortaleza, Ceará, Brazil)
Weighted proper orientations of trees and graphs of bounded treewidth

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

09 janvier 2020
Andreas Schmid ()
A New Approach for the Maximum Planar Subgraph Problem

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.

19 décembre 2019
Marc Heinrich (University of Leeds, School of Computing, United Kingdom)
Counting independent sets in strongly orderable graphs

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.

12 décembre 2019
Dimitrios Thilikos (LIRMM, Algco)
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

For a finite collection of graphs ${\cal F}$, the ${\cal F}$-TM-Deletion problem has as input an $n$-vertex
graph $G$ and an integer $k$ and asks whether there exists a set $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a topological minor. We prove that for every such ${\cal F}$, ${\cal F}$-TM-Deletion
is fixed parameter tractable on planar graphs. In particular, we provide an $f(h,k)\cdot n^{2}$ algorithm where $h$ is an upper bound to the vertices of the graphs in ${\cal F}$.

Joint work with Petr A. Golovach and Giannos Stamoulis

06 novembre 2019
Uéverton S. Souza (Universidade Federal Fluminense, Niterói, Brazil)
Computing the largest bond of a graph

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.

26 septembre 2019
Petr A. Golovach ()
Parameterized Low-Rank Binary Matrix Approximation

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

06 juin 2019
Kolja Knauer (Université Aix-Marseille, Laboratoire d'Informatique et des Systèmes (LIS), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO))
Generating k-connected orientations Transparents de l'exposé

We present a simple algorithm, that given a graph G generates
all of its k-arc-connected orientations. Its amortized runtime is
basically the same as the one of an algorithm that can be extracted from the theory of submodular flows. The latter is however rather intricate.

Another nice thing is, that our algorithm actually consists of two
modules of independent interest:
1. an algorithm that generates all orientations of G with prescribed
outdegree sequence,
2. an algorithm that generates all outdegree sequences of k-connected orientations of G.

Joint work with Sarah Blind and Petru Valicov

23 mai 2019
Stéphan Thomassé (ENS Lyon)
Computing Maximum Independent Set in Graph Classes

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

16 mai 2019
Archontia Giannopoulou (Department of Informatics and Telecommunications, National and Kapodistrian University of Athens,Greece)
Braces of Perfect Matching Width 2

A graph G is called matching covered
if it is connected and every edge is contained in
a perfect matching. Perfect matching width is a
width parameter for matching covered graphs
based on a branch decomposition that can be
considered a generalisation of directed treewidth.
We show that the perfect matching width of every
bipartite matching covered graph is within a factor
of 2 of the perfect matching width of its braces.
Moreover, we give characterisations for braces
of perfect matching width in terms of edge maximal
graphs similar to k-trees for undirected treewidth
and elimination orderings. The latter allows us to
identify braces of perfect matching width 2 in
polynomial time and provides an algorithm to
construct an optimal decomposition.

28 mars 2019
Jayakrishnan Madathil (IMSC, Chennai)
Connecting the Dots (with Minimum Crossings)

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).
We are interested in testing whether G has a subgraph with certain properties (such as, being a perfect matching), and at the same time, has only a given number of crossings.

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.
Specifically, we study the following problems. Here, the input is a two-layered graph G and a non-negative integer k.

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.

21 mars 2019
Rémy Belmonte (University of Electro-Communications , Tokyo, Japan)
Token Sliding on Split Graphs

We consider the complexity of the Independent Set
Reconfiguration problem under the Token Sliding rule. In this problem we are
given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with
one of its neighbors, while maintaining the set independent. Our main result is
to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then
go on to consider the $c$-Colorable Reconfiguration problem
under the same rule, where the constraint is now to maintain the set
$c$-colorable at all times.

Joint work with Eun-Jung Kim, Michael Lampis, Valia Mitsou, Yota
Otachi and Florian Sikora.

07 février 2019
Guilherme Gomes (Departamento de Ciência da Computação, Universidade Feder al de Minas Gerais, Belo Horizonte, Brazil)
On the complexity of finding cuts of bounded degree

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.

17 janvier 2019
Ana Silva (Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil)
Graphs with small fall-spectrum

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.

06 décembre 2018
Mohammed SENHAJI ()
Neighbour-distinguishing decompositions of graphs

The main question taht we explore was introduced by Karonski, Luczak and
Thomason in [KLT04] : Can we weight the edges of a graph G , with weights 1 ,2 , and 3 , such that any two of adjacent vertices of G are distinguished by the sum of their incident weights ? This question later becomes the famous 1-2-3 Conjecture.

In this presentation we explore several variants of the 1-2-3 Conjecture, and
their links with locally irregular decompositions. We are interested in both
optimisation results and algorithmic problems. We first introduce an equitable version of the neighbour-sum-distinguishing edge-weightings, that is a variant where we require every edge weight to be used the same number of times up to a difference of 1. Then we explore an injective variant where each edge is assigned a different weight, which yields necessarily an equitable weighting. This gives us first general upper bounds on the equitable version. Moreover, the injective variant is also a local version of the well-known antimagic labelling. After that we explore how neighbour-sum-distinguishing weightings behave if we require sums of neighbouring vertices to differ by at least 2 . Namely, we present results on the smallest maximal weight needed to construct such weightings for some classes of graphs, and study some algorithmic aspects of this problem. Due
to the links between neighbour-sum-distinguishing edge weightings and locally irregular decompositions, we also explore the locally irregular index of subcubic graphs, along with other variants of the locally irregular decomposition problem. Finally, we present a more general work toward a general theory unifying neighbour-sum-distinguishing edge-weightings and locally irregular decompositions.

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.

[KLT04] M. Karonski, T. Luczak, and A. Thomason. Edge weights and vertex
colours. Journal of Combinatorial Theory, Series B , 91(1):151-157, 2004.

29 novembre 2018
Alan Diego Aurélio Carneiro (Universidade Federal Fluminense (UFF), Niterói, Rio de Janeiro, Brasil)
Complexity Analysis of Deadlock Resolution Graph Problems.

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.

22 novembre 2018
Victor A. Campos (Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brasil)
Free Lula Trees

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

25 octobre 2018
Raul Lopes (Federal university of Ceara - UFC Pargo Group)
Disjoint paths, grids and tree-width: the directed case.

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.

18 octobre 2018
Aniket Basu Roy (LIRMM, Algco/Maore (and previously Indian Institute of Science located, Bangalore, India))
Effectiveness of Local Search for Geometric Packing and Covering Problems

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.

11 octobre 2018
Tom Kelly (University of Waterloo, Department of Combinatorics and Optimization,)
On the density of critical graphs without large cliques

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.

27 septembre 2018
Vinicius Fernandes dos Santos (Universidade Federal de Minas Gerais - UFMG)
Characterization, probe and sandwich problems on a generalization of threshold graphs

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.

20 septembre 2018
Lucia Penso (Universität Ulm Institut für Optimierung und Operations Research)
Dynamic monopolies and Vaccination Transparents de l'exposé


13 septembre 2018
Guilherme Gomes ()
Parameterized Complexity of Equitable Coloring and Intersection Graphs of maximal stars

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.

06 septembre 2018
Dieter Rautenbach ()
On the maximum number of minimum dominating sets, minimum total dominating sets, and maximum independent sets Transparents de l'exposé

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.