Search Results

Documents authored by Bellitto, Thomas

Document
DOI: 10.4230/LIPIcs.SAND.2023.13
Restless Exploration of Periodic Temporal Graphs

Authors: Thomas Bellitto, Cyril Conchon-Kerjan, and Bruno Escoffier

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
A temporal graph is a sequence of graphs, indexed by discrete time steps, with a fixed vertex set but with an edge set that is able to change over time. In the temporal graph exploration problem, an agent wants to visit all the vertices of a given temporal graph. In the classical model, at each time step the agent can either stay where they are, or move along one edge. In this work we add a constraint called restlessness that forces the agent to move along one edge at each time step. We mainly focus on (infinite) periodical temporal graphs. We show that if the period is 2 one can decide in polynomial time whether exploring the whole graph is possible or not, while this problem turns out to be NP-hard for any period p ≥ 3. We also show some time bounds on the explorations of such graphs when the exploration is possible.
Cite as

Thomas Bellitto, Cyril Conchon-Kerjan, and Bruno Escoffier. Restless Exploration of Periodic Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.SAND.2023.13,
  author =	{Bellitto, Thomas and Conchon-Kerjan, Cyril and Escoffier, Bruno},
  title =	{{Restless Exploration of Periodic Temporal Graphs}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.13},
  URN =		{urn:nbn:de:0030-drops-179497},
  doi =		{10.4230/LIPIcs.SAND.2023.13},
  annote =	{Keywords: Temporal graphs, Graph exploration, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.21
Close Relatives (Of Feedback Vertex Set), Revisited

Authors: Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk

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

Abstract
At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon (Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth, IPEC 2020, LIPIcs vol. 180, pp. 3:1-3:17) showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a 2^{o(k log k)} ⋅ n^{𝒪(1)}-time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3^{k} ⋅ k^{𝒪(1)} ⋅ n-time algorithm for FVS using the Cut&Count technique. During their live talk at IPEC 2020, Bergougnoux et al. posed a number of open questions, which we answer in this work. - Subset Even Cycle Transversal, Subset Odd Cycle Transversal, Subset Feedback Vertex Set can be solved in time 2^{𝒪(k log k)} ⋅ n in graphs of treewidth at most k. This matches a lower bound for Even Cycle Transversal of Bergougnoux et al. and improves the polynomial factor in some of their upper bounds. - Subset Feedback Vertex Set and Node Multiway Cut can be solved in time 2^{𝒪(k log k)} ⋅ n, if the input graph is given as a cliquewidth expression of size n and width k. - Odd Cycle Transversal can be solved in time 4^k ⋅ k^{𝒪(1)} ⋅ n if the input graph is given as a cliquewidth expression of size n and width k. Furthermore, the existence of a constant ε > 0 and an algorithm performing this task in time (4-ε)^k ⋅ n^{𝒪(1)} would contradict the Strong Exponential Time Hypothesis. A common theme of the first two algorithmic results is to represent connectivity properties of the current graph in a state of a dynamic programming algorithm as an auxiliary forest with 𝒪(k) nodes. This results in a 2^{𝒪(k log k)} bound on the number of states for one node of the tree decomposition or cliquewidth expression and allows to compare two states in k^{𝒪(1)} time, resulting in linear time dependency on the size of the graph or the input cliquewidth expression.
Cite as

Hugo Jacob, Thomas Bellitto, Oscar Defrain, and Marcin Pilipczuk. Close Relatives (Of Feedback Vertex Set), Revisited. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jacob_et_al:LIPIcs.IPEC.2021.21,
  author =	{Jacob, Hugo and Bellitto, Thomas and Defrain, Oscar and Pilipczuk, Marcin},
  title =	{{Close Relatives (Of Feedback Vertex Set), Revisited}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{21:1--21:15},
  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.21},
  URN =		{urn:nbn:de:0030-drops-154049},
  doi =		{10.4230/LIPIcs.IPEC.2021.21},
  annote =	{Keywords: feedback vertex set, treewidth, cliquewidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.59
The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs

Authors: Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge

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

Abstract
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. We initiate the study of fundamental connectivity problems from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth of finding a properly colored Hamiltonian cycle in an edge-colored graph; properly colored walks in edge-colored graphs is one of the most studied special cases of compatible walks in forbidden-transition graphs.
Cite as

Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge. The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.ISAAC.2020.59,
  author =	{Bellitto, Thomas and Li, Shaohua and Okrasa, Karolina and Pilipczuk, Marcin and Sorge, Manuel},
  title =	{{The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{59:1--59:15},
  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.59},
  URN =		{urn:nbn:de:0030-drops-134036},
  doi =		{10.4230/LIPIcs.ISAAC.2020.59},
  annote =	{Keywords: Graph algorithms, fixed-parameter tractability, parameterized complexity}
}
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