Search Results

Documents authored by Hatanaka, Tatsuhiko

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.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.MFCS.2019.79
Reconfiguration of Minimum Steiner Trees via Vertex Exchanges

Authors: Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou

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

Abstract
In this paper, we study the problem of deciding if there is a transformation between two given minimum Steiner trees of an unweighted graph such that each transformation step respects a prescribed reconfiguration rule and results in another minimum Steiner tree of the graph. We consider two reconfiguration rules, both of which exchange a single vertex at a time, and generalize the known reconfiguration problem for shortest paths in an unweighted graph. This generalization implies that our problems under both reconfiguration rules are PSPACE-complete for bipartite graphs. We thus study the problems with respect to graph classes, and give some boundaries between the polynomial-time solvable and PSPACE-complete cases.
Cite as

Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. Reconfiguration of Minimum Steiner Trees via Vertex Exchanges. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 79:1-79:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{mizuta_et_al:LIPIcs.MFCS.2019.79,
  author =	{Mizuta, Haruka and Hatanaka, Tatsuhiko and Ito, Takehiro and Zhou, Xiao},
  title =	{{Reconfiguration of Minimum Steiner Trees via Vertex Exchanges}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{79:1--79:11},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.79},
  URN =		{urn:nbn:de:0030-drops-110234},
  doi =		{10.4230/LIPIcs.MFCS.2019.79},
  annote =	{Keywords: Combinatorial reconfiguration, Graph algorithms, Steiner tree}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.51
Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

Authors: Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
Let G be a graph such that each vertex has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. For two given list colorings of G, we study the problem of transforming one into the other by changing only one vertex color assignment at a time, while at all times maintaining a list coloring. This problem is known to be PSPACE-complete even for bounded bandwidth graphs and a fixed constant k. In this paper, we study the fixed-parameter tractability of the problem when parameterized by several graph parameters. We first give a fixed-parameter algorithm for the problem when parameterized by k and the modular-width of an input graph. We next give a fixed-parameter algorithm for the shortest variant which computes the length of a shortest transformation when parameterized by k and the size of a minimum vertex cover of an input graph. As corollaries, we show that the problem for cographs and the shortest variant for split graphs are fixed-parameter tractable even when only k is taken as a parameter. On the other hand, we prove that the problem is W[1]-hard when parameterized only by the size of a minimum vertex cover of an input graph.
Cite as

Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hatanaka_et_al:LIPIcs.MFCS.2017.51,
  author =	{Hatanaka, Tatsuhiko and Ito, Takehiro and Zhou, Xiao},
  title =	{{Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{51:1--51:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.51},
  URN =		{urn:nbn:de:0030-drops-81060},
  doi =		{10.4230/LIPIcs.MFCS.2017.51},
  annote =	{Keywords: combinatorial reconfiguration, fixed-parameter tractability, graph algorithm, list coloring, W\lbrack1\rbrack-hardness}
}
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