6 Search Results for "Pierron, Théo"

Document
DOI: 10.4230/LIPIcs.OPODIS.2021.22
Local Certification of Graph Decompositions and Applications to Minor-Free Classes

Authors: Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph G belongs to a given graph class 𝒢. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this work, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds using a new proof technique.
Cite as

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.22,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o},
  title =	{{Local Certification of Graph Decompositions and Applications to Minor-Free Classes}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.22},
  URN =		{urn:nbn:de:0030-drops-157970},
  doi =		{10.4230/LIPIcs.OPODIS.2021.22},
  annote =	{Keywords: Local certification, proof-labeling schemes, locally checkable proofs, graph decompositions, minor-free graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.8
(Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes

Authors: Gabriel Bathie, Nicolas Bousquet, and Théo Pierron

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

Abstract
In a (parameterized) graph edge modification problem, we are given a graph G, an integer k and a (usually well-structured) class of graphs 𝒢, and ask whether it is possible to transform G into a graph G' ∈ 𝒢 by adding and/or removing at most k edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a 2k kernel [Cao and Chen, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size O(k/log k). We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH.
Cite as

Gabriel Bathie, Nicolas Bousquet, and Théo Pierron. (Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bathie_et_al:LIPIcs.IPEC.2021.8,
  author =	{Bathie, Gabriel and Bousquet, Nicolas and Pierron, Th\'{e}o},
  title =	{{(Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{8:1--8:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.8},
  URN =		{urn:nbn:de:0030-drops-153918},
  doi =		{10.4230/LIPIcs.IPEC.2021.8},
  annote =	{Keywords: kernelization, graph editing, split graphs, (sub)linear kernels}
}
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-dev.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-dev.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
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.49
Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes

Authors: Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph G belongs to a given graph class 𝒢. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this paper, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds with a new simple proof technique.
Cite as

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 49:1-49:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.DISC.2021.49,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o},
  title =	{{Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{49:1--49:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.49},
  URN =		{urn:nbn:de:0030-drops-148515},
  doi =		{10.4230/LIPIcs.DISC.2021.49},
  annote =	{Keywords: Local certification, proof-labeling schemes, locally checkable proofs, graph decompositions, minor-free graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.15
Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems

Authors: Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, and Théo Pierron

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from an edge-coloured graph G to an edge-coloured graph H is a vertex-mapping from G to H that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph H, which generalises the classic vertex-colourability property. The question we are interested in is the following: given an edge-coloured graph G, can we perform k graph operations so that the resulting graph admits a homomorphism to H? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs + and -. We denote the corresponding problems (parameterized by k) by Vertex Deletion-H-Colouring, Edge Deletion-H-Colouring and Switching-H-Colouring. These problems generalise the extensively studied H-Colouring problem (where one has to decide if an input graph admits a homomorphism to a fixed target H). For 2-edge-coloured H, it is known that H-Colouring already captures the complexity of all fixed-target Constraint Satisfaction Problems. Our main focus is on the case where H is an edge-coloured graph of order at most 2, a case that is already interesting since it includes standard problems such as Vertex Cover, Odd Cycle Transversal and Edge Bipartization. For such a graph H, we give a PTime/NP-complete complexity dichotomy for all three Vertex Deletion-H-Colouring, Edge Deletion-H-Colouring and Switching-H-Colouring problems. Then, we address their parameterized complexity. We show that all Vertex Deletion-H-Colouring and Edge Deletion-H-Colouring problems for such H are FPT. This is in contrast with the fact that already for some H of order 3, unless PTime = NP, none of the three considered problems is in XP, since 3-Colouring is NP-complete. We show that the situation is different for Switching-H-Colouring: there are three 2-edge-coloured graphs H of order 2 for which Switching-H-Colouring is W[1]-hard, and assuming the ETH, admits no algorithm in time f(k)n^{o(k)} for inputs of size n and for any computable function f. For the other cases, Switching-H-Colouring is FPT.
Cite as

Florent Foucaud, Hervé Hocquard, Dimitri Lajou, Valia Mitsou, and Théo Pierron. Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{foucaud_et_al:LIPIcs.IPEC.2019.15,
  author =	{Foucaud, Florent and Hocquard, Herv\'{e} and Lajou, Dimitri and Mitsou, Valia and Pierron, Th\'{e}o},
  title =	{{Parameterized Complexity of Edge-Coloured and Signed Graph Homomorphism Problems}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.15},
  URN =		{urn:nbn:de:0030-drops-114765},
  doi =		{10.4230/LIPIcs.IPEC.2019.15},
  annote =	{Keywords: Graph homomorphism, Graph modification, Edge-coloured graph, Signed graph}
}
  • Refine by Author
  • 6 Pierron, Théo
  • 5 Bousquet, Nicolas
  • 3 Bathie, Gabriel
  • 2 Bartier, Valentin
  • 2 Feuilloley, Laurent
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 2 Local certification
  • 2 graph decompositions
  • 2 graph editing
  • 2 kernelization
  • 2 locally checkable proofs
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 4 2021
  • 1 2019
  • 1 2022

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 Imprint Privacy Contact