11 Search Results for "M�hlenthaler, Moritz"

Document
DOI: 10.4230/LIPIcs.IPEC.2023.9
Minimum Separator Reconfiguration

Authors: Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden

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

Abstract
We study the problem of reconfiguring one minimum s-t-separator A into another minimum s-t-separator B in some n-vertex graph G containing two non-adjacent vertices s and t. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming A into B. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most 𝓁 jumps can transform A into B is an NP-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size k of the minimum s-t-separators and when parameterized by the number 𝓁 of jumps. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless NP ⊆ coNP/poly. We complete the picture by designing a kernel with 𝒪(𝓁²) vertices and edges for the length 𝓁 of the sequence as a parameter.
Cite as

Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden. Minimum Separator Reconfiguration. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2023.9,
  author =	{C. M. Gomes, Guilherme and Legrand-Duchesne, Cl\'{e}ment and Mahmoud, Reem and Mouawad, Amer E. and Okamoto, Yoshio and F. dos Santos, Vinicius and C. van der Zanden, Tom},
  title =	{{Minimum Separator Reconfiguration}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{9:1--9:12},
  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.9},
  URN =		{urn:nbn:de:0030-drops-194288},
  doi =		{10.4230/LIPIcs.IPEC.2023.9},
  annote =	{Keywords: minimum separators, combinatorial reconfiguration, parameterized complexity, kernelization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.43
Reconfiguration of Digraph Homomorphisms

Authors: Benjamin Lévêque, Moritz Mühlenthaler, and Thomas Suzan

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
For a fixed graph H, the H-Recoloring problem asks whether, given two homomorphisms from a graph G to H, one homomorphism can be transformed into the other by changing the image of a single vertex in each step and maintaining a homomorphism to H throughout. The most general algorithmic result for H-Recoloring so far has been proposed by Wrochna in 2014, who introduced a topological approach to obtain a polynomial-time algorithm for any undirected loopless square-free graph H. We show that the topological approach can be used to recover essentially all previous algorithmic results for H-Recoloring and that it is applicable also in the more general setting of digraph homomorphisms. In particular, we show that H-Recoloring admits a polynomial-time algorithm i) if H is a loopless digraph that does not contain a 4-cycle of algebraic girth 0 and ii) if H is a reflexive digraph that contains no triangle of algebraic girth 1 and no 4-cycle of algebraic girth 0.
Cite as

Benjamin Lévêque, Moritz Mühlenthaler, and Thomas Suzan. Reconfiguration of Digraph Homomorphisms. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 43:1-43:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{leveque_et_al:LIPIcs.STACS.2023.43,
  author =	{L\'{e}v\^{e}que, Benjamin and M\"{u}hlenthaler, Moritz and Suzan, Thomas},
  title =	{{Reconfiguration of Digraph Homomorphisms}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{43:1--43:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.43},
  URN =		{urn:nbn:de:0030-drops-176958},
  doi =		{10.4230/LIPIcs.STACS.2023.43},
  annote =	{Keywords: Digraph Homomorphisms, Combinatorial Reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.5
Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults

Authors: David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
The Edge-disjoint s-t Paths Problem (s-t EDP) is a classical network design problem whose goal is to connect for some k ≥ 1 two given vertices of a graph under the condition that any k-1 edges of the graph may fail. We extend the simple uniform failure model of the s-t EDP as follows: the edge set of the graph is partitioned into vulnerable, and safe edges, and a set of at most k vulnerable edges may fail, while safe edges do not fail. In particular we study the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest s-t Path problem in this non-uniform failure model as well as the Fault-Tolerant Flow (FTF) problem, the counterpart of s-t EDP. We present complexity results alongside exact and approximation algorithms for both problems. We emphasize the vast increase in complexity of the problems compared to s-t EDP.
Cite as

David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{adjiashvili_et_al:LIPIcs.SWAT.2022.5,
  author =	{Adjiashvili, David and Hommelsheim, Felix and M\"{u}hlenthaler, Moritz and Schaudt, Oliver},
  title =	{{Fault-Tolerant Edge-Disjoint s-t Paths - Beyond Uniform Faults}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.5},
  URN =		{urn:nbn:de:0030-drops-161659},
  doi =		{10.4230/LIPIcs.SWAT.2022.5},
  annote =	{Keywords: graph algorithms, network design, fault tolerance, approximation algorithms}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2021.11
Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles

Authors: Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, and Daniel Delling

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
Electric Vehicle routing is often modeled as a Shortest Feasible Path Problem (SFPP), which minimizes total travel time while maintaining a non-zero State of Charge (SoC) along the route. However, the problem assumes perfect information about energy consumption and charging stations, which are difficult to even estimate in practice. Further, drivers might have varying risk tolerances for different trips. To overcome these limitations, we propose two generalizations to the SFPP; they compute the shortest feasible path for any initial SoC and, respectively, for every possible minimum SoC threshold. We present algorithmic solutions for each problem, and provide two constructs: Starting Charge Maps and Buffer Maps, which represent the tradeoffs between robustness of feasible routes and their travel times. The two constructs are useful in many ways, including presenting alternate routes or providing charging prompts to users. We evaluate the performance of our algorithms on realistic input instances.
Cite as

Payas Rajan, Moritz Baum, Michael Wegner, Tobias Zündorf, Christian J. West, Dennis Schieferdecker, and Daniel Delling. Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rajan_et_al:OASIcs.ATMOS.2021.11,
  author =	{Rajan, Payas and Baum, Moritz and Wegner, Michael and Z\"{u}ndorf, Tobias and West, Christian J. and Schieferdecker, Dennis and Delling, Daniel},
  title =	{{Robustness Generalizations of the Shortest Feasible Path Problem for Electric Vehicles}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{11:1--11:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.11},
  URN =		{urn:nbn:de:0030-drops-148807},
  doi =		{10.4230/OASIcs.ATMOS.2021.11},
  annote =	{Keywords: Electric Vehicles, Route Planning}
}
Document
DOI: 10.4230/OASIcs.iPMVM.2020.15
Physics Simulation of Material Flows: Effects on the Performance of a Production System

Authors: Moritz Glatt, Bahram Ravani, and Jan C. Aurich

Published in: OASIcs, Volume 89, 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)

Abstract
In cyber-physical production systems, material flows show complexity due to varying physical aspects of transported work pieces and autonomously selected transport routes. As a result, physically induced disturbances that may lead to delays or damages are hard to predict. The on-line usage of a physics engine offers potential to derive material flow parameters that enable safe transports with optimized accelerations. Previous work showed the feasibility of this approach and potential operational benefits through faster material flows. In consequence, the scope of this paper is to apply discrete-event simulation to investigate whether physics simulation of material flows leads to positive impacts on production system performance indicators such as throughput times and capacity utilization. The results indicate that increased velocity and acceleration of material flows can positively influence these indicators. In consequence, applying physics simulation to ensure safe transports with such high velocities and accelerations can improve the overall performance of a production system.
Cite as

Moritz Glatt, Bahram Ravani, and Jan C. Aurich. Physics Simulation of Material Flows: Effects on the Performance of a Production System. In 2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020). Open Access Series in Informatics (OASIcs), Volume 89, pp. 15:1-15:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{glatt_et_al:OASIcs.iPMVM.2020.15,
  author =	{Glatt, Moritz and Ravani, Bahram and Aurich, Jan C.},
  title =	{{Physics Simulation of Material Flows: Effects on the Performance of a Production System}},
  booktitle =	{2nd International Conference of the DFG International Research Training Group 2057 – Physical Modeling for Virtual Manufacturing (iPMVM 2020)},
  pages =	{15:1--15:26},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-183-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{89},
  editor =	{Garth, Christoph and Aurich, Jan C. and Linke, Barbara and M\"{u}ller, Ralf and Ravani, Bahram and Weber, Gunther H. and Kirsch, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.iPMVM.2020.15},
  URN =		{urn:nbn:de:0030-drops-137640},
  doi =		{10.4230/OASIcs.iPMVM.2020.15},
  annote =	{Keywords: Physics simulation, discrete-event simulation, cyber-physical production systems}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.15
Fixed-Parameter Algorithms for Graph Constraint Logic

Authors: Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki

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

Abstract
Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures PSPACE and has been a useful tool for proving algorithmic hardness of many puzzles, games, and reconfiguration problems. In particular, its usefulness stems from the fact that it remains PSPACE-complete even under severe restrictions of the weights (e.g., only edge-weights one and two are needed) and the structure of the constraint graph (e.g., planar AND/OR graphs of bounded bandwidth). While such restrictions on the structure of constraint graphs do not seem to limit the expressiveness of NCL, the building blocks of the constraint graphs cannot be limited without losing expressiveness: We consider as parameters the number of weight-one edges and the number of weight-two edges of a constraint graph, as well as the number of AND or OR vertices of an AND/OR constraint graph. We show that NCL is fixed-parameter tractable (FPT) for any of these parameters. In particular, for NCL parameterized by the number of weight-one edges or the number of AND vertices, we obtain a linear kernel. It follows that, in a sense, NCL as introduced by Hearn and Demaine is defined in the most economical way for the purpose of capturing PSPACE.
Cite as

Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki. Fixed-Parameter Algorithms for Graph Constraint Logic. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hatanaka_et_al:LIPIcs.IPEC.2020.15,
  author =	{Hatanaka, Tatsuhiko and Hommelsheim, Felix and Ito, Takehiro and Kobayashi, Yusuke and M\"{u}hlenthaler, Moritz and Suzuki, Akira},
  title =	{{Fixed-Parameter Algorithms for Graph Constraint Logic}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{15:1--15:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.15},
  URN =		{urn:nbn:de:0030-drops-133182},
  doi =		{10.4230/LIPIcs.IPEC.2020.15},
  annote =	{Keywords: Combinatorial Reconfiguration, Nondeterministic Constraint Logic, Fixed Parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.35
Shortest Reconfiguration of Colorings Under Kempe Changes

Authors: Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
A k-coloring of a graph maps each vertex of the graph to a color in {1, 2, …, k}, such that no two adjacent vertices receive the same color. Given a k-coloring of a graph, a Kempe change produces a new k-coloring by swapping the colors in a bicolored connected component. We investigate the complexity of finding the smallest number of Kempe changes needed to transform a given k-coloring into another given k-coloring. We show that this problem admits a polynomial-time dynamic programming algorithm on path graphs, which turns out to be highly non-trivial. Furthermore, the problem is NP-hard even on star graphs and we show that on such graphs it admits a constant-factor approximation algorithm and is fixed-parameter tractable when parameterized by the number k of colors. The hardness result as well as the algorithmic results are based on the notion of a canonical transformation.
Cite as

Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa. Shortest Reconfiguration of Colorings Under Kempe Changes. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.STACS.2020.35,
  author =	{Bonamy, Marthe and Heinrich, Marc and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and M\"{u}hlenthaler, Moritz and Suzuki, Akira and Wasa, Kunihiro},
  title =	{{Shortest Reconfiguration of Colorings Under Kempe Changes}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.35},
  URN =		{urn:nbn:de:0030-drops-118961},
  doi =		{10.4230/LIPIcs.STACS.2020.35},
  annote =	{Keywords: Combinatorial Reconfiguration, Graph Algorithms, Graph Coloring, Kempe Equivalence}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.80
The Perfect Matching Reconfiguration Problem

Authors: Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.
Cite as

Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa. The Perfect Matching Reconfiguration Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.MFCS.2019.80,
  author =	{Bonamy, Marthe and Bousquet, Nicolas and Heinrich, Marc and Ito, Takehiro and Kobayashi, Yusuke and Mary, Arnaud and M\"{u}hlenthaler, Moritz and Wasa, Kunihiro},
  title =	{{The Perfect Matching Reconfiguration Problem}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.80},
  URN =		{urn:nbn:de:0030-drops-110248},
  doi =		{10.4230/LIPIcs.MFCS.2019.80},
  annote =	{Keywords: Combinatorial Reconfiguration, Graph Algorithms, Perfect Matching}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.38
How to Secure Matchings Against Edge Failures

Authors: Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
Suppose we are given a bipartite graph that admits a perfect matching and an adversary may delete any edge from the graph with the intention of destroying all perfect matchings. We consider the task of adding a minimum cost edge-set to the graph, such that the adversary never wins. We show that this problem is equivalent to covering a digraph with non-trivial strongly connected components at minimal cost. We provide efficient exact and approximation algorithms for this task. In particular, for the unit-cost problem, we give a log_2 n-factor approximation algorithm and a polynomial-time algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter algorithm for the problem parameterized by the treewidth of the input graph. For general non-negative weights we give tight upper and lower approximation bounds relative to the Directed Steiner Forest problem. Additionally we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. To obtain our results, we exploit a close relation to the classical Strong Connectivity Augmentation problem as well as directed Steiner problems.
Cite as

Felix Hommelsheim, Moritz Mühlenthaler, and Oliver Schaudt. How to Secure Matchings Against Edge Failures. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hommelsheim_et_al:LIPIcs.STACS.2019.38,
  author =	{Hommelsheim, Felix and M\"{u}hlenthaler, Moritz and Schaudt, Oliver},
  title =	{{How to Secure Matchings Against Edge Failures}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.38},
  URN =		{urn:nbn:de:0030-drops-102772},
  doi =		{10.4230/LIPIcs.STACS.2019.38},
  annote =	{Keywords: Matchings, Robustness, Connectivity Augmentation, Graph Algorithms, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.56
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

Authors: Frank Kammer, Dieter Kratsch, and Moritz Laudahn

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We present space-efficient algorithms for computing cut vertices in a given graph with n vertices and m edges in linear time using O(n+min{m,n log log n}) bits. With the same time and using O(n+m) bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in O(n log log n) time using O(n) bits.
Cite as

Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.MFCS.2016.56,
  author =	{Kammer, Frank and Kratsch, Dieter and Laudahn, Moritz},
  title =	{{Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.56},
  URN =		{urn:nbn:de:0030-drops-64683},
  doi =		{10.4230/LIPIcs.MFCS.2016.56},
  annote =	{Keywords: graph algorithms, space efficiency, cut vertices, maximal outerplanar graphs}
}
Document
DOI: 10.4230/DagSemProc.07281.3
Approximating Solution Structure

Authors: Iris van Rooij, Matthew Hamilton, Moritz Müller, and Todd Wareham

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
hen it is hard to compute an optimal solution $y in optsol(x)$ to an instance $x$ of a problem, one may be willing to settle for an efficient algorithm $A$ that computes an approximate solution $A(x)$. The most popular type of approximation algorithm in Computer Science (and indeed many other applications) computes solutions whose value is within some multiplicative factor of the optimal solution value, {em e.g.}, $max(frac{val(A(x))}{optval(x)}, frac{optval(x)}{val(A(x))}) leq h(|x|)$ for some function $h()$. However, an algorithm might also produce a solution whose structure is ``close'' to the structure of an optimal solution relative to a specified solution-distance function $d$, {em i.e.}, $d(A(x), y) leq h(|x|)$ for some $y in optsol(x)$. Such structure-approximation algorithms have applications within Cognitive Science and other areas. Though there is an extensive literature dating back over 30 years on value-approximation, there is to our knowledge no work on general techniques for assessing the structure-(in)approximability of a given problem. In this talk, we describe a framework for investigating the polynomial-time and fixed-parameter structure-(in)approximability of combinatorial optimization problems relative to metric solution-distance functions, {em e.g.}, Hamming distance. We motivate this framework by (1) describing a particular application within Cognitive Science and (2) showing that value-approximability does not necessarily imply structure-approximability (and vice versa). This framework includes definitions of several types of structure approximation algorithms analogous to those studied in value-approximation, as well as structure-approximation problem classes and a structure-approximability-preserving reducibility. We describe a set of techniques for proving the degree of structure-(in)approximability of a given problem, and summarize all known results derived using these techniques. We also list 11 open questions summarizing particularly promising directions for future research within this framework. vspace*{0.15in} oindent (co-presented with Todd Wareham) vspace*{0.15in} jointwork{Hamilton, Matthew; M"{u}ller, Moritz; van Rooij, Iris; Wareham, Todd}
Cite as

Iris van Rooij, Matthew Hamilton, Moritz Müller, and Todd Wareham. Approximating Solution Structure. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{vanrooij_et_al:DagSemProc.07281.3,
  author =	{van Rooij, Iris and Hamilton, Matthew and M\"{u}ller, Moritz and Wareham, Todd},
  title =	{{Approximating Solution Structure}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.3},
  URN =		{urn:nbn:de:0030-drops-12345},
  doi =		{10.4230/DagSemProc.07281.3},
  annote =	{Keywords: Approximation Algorithms, Solution Structure}
}
  • Refine by Author
  • 6 Mühlenthaler, Moritz
  • 3 Hommelsheim, Felix
  • 3 Ito, Takehiro
  • 3 Kobayashi, Yusuke
  • 2 Bonamy, Marthe
  • Show More...

  • Refine by Classification
  • 5 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Approximation algorithms
  • 2 Theory of computation → Fixed parameter tractability
  • 1 Computing methodologies → Modeling and simulation
  • 1 Hardware → Robustness
  • Show More...

  • Refine by Keyword
  • 4 Combinatorial Reconfiguration
  • 3 Graph Algorithms
  • 2 graph algorithms
  • 1 Approximation Algorithms
  • 1 Connectivity Augmentation
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 2 2019
  • 2 2020
  • 2 2021
  • 2 2023
  • 1 2007
  • Show More...

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