Author name cluster

Moritz Mühlenthaler

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

TCS Journal 2023 Journal Article

Feedback vertex set reconfiguration in planar graphs

Nicolas Bousquet
Felix Hommelsheim
Yusuke Kobayashi
Moritz Mühlenthaler
Akira Suzuki

We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one is obtained by exchanging a single vertex. We give a classification of the complexity of this question for planar graphs in terms of the maximum degree. We show that for planar graphs of maximum degree at most three the problem is tractable because there always exists a transformation, while it is PSPACE-complete when the maximum degree is at most four. The positive side of the classification extends to K 3, 3 -minor-free graphs of maximum degree three. We then consider the Matroid Parity problem, which generalizes feedback vertex sets in graphs of maximum degree three as well as matchings and spanning trees in general graphs. Generalizing known results for the latter two we show that there always exists a transformation between any two non-maximum independent parity sets.

Details DOI

TCS Journal 2023 Journal Article

Fixed-parameter algorithms for graph constraint logic

Tatsuhiko Hatanaka
Felix Hommelsheim
Takehiro Ito
Yusuke Kobayashi
Moritz Mühlenthaler
Akira Suzuki

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.

Details DOI

TCS Journal 2020 Journal Article

Diameter of colorings under Kempe changes

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

Given a k-coloring of a graph G, a Kempe-change for two colors a and b produces another k-coloring of G, as follows: first choose a connected component in the subgraph of G induced by the two color classes of a and b, and then swap the colors a and b in the component. Two k-colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two k-colorings of a graph G, Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph G and a positive integer k, Kempe Connectivity asks whether any two k-colorings of G are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is PSPACE -complete for any fixed k ≥ 3, and that it remains PSPACE -complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two k-colorings are Kempe-equivalent.

Details DOI

MFCS Conference 2019 Conference Paper

The Perfect Matching Reconfiguration Problem

Marthe Bonamy
Nicolas Bousquet 0001
Marc Heinrich
Takehiro Ito
Yusuke Kobayashi 0001
Arnaud Mary
Moritz Mühlenthaler
Kunihiro Wasa

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.

Details