Search Results

Documents authored by Focke, Jacob

Document
DOI: 10.4230/LIPIcs.SoCG.2024.57
Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern

Authors: Jacob Focke, Florian Hörsch, Shaohua Li, and Dániel Marx

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The Multicut problem asks for a minimum cut separating certain pairs of vertices: formally, given a graph G and a demand graph H on a set T ⊆ V(G) of terminals, the task is to find a minimum-weight set C of edges of G such that whenever two vertices of T are adjacent in H, they are in different components of G⧵ C. Colin de Verdière [Algorithmica, 2017] showed that Multicut with t terminals on a graph G of genus g can be solved in time f(t,g) n^O(√{g²+gt+t}). Cohen-Addad et al. [JACM, 2021] proved a matching lower bound showing that the exponent of n is essentially best possible (for every fixed value of t and g), even in the special case of Multiway Cut, where the demand graph H is a complete graph. However, this lower bound tells us nothing about other special cases of Multicut such as Group 3-Terminal Cut (where three groups of terminals need to be separated from each other). We show that if the demand pattern is, in some sense, close to being a complete bipartite graph, then Multicut can be solved faster than f(t,g) n^{O(√{g²+gt+t})}, and furthermore this is the only property that allows such an improvement. Formally, for a class ℋ of graphs, Multicut(ℋ) is the special case where the demand graph H is in ℋ. For every fixed class ℋ (satisfying some mild closure property), fixed g, and fixed t, our main result gives tight upper and lower bounds on the exponent of n in algorithms solving Multicut(ℋ). In addition, we investigate a similar setting where, instead of parameterizing by the genus g of G, we parameterize by the minimum number k of edges of G that need to be deleted to obtain a planar graph. Interestingly, in this setting it makes a significant difference whether the graph G is weighted or unweighted: further nontrivial algorithmic techniques give substantial improvements in the unweighted case.
Cite as

Jacob Focke, Florian Hörsch, Shaohua Li, and Dániel Marx. Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{focke_et_al:LIPIcs.SoCG.2024.57,
  author =	{Focke, Jacob and H\"{o}rsch, Florian and Li, Shaohua and Marx, D\'{a}niel},
  title =	{{Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.57},
  URN =		{urn:nbn:de:0030-drops-200021},
  doi =		{10.4230/LIPIcs.SoCG.2024.57},
  annote =	{Keywords: MultiCut, Multiway Cut, Parameterized Complexity, Tight Bounds, Embedded Graph, Planar Graph, Genus, Surface, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.22
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments

Authors: Jacob Focke, Nicole Megow, and Julie Meißner

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
We consider the minimum spanning tree (MST) problem in an uncertainty model where uncertain edge weights can be explored at extra cost. The task is to find an MST by querying a minimum number of edges for their exact weight. This problem has received quite some attention from the algorithms theory community. In this paper, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved completely by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library.
Cite as

Jacob Focke, Nicole Megow, and Julie Meißner. Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{focke_et_al:LIPIcs.SEA.2017.22,
  author =	{Focke, Jacob and Megow, Nicole and Mei{\ss}ner, Julie},
  title =	{{Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.22},
  URN =		{urn:nbn:de:0030-drops-76202},
  doi =		{10.4230/LIPIcs.SEA.2017.22},
  annote =	{Keywords: MST, explorable uncertainty, competitive ratio, experimental algorithms}
}
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