4 Search Results for "Swennenhuis, Céline M. F."

Document
DOI: 10.4230/LIPIcs.ESA.2024.76
Steiner Tree Parameterized by Multiway Cut and Even Less

Authors: Bart M.P. Jansen and Céline M.F. Swennenhuis

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In the Steiner Tree problem we are given an undirected edge-weighted graph as input, along with a set K of vertices called terminals. The task is to output a minimum-weight connected subgraph that spans all the terminals. The famous Dreyfus-Wagner algorithm running in 3^{|K|}poly(n) time shows that the problem is fixed-parameter tractable parameterized by the number of terminals. We present fixed-parameter tractable algorithms for Steiner Tree using structurally smaller parameterizations. Our first result concerns the parameterization by a multiway cut S of the terminals, which is a vertex set S (possibly containing terminals) such that each connected component of G-S contains at most one terminal. We show that Steiner Tree can be solved in 2^{𝒪(|S|log|S|)}poly(n) time and polynomial space, where S is a minimum multiway cut for K. The algorithm is based on the insight that, after guessing how an optimal Steiner tree interacts with a multiway cut S, computing a minimum-cost solution of this type can be formulated as minimum-cost bipartite matching. Our second result concerns a new hybrid parameterization called K-free treewidth that simultaneously refines the number of terminals |K| and the treewidth of the input graph. By utilizing recent work on ℋ-Treewidth in order to find a corresponding decomposition of the graph, we give an algorithm that solves Steiner Tree in time 2^{𝒪(k)} poly(n), where k denotes the K-free treewidth of the input graph. To obtain this running time, we show how the rank-based approach for solving Steiner Tree parameterized by treewidth can be extended to work in the setting of K-free treewidth, by exploiting existing algorithms parameterized by |K| to compute the table entries of leaf bags of a tree K-free decomposition.
Cite as

Bart M.P. Jansen and Céline M.F. Swennenhuis. Steiner Tree Parameterized by Multiway Cut and Even Less. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 76:1-76:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ESA.2024.76,
  author =	{Jansen, Bart M.P. and Swennenhuis, C\'{e}line M.F.},
  title =	{{Steiner Tree Parameterized by Multiway Cut and Even Less}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{76:1--76:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.76},
  URN =		{urn:nbn:de:0030-drops-211471},
  doi =		{10.4230/LIPIcs.ESA.2024.76},
  annote =	{Keywords: fixed-parameter tractability, Steiner Tree, structural parameterization, H-treewidth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.50
Isolation Schemes for Problems on Decomposable Graphs

Authors: Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis, and Karol Węgrzycki

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique solution, provided a solution exists at all. Since its introduction, much effort has been dedicated towards derandomization of the Isolation Lemma for specific classes of problems. So far, the focus was mainly on problems solvable in polynomial time. In this paper, we study a setting that is more typical for NP-complete problems, and obtain partial derandomizations in the form of significantly decreasing the number of required random bits. In particular, motivated by the advances in parameterized algorithms, we focus on problems on decomposable graphs. For example, for the problem of detecting a Hamiltonian cycle, we build upon the rank-based approach from [Bodlaender et al., Inf. Comput.'15] and design isolation schemes that use - 𝒪(tlog n + log²{n}) random bits on graphs of treewidth at most t; - 𝒪(√n) random bits on planar or H-minor free graphs; and - 𝒪(n)-random bits on general graphs. In all these schemes, the weights are bounded exponentially in the number of random bits used. As a corollary, for every fixed H we obtain an algorithm for detecting a Hamiltonian cycle in an H-minor-free graph that runs in deterministic time 2^{𝒪(√n)} and uses polynomial space; this is the first algorithm to achieve such complexity guarantees. For problems of more local nature, such as finding an independent set of maximum size, we obtain isolation schemes on graphs of treedepth at most d that use 𝒪(d) random bits and assign polynomially-bounded weights. We also complement our findings with several unconditional and conditional lower bounds, which show that many of the results cannot be significantly improved.
Cite as

Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis, and Karol Węgrzycki. Isolation Schemes for Problems on Decomposable Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nederlof_et_al:LIPIcs.STACS.2022.50,
  author =	{Nederlof, Jesper and Pilipczuk, Micha{\l} and Swennenhuis, C\'{e}line M. F. and W\k{e}grzycki, Karol},
  title =	{{Isolation Schemes for Problems on Decomposable Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.50},
  URN =		{urn:nbn:de:0030-drops-158601},
  doi =		{10.4230/LIPIcs.STACS.2022.50},
  annote =	{Keywords: Isolation Lemma, Derandomization, Hamiltonian Cycle, Exact Algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.9
Parameterized Complexities of Dominating and Independent Set Reconfiguration

Authors: Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis

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

Abstract
We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show that both problems are XL-complete when there is no limit on the number of moves and XNL-complete when a maximum length 𝓁 for the sequence is given in binary in the input. The problems are known to be XNLP-complete when 𝓁 is given in unary instead, and W[1]- and W[2]-hard respectively when 𝓁 is also a parameter. We complete the picture by showing membership in those classes. Moreover, we show that for all the variants that we consider, token sliding and token jumping are equivalent under pl-reductions. We introduce partitioned variants of token jumping and token sliding, and give pl-reductions between the four variants that have precise control over the number of tokens and the length of the reconfiguration sequence.
Cite as

Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis. Parameterized Complexities of Dominating and Independent Set Reconfiguration. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2021.9,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Swennenhuis, C\'{e}line M. F.},
  title =	{{Parameterized Complexities of Dominating and Independent Set Reconfiguration}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{9:1--9:16},
  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.9},
  URN =		{urn:nbn:de:0030-drops-153920},
  doi =		{10.4230/LIPIcs.IPEC.2021.9},
  annote =	{Keywords: Parameterized complexity, independent set reconfiguration, dominating set reconfiguration, W-hierarchy, XL, XNL, XNLP}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.25
On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan

Authors: Jesper Nederlof and Céline M. F. Swennenhuis

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
We study a natural variant of scheduling that we call partial scheduling: In this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f(k)n^𝒪(1) or n^𝒪(f(k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in 𝖯, NP-complete and fixed-parameter tractable by k, or 𝖶[1]-hard parameterized by k. Second, for many interesting cases we further investigate the run time on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an 𝒪(8^k k(|V|+|E|)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V,E) is the graph with precedence constraints.
Cite as

Jesper Nederlof and Céline M. F. Swennenhuis. On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nederlof_et_al:LIPIcs.IPEC.2020.25,
  author =	{Nederlof, Jesper and Swennenhuis, C\'{e}line M. F.},
  title =	{{On the Fine-Grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.25},
  URN =		{urn:nbn:de:0030-drops-133287},
  doi =		{10.4230/LIPIcs.IPEC.2020.25},
  annote =	{Keywords: Fixed-Parameter Tractability, Scheduling, Precedence Constraints}
}
  • Refine by Author
  • 3 Swennenhuis, Céline M. F.
  • 2 Nederlof, Jesper
  • 1 Bodlaender, Hans L.
  • 1 Groenland, Carla
  • 1 Jansen, Bart M.P.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Fixed parameter tractability
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Derandomization
  • 1 Exact Algorithms
  • 1 Fixed-Parameter Tractability
  • 1 H-treewidth
  • 1 Hamiltonian Cycle
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021
  • 1 2022
  • 1 2024

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