AlGCo homepage

Monadic second-order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independent sets, or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order n is at most 95^(n/13) and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did with minimal dominating sets can be done with any family of sets definable by a monadic second-order formula.

We introduce the parameter of block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class ${\cal G}$, the class ${\cal B}({\cal G})$ contains all graphs whose blocks belong to ${\cal G}$ and the class ${\cal A}({\cal G})$ contains all graphs where the removal of a vertex creates a graph in ${\cal G}$. Given a hereditary graph class ${\cal G}$, we recursively define ${\cal G}^{(k)}$ so that ${\cal G}^{(0)}={\cal B}({\cal G})$ and, if $k\geq 1$, ${\cal G}^{(k)}={\cal B}({\cal A}({\cal G}^{(k-1)}))$. The block elimination distance, denoted by ${\bf bed}(G)$ of a graph $G$ to a graph class ${\cal G}$ is the minimum $k$ such that $G\in{\cal G}^{(k)}$ and can be seen as an analog of the elimination distance parameter, defined in [J. Bulian and A. Dawar. Algorithmica, 75(2):363–382, 2016], with the difference that connectivity is now replaced by biconnectivity. We show that, for every non-trivial hereditary class ${\cal G}$, the problem of deciding whether $G\in{\cal G}^{(k)}$ is {\sf NP}-complete. We focus on the case where ${\cal G}$ is minor-closed and we study the minor obstruction set of ${\cal G}^{(k)}$ i.e., the minor-minimal graphs not in ${\cal G}^{(k)}$. We prove that the size of the obstructions of ${\cal G}^{(k)}$ is upper bounded by some explicit function of $k$ and the maximum size of a minor obstruction of ${\cal G}$. This implies that the problem of deciding whether $G\in{\cal G}^{(k)}$ is constructively fixed parameter tractable, when parameterized by $k$. Our results are based on a structural characterization of the obstructions of ${\cal B}({\cal G})$, relatively to the obstructions of ${\cal G}$. Finally, we give two graph operations that generate members of ${\cal G}^{(k)}$ from members of ${\cal G}^{(k-1)}$ and we prove that this set of operations is complete for the class ${\cal O}$ of outerplanar graphs. This yields the identification of all members ${\cal O}\cap{\cal G}^{(k)}$, for every $k\in\mathbb{N}$ and every non-trivial minor-closed graph class ${\cal G}$.

Joint work with Öznur Yaşar Diner, Archontia C. Giannopoulou, and Dimitrios M. Thilikos
Dimitrios M. Thilikos

In mixed search games, searchers can be put, removed from vertices, or slide along edges. There are different versions of mixed search games depending on whether the robber is visible or invisible and lazy or agile. We consider two graph searching parameters, namely the minimum number of searchers that are required for capturing a robber that is lazy and invisible or, alternatively, agile and visible. These two graph searching parameter are the only search game variants whose monotonicity remains open up to now. In our recent work, we show the monotonicity of these two graph searching variants by proving their equivalence to the «largeur arborescente» (la), a variant of treewidth defined in [Yves Colin de Verdière: Multiplicities of Eigenvalues and Tree-Width of Graphs. Journal of Combinatorial Theory, Series B 74(2): 121-146 (1998)]. The largeur arborescente, ${\bf la}(G)$, of a graph $G$ is defined as the minimum $k$ such that $G$ is a minor of $T \times K_k$ for some tree $T$. The largeur arborescente captures the tree-like structure of graphs in a smoother way than the treewidth, is parametrically equivalent to the treewidth, and treewidth can be reduced to it. In our work, we contribute to the study of largeur arborescente by giving eight different equivlalent characterizations, including an obstruction min-max charactereization that implies the monotonicity of the aforementioned mixed search games.

Joint Work with Christophe Paul and Dimitrios M. Thilikos

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).
In this work, we resolve the problem for general graphs, by showing that for any fixed $k \geq 2$, the Karger-Stein algorithm outputs any fixed minimum $k$-cut with probability at least $\widehat{O}(n^{-k})$, where $\widehat{O}(\cdot)$ hides a $2^{O(\ln \ln n)^2}$ factor. This also gives an extremal bound of $\widehat{O}(n^k)$ on the number of minimum $k$-cuts in an $n$-vertex graph and an algorithm to compute a minimum $k$-cut in similar runtime. Both are tight up to $\widehat{O}(1)$ factors. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks-and how the average degree evolves-under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-\delta) OPT/k$, using the Sunflower lemma.

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

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)$.
This is joint work with Michał Seweryn.

Est-il possible de proposer un système de vote qui soit à la fois démocratique et non manipulable ?
Kenneth Arrow a reçu en 1972 le prix Nobel d’économie pour sa réponse négative, publiée en 1951, à cette question.

Plus formellement, Arrow montre que si un vote d’au moins deux électeurs porte sur au moins 3 options que chaque électeur doit
ordonner totalement, alors il n’existe pas de fonction de vote qui ordonner totalement les options et satisfait simultanément
les propriétés suivantes :
1- unanimité : si tous les électeurs préfèrent une option à une autre, le vote doit refléter cette unanimité.
2- non-dictature : la fonction de vote ne retourne pas le vote d’un des électeurs (dictateur).
3- indépendance des solutions : le classement relatif entre deux options par la fonction de vote ne dépend
que des classements entre ces deux options pour chacun des électeurs.

La preuve de ce résultat a fait l’objet de simplifications successives pour devenir relativement simple et élégante. Nous
présenterons une preuve récente. En fonction du temps disponible, nous discuterons aussi de variantes de ce résultat.

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 $k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}.$ We denote by ${\cal A}_k ({\cal G})$ the graph class containining the graphs that are $k$-apices of ${\cal G}.$ We prove that every graph in the obstruction set of ${\cal A}_k ({\cal G}), $i.e., the minor-minimal set of graphs not belonging to ${\cal A}_k ({\cal G}),$ has size at most $2^{2^{2^{2^{poly(k)}}}},$ where ${poly}$ is a polynomial function whose degree depends on the size of the minor-obstructions of ${\cal G}.$

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 Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph $G$ and a positive integer $k$, and the objective is to decide whether $G$ contains a minimal vertex cover of size at least $k$. This problem has been considered in several articles in the last years. In this talk we focus on its kernelization, which had been almost unexplored so far. We prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover or of a maximum matching, unless NP⊆coNP/poly. Motivated by a question of Boria et al. (Discret. Appl. Math. 2015) about the existence of subquadratic kernels for MMVC parameterized by $k$, we rule out their existence unless P=NP, if we restrict the kernelization algorithms to apply only a type of natural reduction rules that we call large optimal preserving rules. In particular, these rules contain the typical reduction rules to obtain linear kernels for Vertex Cover. On the positive side, we provide subquadratic kernels on $H$-free graphs for several graphs $H$, such as the bull, the paw, or the cliques, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition.

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
in the context of kernelization. Given the "counting" nature of 𝗆𝗆𝖻𝗌, it does not seem to be expressible in monadic second-order logic, hence its tractability does not follow from Courcelle's theorem. Our main technical contribution is a fixed-parameter tractable algorithm for this problem.

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.
However, many of these results appear flawd when first encountered: The Erdős-Pósa property of butterfly minors does not appear to be linked to a topological property, and the directed version of the Flat Wall is not actually flat.
In this talk we identify two possible reasons for these flaws and show how recent advancements in the area of structural matching theory can be used, by rethinking the way we handle butterfly minors and unavoidable infinite anti-chains of them, to achieve much nicer results.

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...
We will more specifically consider nowhere dense classes of graphs: What are they? Why is this notion relevant? How to make algorithms from these graph properties?

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.
Because of their expressiveness and practical interest, the study of forbidden-transition graphs is a fast-emerging field but we are still very far from understanding them as well as regular graphs. Problems of routing, connectivity or robustness in those graphs have received growing attention in the last few decades but unfortunately, those problems generally turn out to be algorithmically very difficult, even on restricted subclasses of graphs.
In this talk, I will give an introduction to forbidden-transition graphs, present some important variants, some of the challenges that their study raises and discuss a few applications. I will present results I obtained with Benjamin Bergougnoux, Jørgen Bang-Jensen and Anders Yeo on minimum connectivity requirements. Finally, I will present an ongoing project that studies the parametrized complexity of important difficult problems in these graphs.

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.
We describe an algorithm for a matching version of the disjoint paths problem on bipartite graphs of bounded perfect matching width. Finally, by combining these results, we show that the problem of deciding whether a bipartite graph with a perfect matching contains a fixed bipartite, planar, and matching covered graph H as a matching minor is polynomial time solvable.

The disjoint paths problem is a fundamental problem in
algorithmic graph theory. For a given graph $G$ and a set of $k$ pairs
of terminals in $G$, it asks for the existence of $k$ vertex-disjoint
paths connecting each pair of terminals. Very famously, Robertson and
Seymour proved the existence of a $n^3$ algorithm for any fixed $k$ in
1995 as part of the Graph Minor project. In this talk, we focus on the
version of this problem where all the paths are required to be
shortest paths. This was first introduced as the disjoint shortest
paths problem by Eilam-Tzoreff in 1998 where she proved that the case
$k = 2$ admits a polynomial time algorithm. She also asked for the
existence of a polynomial time algorithm for any fixed $k$, a question
which remained open even for the case $k = 3$. The goal of this talk
is to prove that, for any fixed $k$, there exists a $n^{f(k)}$
algorithm for the $k$-disjoint shortest paths problem, answering
Eilam-Tzoreff's question.

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$.
On s’intéresse à la coloration à distance 2 des graphes planaires subcubiques. Plus précisément, on montre le résultat suivant : si $G$ est un graphe planaire subcubique de maille au moins 8, alors $χ^2(G) ≤ 6$. Ce résultat améliore celui de Cranston et Kim pour les graphes planaires subcubiques de maille 9 [D. Cranston and S.-J. Kim, List-coloring the square of subcubic graph, J. Graph Theory 57(1) (2008), 65–87].
La preuve est faite par déchargement. L’assistance par ordinateur joue un rôle crucial dans la vérification des charges et l’identification des configurations réductibles. L’intérêt de cette méthode est la possibilité d’améliorer la borne sur la maille des résultats existants de la forme : si $G$ est un graphe planaire de degré maximum $∆$ et de maille au moins $G$ alors $χ^2(G) ≤ ∆+c$ pour une petite constante $c$. L’encodage utilisé pour représenter les sous-graphes et l’algorithme de déchargement sont généralisables à d’autres colorations avec procédure de déchargement locale sur les graphes planaires.

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₁,A₂,⋯,A_m,E₁,E₂,⋯,E_n) is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an (m,n)-colored-mixed graph G to another (m,n)-colored-mixed graph H is a morphism φ:V(G)→V(H) such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An (m,n)-colored-mixed graph T is said to be P_g^(m,n)-universal if every graph in P_g^(m,n) (the planar (m,n)-colored-mixed graphs with girth at least g) admits a homomorphism to T. We show that planar P_g^(m,n)-universal graphs do not exist for 2m+n≥3 (and any value of g) and find a minimal (in the number vertices) planar P_g^(m,n)-universal graphs in the other cases.

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 span $V(B)$. Given a digraph $D$, an $r$-arborescence $B$ that is a subgraph of $D$ is said to be spanning if it spans $V(D)$. In 1973, Edmonds characterized digraphs admitting a packing of $k$ spanning $r$-arborescences for a fixed root $r$ and some integer $k$. It can readily be seen that this theorem can be generalized to allow fixed but distinct roots for the arborescences.
In case that some vertex cannot be reached from a given root, the only information we obtain from Edmonds theorem is that the desired packing does not exist. For this reason, in 2009, Kamiyama, Katoh and Takizawa introduced the concept of reachability arborescences. An $r$-arborescence is called a reachability $r$-arborescence if it spans all the vertices reachable from $r$ in $D$. They characterize digraphs that, for a given root multiset $R$, have a packing of arborescences $\{B_r : r ∈ R\}$ such that $B_r$ is a reachability $r$-arborescence for all $r ∈ R$. A new, shorter proof for the theorem of Kamiyama, Katoh and Takizawa will be presented. Being of inductive nature, it uses a stronger form of Edmonds’ theorem and is self-contained otherwise. Further, several ways of generalizing these concepts will be mentioned. Firstly, the condition on the arborescences to be spanning or reachability arborescences can be relaxed to more general conditions called matroid-based packing and matroid-reachability-based packing. Further, the objects of consideration can be generalized from digraphs to mixed graphs, dypergraphs and mixed hypegraphs. All the proofs considered provide efficient algorithms for finding the desired arborescences.

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 Contraction($\pi$) problem consists in, given a graph $G$ and two positive integers $k,d$, deciding whether one can contract at most $k$ edges of $G$ to obtain a graph in which $\pi$ has dropped by at least $d$. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where $\pi$ is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection H according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in H, which in particular imply that Contraction($\pi$) is co-NP-hard even for fixed $k=d=1$ when $\pi$ is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when $\pi$ is the size of a minimum vertex cover, the problem is in XP parameterized by $d$.

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 VC (the classical Vertex Cover problem consisting in, given a graph $G$ and an integer parameter $k$, deciding whether $G$ contains at most $k$ vertices intersecting all its edges) one can consider VC parameterized by $κ$, where the parameter $κ(G, k)$ is not necessarily $k$, but a function depending on $G$, such as the treewidth of $G$. Kernelization considering structural parameters has grown dramatically thanks to [2], which proves that VC/FVS (meaning VC parameterized by the size of a feedback vertex set) admits a polynomial kernel, that is, a polynomial-time algorithm that transforms an instance into an equivalent one with size polynomially bounded in terms of the parameter. As occurs quite often in Parameterized Complexity, the Vertex Cover problem played a triggering role in this area as a "simple" but still fundamental problem, for which the ultimate quest would be characterize for which graph parameters $p$ the problem VC$/p$ admits a polynomial kernel, subject to reasonable complexity assumptions. This quest has motivated a number of recent research articles. In this talk, I will present some techniques that are used in several papers of this area. The goal is to

1) understand the link between Minimal Blocking Sets and Structural Kernelization of VC.
2) explain how kernels like [2,4,5] are obtained
3) explain what is the result of [4] which almost answer the ultimate quest

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-transform to D' if there is a sequence D_0,…,D_ℓ of dominating sets in G such that D=D_0,D'=D_ℓ,|D_i|≤k for every i∈{0,1,…,ℓ}, and D_i arises from D_{i-1} by adding or removing one vertex for every i∈{1,…,ℓ}. We prove that there is some positive constant c and there are toroidal graphs G of arbitrarily large order n, and two minimum dominating sets D and D' in G such that D k-transforms to D' only if k≥max{|D|,|D'|}+c√n. Conversely, for every hereditary class G that has balanced separators of order n↦n^α for some α<1, we prove that there is some positive constant C such that, if G is a graph in G of order n, and D and D' are two dominating sets in G, then D k-transforms to D' for k=max{|D|,|D'|}+⌊Cn^α⌋.

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

http://bbb.lirmm.fr/b/dim-ajj-ddd

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

http://bbb.lirmm.fr/b/dim-ajj-ddd

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

http://bbb.lirmm.fr/b/dim-ajj-ddd

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.

https://moodle.umontpellier.fr/enrol/index.php?id=15640

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

https://moodle.umontpellier.fr/course/view.php?id=15640

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

https://moodle.umontpellier.fr/course/view.php?id=15640

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

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

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

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.

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.

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

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

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.

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.

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.

AlGCo : algorithmes, graphes et combinatoire

Responsable : Emeric Gioan

Département Informatique - LIRMM