2 Search Results for "Wiederrecht, Sebastian"

Document
DOI: 10.4230/LIPIcs.IPEC.2023.26
Dynamic Programming on Bipartite Tree Decompositions

Authors: Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Theor. Comput. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that K_t-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are FPT parameterized by bipartite treewidth. We also provide the following complexity dichotomy when H is a 2-connected graph, for each of the H-Subgraph-Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is para-NP-complete parameterized by bipartite treewidth while, if H is non-bipartite, then the problem is solvable in XP-time. Beyond bipartite treewidth, we define 1-ℋ-treewidth by replacing the bipartite graph class by any graph class ℋ. Most of the technology developed here also works for this more general parameter.
Cite as

Lars Jaffke, Laure Morelle, Ignasi Sau, and Dimitrios M. Thilikos. Dynamic Programming on Bipartite Tree Decompositions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jaffke_et_al:LIPIcs.IPEC.2023.26,
  author =	{Jaffke, Lars and Morelle, Laure and Sau, Ignasi and Thilikos, Dimitrios M.},
  title =	{{Dynamic Programming on Bipartite Tree Decompositions}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.26},
  URN =		{urn:nbn:de:0030-drops-194455},
  doi =		{10.4230/LIPIcs.IPEC.2023.26},
  annote =	{Keywords: tree decomposition, bipartite graphs, dynamic programming, odd-minors, packing, maximum cut, vertex cover, independent set, odd cycle transversal}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.143
Congestion-Free Rerouting of Flows on DAGs

Authors: Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Changing a given configuration in a graph into another one is known as a reconfiguration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute k unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for k=2 flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general k, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.
Cite as

Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht. Congestion-Free Rerouting of Flows on DAGs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 143:1-143:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{akhoondianamiri_et_al:LIPIcs.ICALP.2018.143,
  author =	{Akhoondian Amiri, Saeed and Dudycz, Szymon and Schmid, Stefan and Wiederrecht, Sebastian},
  title =	{{Congestion-Free Rerouting of Flows on DAGs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{143:1--143:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.143},
  URN =		{urn:nbn:de:0030-drops-91471},
  doi =		{10.4230/LIPIcs.ICALP.2018.143},
  annote =	{Keywords: Unsplittable Flows, Reconfiguration, DAGs, FPT, NP-Hardness}
}
  • Refine by Author
  • 1 Akhoondian Amiri, Saeed
  • 1 Dudycz, Szymon
  • 1 Jaffke, Lars
  • 1 Morelle, Laure
  • 1 Sau, Ignasi
  • Show More...

  • Refine by Classification
  • 1 Networks → Network algorithms
  • 1 Theory of computation → Network flows
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 DAGs
  • 1 FPT
  • 1 NP-Hardness
  • 1 Reconfiguration
  • 1 Unsplittable Flows
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2023

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