Reconfiguration de Graphes (GrR)

C. Brosse, A. Lagoutte, V. Limouzy, A. Mary et L. Pastor, Efficient enumeration of maximal split subgraphs and sub-cographs and related classes

In this paper, we are interested in algorithms that take in input an arbitrary graph $G$, and that enumerate in output all the (inclusion-wise) maximal ``subgraphs'' of $G$ which fulfil a given property $\Pi$. All over this paper, we study several different properties $\Pi$, and the notion of subgraph under consideration (induced or not) will vary from a result to another.

More precisely, we present efficient algorithms to list all maximal split subgraphs, sub-cographs and some subclasses of cographs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal independent sets of an auxiliary graph. For cographs and some subclasses , the algorithms rely on a framework recently introduced by Conte \& Uno \cite{conte-uno} called \emph{Proximity Search}. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property $\Pi$ that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every ``interesting'' hereditary property $\Pi$. We extend the hardness result to some specific edge version of the extension problem.

https://arxiv.org/abs/2007.01031

N. Bousquet et M. Heinrich, A polynomial version of Cereceda's conjecture

Let `k` and `d` be such that `k \ge d+2`. Consider two `k`-colourings of a `d`-degenerate graph `G`. Can we transform one into the other by recolouring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. However, Cereceda conjectured that there should exist one of quadratic length. The `k`-reconfiguration graph of G is the graph whose vertices are the proper `k`-colourings of `G`, with an edge between two colourings if they differ on exactly one vertex. Cereceda's conjecture can be reformulated as follows: the diameter of the `(d+2)`-reconfiguration graph of any `d`-degenerate graph on `n` vertices is `O(n^2)`. So far, the existence of a polynomial diameter is open even for `d=2`. In this paper, we prove that the diameter of the k-reconfiguration graph of a `d`-degenerate graph is `O(n^{d+1})` for `k \ge d+2`. Moreover, we prove that if ` k \ge \frac 32(d+1)` then the diameter of the `k`-reconfiguration graph is quadratic, improving the previous bound of `k \ge 2d+1`. We also show that the `5`-reconfiguration graph of planar bipartite graphs has quadratic diameter, confirming Cereceda's conjecture for this class of graphs.

https://arxiv.org/abs/1903.05619

M. Bonamy, O. Defrain, M. Heinrich, M. Pilipczuk and Jean Florent Raymond%, Enumerating minimal dominating sets in $K_t$-free graphs and variants
ACM Transactions on Algorithms (2020).

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this article we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for $K_t$-free graphs and for several related graph classes. This answers a question of Kanté et al. about enumeration in bipartite graphs.

https://arxiv.org/abs/1810.00789

N. Bousquet, T. Ito, Y. Kobayashi, H. Mizuta, P. Ouvrard, A. Suzuki et K. Wasa, Reconfiguration of Spanning Trees with Many or Few Leaves
European Symposium on Algorithms (ESA 2020)

Let $G$ be a graph and $T_1,T_2$ be two spanning trees of $G$. We say that $T_1$ can be transformed into $T_2$ via an edge flip if there exist two edges $e \in T_1$ and $f$ in $T_2$ such that $T_2= (T_1 \setminus e) \cup f$. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed by Ito et al.

We investigate the problem of determining, given two spanning trees $T_1,T_2$ with an additional property $\Pi$, if there exists an edge flip transformation from $T_1$ to $T_2$ keeping property $\Pi$ all along.

First we show that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at most $k$ (for any fixed $k \ge 3$) leaves is PSPACE-complete.

We then prove that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at least $k$ leaves (where $k$ is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when $k=n-2$.

https://arxiv.org/abs/2006.14309

V. Bartier, N. Bousquet, C. Dallard, K. Lomer et A. Mouawad, On girth and the parameterized complexity of token sliding and token jumping
International Symposium on Algorithms and Computation (ISAAC 2020)

In the {\sc Token Jumping} problem we are given a graph $G = (V,E)$ and two independent sets $S$ and $T$ of $G$, each of size $k \geq 1$. The goal is to determine whether there exists a sequence of $k$-sized independent sets in $G$, $\langle S_0, S_1, \ldots, S_\ell \rangle$, such that for every $i$, $|S_i| = k$, $S_i$ is an independent set, $S = S_0$, $S_\ell = T$, and $|S_i \Delta S_{i+1}| = 2$. In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of $G$, then the problem asks for a sequence of independent sets which transforms $S$ to $T$ by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the {\sc Token Sliding} problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. {\sc Token Sliding} is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both {\sc Token Sliding} and {\sc Token Jumping} are fixed-parameter tractable on $C_4$-free bipartite graphs when parameterized by $k$. For {\sc Token Jumping}, we in fact show that the problem admits a polynomial kernel on $\{C_3,C_4\}$-free graphs. In the case of {\sc Token Sliding}, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant $p \geq 4$, both problems are W[1]-hard on $C_\ell$-free graphs, where $4 \leq \ell \leq p$, and {\sc Token Sliding} remains W[1]-hard even on bipartite graphs.

https://arxiv.org/abs/2006.16726

N. Bousquet, A. Joffard et P. Ouvrard, Linear transformations between dominating sets in the TAR-model
International Symposium on Algorithms and Computation (ISAAC 2020)

Given a graph $G$ and an integer $k$, a token addition and removal ({\sf TAR} for short) reconfiguration sequence between two dominating sets $D_\source$ and $D_\target$ of size at most $k$ is a sequence $S= \langle D_0 = D_\source, D_1 \ldots, D_\ell = D_\target \rangle$ of dominating sets of $G$ such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than $k$.

We first improve a result of Haas and Seyffarth~\cite{Haas17}, by showing that if $k=\Gamma(G)+\alpha(G)-1$ (where $\Gamma(G)$ is the maximum size of a minimal dominating set and $\alpha(G)$ the maximum size of an independent set), then there exists a linear {\sf TAR} reconfiguration sequence between any pair of dominating sets.

We then improve these results on several graph classes by showing that the same holds for $K_{\ell}$-minor free graph as long as $k \ge \Gamma(G)+O(\ell \sqrt{\log \ell})$ and for planar graphs whenever $k \ge \Gamma(G)+3$. Finally, we show that if $k=\Gamma(G)+tw(G)+1$, then there also exists a linear transformation between any pair of dominating sets.

https://arxiv.org/abs/2006.16726

V. Dujmović, L. Esperet, C. Gavoille, G. Joret, P. Micek, and P. Morin, Adjacency Labelling for Planar Graphs (and Beyond)
Symposium on Foundations of Computer Science (FOCS 2020)

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an `n`-vertex planar graph `G` is assigned a `(1+o(1)) log_2 n`-bit label and the labels of two vertices `u` and `v` are sufficient to determine if `uv` is an edge of `G`. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every `n`, there exists a graph `U_n` with `n^{1+o(1)}` vertices such that every `n`-vertex planar graph is an induced subgraph of `U_n`. These results generalize to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

arXiv:2003.04280

V. Dujmović, L. Esperet, G. Joret, B. Walczak, et D.R. Wood, Planar graphs have bounded nonrepetitive chromatic number
Advances in Combinatorics 2020:5, 11pp.

A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the second half. We show that planar graphs have nonrepetitive colourings with a bounded number of colours, thus proving a conjecture of Alon, Grytczuk, Haluszczak and Riordan (2002). We also generalise this result for graphs of bounded Euler genus, graphs excluding a fixed minor, and graphs excluding a fixed topological minor.

arXiv:1904.05269

N. Bousquet, W. Cames van Batenburg, L. Esperet, G. Joret, W. Lochet, C. Muller, et F. Pirot, Packing and covering balls in graphs excluding a minor
Combinatorica (2020)

We prove that for every integer `t >=1` there exists a constant `c_t` such that for every `K_t`-minor-free graph `G`, and every set `S` of balls in `G`, the minimum size of a set of vertices of `G` intersecting all the balls of `S` is at most `c_t` times the maximum number of vertex-disjoint balls in `S`. This was conjectured by Chepoi, Estellon, and Vaxès in 2007 in the special case of planar graphs and of balls having the same radius.

arXiv:2001.04517

Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma et T. Pierron, Graph Isomorphism for (H1,H2)-free Graphs: An Almost Complete Dichotomy
Algorithmica (2020).

We resolve the computational complexity of {\sc Graph Isomorphism} for classes of graphs characterized by two forbidden induced subgraphs~$H_1$ and~$H_2$ for all but six pairs $(H_1,H_2)$. Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that {\sc Graph Isomorphism} is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between {\sc Graph Isomorphism} and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for $(H_1,H_2)$-free graphs to five.

https://arxiv.org/abs/1811.12252

N. Bousquet et B. Durain, A note on the simultaneous edge coloring
Discrete Mathematics, 343(5): 111781 (2020).

Let $G=(V,E)$ be a graph. A \emph{(proper) $k$-edge-coloring} is a coloring of the edges of $G$ such that any pair of edges sharing an endpoint receive distinct colors. A classical result of Vizing~\cite{Vizing64} ensures that any simple graph $G$ admits a $(\Delta(G)+1)$-edge coloring where $\Delta(G)$ denotes the maximum degreee of $G$. Recently, Cabello raised the following question: given two graphs $G_1,G_2$ of maximum degree $\Delta$ on the same set of vertices $V$, is it possible to edge-color their (edge) union with $\Delta+2$ colors in such a way the restriction of $G$ to respectively the edges of $G_1$ and the edges of $G_2$ are edge-colorings? More generally, given $\ell$ graphs, how many colors do we need to color their union in such a way the restriction of the coloring to each graph is proper?

In this short note, we prove that we can always color the union of the graphs $G_1,\ldots,G_\ell$ of maximum degree $\Delta$ with $\Omega(\sqrt{\ell} \cdot \Delta)$ colors and that there exist graphs for which this bound is tight up to a constant multiplicative factor. Moreover, for two graphs, we prove that at most $\frac 32 \Delta +4$ colors are enough which is, as far as we know, the best known upper bound.

https://arxiv.org/abs/2001.01463

N. Bousquet et A. Joffard, Approximating Shortest Connected Graph Transformation for Trees
SOFSEM 2020, pages 76-87.

Let $G,H$ be two connected graphs with the same degree sequence. The aim of this paper is to find a transformation from $G$ to $H$ via a sequence of flips maintaining connectivity. A flip of $G$ is an operation consisting in replacing two existing edges $uv,xy$ of $G$ by $ux$ and $vy$.

Taylor showed that there always exists a sequence of flips that transforms $G$ into $H$ maintaining connectivity. Bousquet and Mary proved that there exists a $4$-approximation algorithm of a shortest transformation. In this paper, we show that there exists a $2.5$-approximation algorithm running in polynomial time. We also discuss the tightness of the lower bound and show that, in order to drastically improve the approximation ratio, we need to improve the best known lower bounds.

https://hal.archives-ouvertes.fr/hal-02358489/

L. Esperet et M. Stehlík, Bipartite complements of circle graphs
Discrete Mathematics 343(6) (2020), 111834.

Using an algebraic characterization of circle graphs, Bouchet proved in 1999 that if a bipartite graph `G` is the complement of a circle graph, then `G` is a circle graph. We give an elementary proof of this result.

arXiv:1910.08388 doi:10.1016/j.disc.2020.111834

M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi , A. Mary , M. Mühlenthaler et K. Wasa, The Perfect Matching Reconfiguration Problem
Mathematical Foundations of Computer Science (MFCS 2019), 24:1--24:15

We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as `P_4`-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.

https://arxiv.org/abs/1904.06184

V. Bartier et N.Bousquet, Linear Transformations Between Colorings in Chordal Graphs
42th Annual European Symposium on Algorithms (ESA 2019), 24:1--24:15

Let $k$ and $d$ be such that $k\ge d+ 2$. Consider two $k$-colorings of a $d$-degenerate graph $G$. Canwe transform one into the other by recoloring one vertex at each step while maintaining a propercoloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited arecolouring sequence of exponential length.If $k=d+ 2$, we know that there exists graphs for which a quadratic number of recolorings is needed. And when $k= 2d+ 2$, there always exists a linear transformation. In this paper, we provethat, as long as $k \ge d+ 4$, there exists a transformation of length at most $f(\Delta)\cdot n$ between any pair of $k$-colorings of chordal graphs (where $\Delta$ denotes the maximum degree of the graph). The proof is constructive and provides a linear time algorithm that, given two $k$-colorings $c_1, c_2$ computes alinear transformation between $c_1$ and $c_2$.

https://arxiv.org/abs/1907.01863

N. Bousquet, T. Hatanaka, T. Ito et M. Mühlenthaler, Shortest Reconfiguration of Matchings
45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019)

Imagine that unlabelled tokens are placed on edges forming a matching of a graph. A token can be moved to another edge provided that the edges containing tokens remain a matching. The distance between two configurations of tokens is the minimum number of moves required to transform one into the other. We study the problem of computing the distance between two given configurations. We prove that if source and target configurations are maximal matchings, then the problem admits no polynomial-time sublogarithmic-factor approximation algorithm unless $𝖯=𝖭𝖯$. On the positive side, we show that for matchings of bipartite graphs the problem is fixed-parameter tractable parameterized by the size d of the symmetric difference of the two given configurations. Furthermore, we obtain a 𝑑𝜀-factor approximation algorithm for the distance of two maximum matchings of bipartite graphs for every $\epsilon>0$. The proofs of our positive results are constructive and can hence be turned into algorithms that output shortest transformations. Both algorithmic results rely on a close connection to the Directed Steiner Tree problem. Finally, we show that determining the exact distance between two configurations is complete for the class 𝖣𝖯, and determining the maximum distance between any two configurations of a given graph is DP-hard.

https://arxiv.org/abs/1812.05419

E. Bamas et L. Esperet, Local approximation of the Maximum Cut in regular graphs
45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019)

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least `1/2` in average. When the graph is `d`-regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MAXCUT in regular graphs. We first prove that if `G` is `d`-regular, with `d` even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of `1/d` for `d`-regular graphs with `d` odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio `1/d+\epsilon` (with `\epsilon>0`) can run in a constant number of rounds. We also prove results of a similar flavour for the MAXDICUT problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut.

arXiv:1902.04899