Abstract In the Token Sliding problem we are given a graph G and two independent sets $$I_s$$ I s and $$I_t$$ I t in G of size $$k \ge 1$$ k ≥ 1 . The goal is to decide whether there exists a sequence $$\langle I_1, I_2, \ldots , I_\ell \rangle $$ ⟨ I 1 , I 2 , … , I ℓ ⟩ of independent sets such that for all $$j \in \{1,\ldots , \ell - 1\}$$ j ∈ { 1 , … , ℓ - 1 } the set $$I_j$$ I j is an independent set of size k, $$I_1 = I_s$$ I 1 = I s , $$I_\ell = I_t$$ I ℓ = I t and $$I_j \triangle I_{j + 1} = \{u, v\} \in E(G)$$ I j ▵ I j + 1 = { u , v } ∈ E ( G ) . Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms $$I_s$$ I s into $$I_t$$ I t where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by k. As shown by Bartier et al. (Algorithmica 83(9):2914–2951, 2021. https://doi.org/10.1007/s00453-021-00848-1 ), the problem is -hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant $$p \ge 5$$ p ≥ 5 such that the problem becomes fixed-parameter tractable on graphs of girth at least p. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph.

Given a graph G and two independent sets I_s and I_t of size k, the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets that transforms I_s to I_t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G, the two most studied reconfiguration steps are token jumping and token sliding. Over a series of papers, it was shown that the Token Jumping problem is fixed-parameter tractable when restricted to sparse graph classes, such as planar, bounded treewidth, and nowhere-dense graphs. As for the Token Sliding problem almost nothing is known. We remedy this situation by showing that Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number.

Abstract. For a positive integer [Formula: see text], the [Formula: see text]-recoloring graph of a graph [Formula: see text] has as vertex set all proper [Formula: see text]-colorings of [Formula: see text] with two [Formula: see text]-colorings being adjacent if they differ by the color of exactly one vertex. A result of Dyer et al. regarding graphs of bounded degeneracy implies that the 7-recoloring graphs of planar graphs, the 5-recoloring graphs of triangle-free planar graphs and the 4-recoloring graphs planar graphs of girth at least six are connected. On the other hand, there are planar graphs whose 6-recoloring graph is disconnected, triangle-free planar graphs whose 4-recoloring graph is disconnected, and planar graphs of any given girth whose 3-recoloring graph is disconnected. The main result of this paper consists in showing, via a novel application of the discharging method, that the 4-recoloring graph of every planar graph of girth five is connected. This completes the classification of the connectedness of the recoloring graph for planar graphs of given girth. We also prove some theorems regarding the diameter of the recoloring graph of planar graphs.

We introduce the problem of selecting patient-donor pairs in a kidney exchange program to undergo a crossmatch test, and we model this selection problem as a two-stage stochastic integer programming problem. The optimal solutions of this new formulation yield a larger expected number of realized transplants than previous approaches based on internal recourse or subset recourse. We settle the computational complexity of the selection problem by showing that it remains NP-hard even for maximum cycle length equal to two. Furthermore, we investigate to what extent different algorithmic approaches, including one based on Benders decomposition, are able to solve instances of the model. We empirically investigate the computational efficiency of this approach by solving randomly generated instances and study the corresponding running times as a function of maximum cycle length, and of the presence of nondirected donors. Summary of Contribution: This paper deals with an important and very complex issue linked to the optimization of transplant matchings in kidney exchange programs, namely, the inherent uncertainty in the assessment of compatibility between donors and recipients of transplants. Although this issue has previously received some attention in the optimization literature, most attempts to date have focused on applying recourse to solutions selected within restricted spaces. The present paper explicitly formulates the maximization of the expected number of transplants as a two-stage stochastic integer programming problem. The formulation turns out to be computationally difficulty, both from a theoretical and from a numerical perspective. Different algorithmic approaches are proposed and tested experimentally for its solution. The quality of the kidney exchanges produced by these algorithms compares favorably with that of earlier models.

This document describes our exact Cluster Editing solver, PaSTEC, which got the third place in the 2021 PACE Challenge.

International audience

In the Token Jumping problem we are given a graph $$G = (V,E)$$ and two independent sets S and T of G, each of size $$k \ge 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 \varDelta 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 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. 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 Token Sliding and Token Jumping are fixed-parameter tractable on $$C_4$$ -free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on $$\{C_3,C_4\}$$ -free graphs. In the case of 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 \ge 4$$ , both problems are W[1]-hard on $$\{C_4, \dots , C_p\}$$ -free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.

Let $k$ and $d$ be such that $k \ge d+2$. Consider two $k$-colorings of a $d$-degenerate graph $G$. Can we transform one into the other by recoloring 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. 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 prove that, as long as $k \ge d+4$, there exists a transformation of length at most $f(Δ) \cdot n$ between any pair of $k$-colorings of chordal graphs (where $Δ$ 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 a linear transformation between $c_1$ and $c_2$.