Search Results

Documents authored by Bartier, Valentin

Document
DOI: 10.4230/LIPIcs.ESA.2022.15
Galactic Token Sliding

Authors: Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
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 (each of size k) I_s = I₀, I₁, I₂, …, I_𝓁 = 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. In the Token Jumping variant of the problem, a single step allows a token to jump from one vertex to any other vertex in the graph. In the Token Sliding variant, a token is only allowed to slide from a vertex to one of its neighbors. Like the Independent Set problem, both of the aforementioned problems are known to be W[1]-hard on general graphs (for parameter k). A very fruitful line of research [Bodlaender, 1988; Grohe et al., 2017; Telle and Villanger, 2019; Pilipczuk and Siebertz, 2021] has showed that the Independent Set problem becomes fixed-parameter tractable when restricted to sparse graph classes, such as planar, bounded treewidth, nowhere-dense, and all the way to biclique-free graphs. Over a series of papers, the same was shown to hold for the Token Jumping problem [Ito et al., 2014; Lokshtanov et al., 2018; Siebertz, 2018; Bousquet et al., 2017]. As for the Token Sliding problem, which is mentioned in most of these papers, almost nothing is known beyond the fact that the problem is polynomial-time solvable on trees [Demaine et al., 2015] and interval graphs [Marthe Bonamy and Nicolas Bousquet, 2017]. We remedy this situation by introducing a new model for the reconfiguration of independent sets, which we call galactic reconfiguration. Using this new model, we show that (standard) Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. We believe that the galactic reconfiguration model is of independent interest and could potentially help in resolving the remaining open questions concerning the (parameterized) complexity of Token Sliding.
Cite as

Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad. Galactic Token Sliding. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.ESA.2022.15,
  author =	{Bartier, Valentin and Bousquet, Nicolas and Mouawad, Amer E.},
  title =	{{Galactic Token Sliding}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.15},
  URN =		{urn:nbn:de:0030-drops-169535},
  doi =		{10.4230/LIPIcs.ESA.2022.15},
  annote =	{Keywords: reconfiguration, independent set, galactic reconfiguration, sparse graphs, token sliding, parameterized complexity}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2021.29
PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters

Authors: Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

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

Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 29:1-29:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.IPEC.2021.29,
  author =	{Bartier, Valentin and Bathie, Gabriel and Bousquet, Nicolas and Heinrich, Marc and Pierron, Th\'{e}o and Prieto, Ulysse},
  title =	{{PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{29:1--29:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.29},
  URN =		{urn:nbn:de:0030-drops-154129},
  doi =		{10.4230/LIPIcs.IPEC.2021.29},
  annote =	{Keywords: cluster editing, exact algorithm, star packing, twins}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2021.33
PACE Solver Description: μSolver - Heuristic Track

Authors: Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
This document describes our heuristic Cluster Editing solver, μSolver, which got the third place in the 2021 PACE Challenge. We present the local search and kernelization techniques for Cluster Editing that are implemented in the solver.
Cite as

Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. PACE Solver Description: μSolver - Heuristic Track. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 33:1-33:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.IPEC.2021.33,
  author =	{Bartier, Valentin and Bathie, Gabriel and Bousquet, Nicolas and Heinrich, Marc and Pierron, Th\'{e}o and Prieto, Ulysse},
  title =	{{PACE Solver Description: \muSolver - Heuristic Track}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{33:1--33:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.33},
  URN =		{urn:nbn:de:0030-drops-154161},
  doi =		{10.4230/LIPIcs.IPEC.2021.33},
  annote =	{Keywords: kernelization, graph editing, clustering, local search}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.44
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Authors: Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
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 ≥ 1. The goal is to determine whether there exists a sequence of k-sized independent sets in G, 〈S_0, S_1, ..., S_𝓁〉, such that for every i, |S_i| = k, S_i is an independent set, S = S_0, S_𝓁 = T, and |S_i Δ 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 ≥ 4, both problems are W[1]-hard on {C_4, ..., C_p}-free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.
Cite as

Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad. On Girth and the Parameterized Complexity of Token Sliding and Token Jumping. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 44:1-44:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.ISAAC.2020.44,
  author =	{Bartier, Valentin and Bousquet, Nicolas and Dallard, Cl\'{e}ment and Lomer, Kyle and Mouawad, Amer E.},
  title =	{{On Girth and the Parameterized Complexity of Token Sliding and Token Jumping}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{44:1--44:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.44},
  URN =		{urn:nbn:de:0030-drops-133886},
  doi =		{10.4230/LIPIcs.ISAAC.2020.44},
  annote =	{Keywords: Combinatorial reconfiguration, Independent Set, Token Jumping, Token Sliding, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.24
Linear Transformations Between Colorings in Chordal Graphs

Authors: Nicolas Bousquet and Valentin Bartier

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Let k and d be such that k >= 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 >= d+4, there exists a transformation of length at most f(Delta) * 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 a linear transformation between c_1 and c_2.
Cite as

Nicolas Bousquet and Valentin Bartier. Linear Transformations Between Colorings in Chordal Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ESA.2019.24,
  author =	{Bousquet, Nicolas and Bartier, Valentin},
  title =	{{Linear Transformations Between Colorings in Chordal Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.24},
  URN =		{urn:nbn:de:0030-drops-111459},
  doi =		{10.4230/LIPIcs.ESA.2019.24},
  annote =	{Keywords: graph recoloring, chordal graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact