Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

We consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized (1 - 1/e - ε)-approximation algorithm that requires Õ_{ε}(√r n) independence oracle and value oracle queries, where n is the number of elements in the matroid and r ≤ n is the rank of the matroid. This improves upon the previously best algorithm by Buchbinder-Feldman-Schwartz [Mathematics of Operations Research 2017] that requires Õ_{ε}(r² + √rn) queries.
Our algorithm is based on continuous relaxation, as with other submodular maximization algorithms in the literature. To achieve subquadratic query complexity, we develop a new rounding algorithm, which is our main technical contribution. The rounding algorithm takes as input a point represented as a convex combination of t bases of a matroid and rounds it to an integral solution. Our rounding algorithm requires Õ(r^{3/2} t) independence oracle queries, while the previously best rounding algorithm by Chekuri-Vondrák-Zenklusen [FOCS 2010] requires O(r² t) independence oracle queries. A key idea in our rounding algorithm is to use a directed cycle of arbitrary length in an auxiliary graph, while the algorithm of Chekuri-Vondrák-Zenklusen focused on directed cycles of length two.

Yusuke Kobayashi and Tatsuya Terao. Subquadratic Submodular Maximization with a General Matroid Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ICALP.2024.100, author = {Kobayashi, Yusuke and Terao, Tatsuya}, title = {{Subquadratic Submodular Maximization with a General Matroid Constraint}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {100:1--100:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.100}, URN = {urn:nbn:de:0030-drops-202437}, doi = {10.4230/LIPIcs.ICALP.2024.100}, annote = {Keywords: submodular maximization, matroid constraint, approximation algorithm, rounding algorithm, query complexity} }

Document

**Published in:** LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

An arborescence in a digraph is an acyclic arc subset in which every vertex except a root has exactly one incoming arc. In this paper, we show the reconfigurability of the union of k arborescences for fixed k in the following sense: for any pair of arc subsets that can be partitioned into k arborescences, one can be transformed into the other by exchanging arcs one by one so that every intermediate arc subset can also be partitioned into k arborescences. This generalizes the result by Ito et al. (2023), who showed the case with k = 1. Since the union of k arborescences can be represented as a common matroid basis of two matroids, our result gives a new non-trivial example of matroid pairs for which two common bases are always reconfigurable to each other.

Yusuke Kobayashi, Ryoga Mahara, and Tamás Schwarcz. Reconfiguration of the Union of Arborescences. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2023.48, author = {Kobayashi, Yusuke and Mahara, Ryoga and Schwarcz, Tam\'{a}s}, title = {{Reconfiguration of the Union of Arborescences}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {48:1--48:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.48}, URN = {urn:nbn:de:0030-drops-193502}, doi = {10.4230/LIPIcs.ISAAC.2023.48}, annote = {Keywords: Arborescence packing, common matroid basis, combinatorial reconfiguration} }

Document

**Published in:** LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

The 2-Edge-Connected Spanning Subgraph problem (2-ECSS) is one of the most fundamental and well-studied problems in the context of network design. We are given an undirected graph G, and the objective is to find a 2-edge-connected spanning subgraph H of G with the minimum number of edges. For this problem, a lot of approximation algorithms have been proposed in the literature. In particular, very recently, Garg, Grandoni, and Ameli gave an approximation algorithm for 2-ECSS with a factor of 1.326, which is the best approximation ratio. In this paper, under the assumption that a maximum triangle-free 2-matching can be found in polynomial time in a graph, we give a (1.3+ε)-approximation algorithm for 2-ECSS, where ε is an arbitrarily small positive fixed constant. Note that a complicated polynomial-time algorithm for finding a maximum triangle-free 2-matching is announced by Hartvigsen in his PhD thesis, but it has not been peer-reviewed or checked in any other way. In our algorithm, we compute a minimum triangle-free 2-edge-cover in G with the aid of the algorithm for finding a maximum triangle-free 2-matching. Then, with the obtained triangle-free 2-edge-cover, we apply the arguments by Garg, Grandoni, and Ameli.

Yusuke Kobayashi and Takashi Noguchi. An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 49:1-49:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2023.49, author = {Kobayashi, Yusuke and Noguchi, Takashi}, title = {{An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {49:1--49:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.49}, URN = {urn:nbn:de:0030-drops-193514}, doi = {10.4230/LIPIcs.ISAAC.2023.49}, annote = {Keywords: approximation algorithm, survivable network design, minimum 2-edge-connected spanning subgraph, triangle-free 2-matching} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

In this paper, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths 𝒫 and 𝒬 connecting the same set of terminal pairs, we aim to determine whether 𝒫 can be transformed to 𝒬 by repeatedly replacing one path with another path so that the intermediates are also k disjoint paths. The problem is called Disjoint Paths Reconfiguration. We first show that Disjoint Paths Reconfiguration is PSPACE-complete even when k = 2. On the other hand, we prove that, when the graph is embedded on a plane and all paths in 𝒫 and 𝒬 connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint s-t paths as a variant. We show that the disjoint s-t paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Rerouting Planar Curves and Disjoint Paths. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 81:1-81:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ICALP.2023.81, author = {Ito, Takehiro and Iwamasa, Yuni and Kakimura, Naonori and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta}, title = {{Rerouting Planar Curves and Disjoint Paths}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {81:1--81:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.81}, URN = {urn:nbn:de:0030-drops-181339}, doi = {10.4230/LIPIcs.ICALP.2023.81}, annote = {Keywords: Disjoint paths, combinatorial reconfiguration, planar graphs} }

Document

Track A: Algorithms, Complexity and Games

**Published in:** LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of the well-known associahedron. The associahedron is obtained as the graph associahedron of a path. It is a tantalizing and important open problem in theoretical computer science whether the computation of a combinatorial shortest path between two vertices of the associahedron can be done in polynomial time, which is identical to the computation of the flip distance between two triangulations of a convex polygon, and the rotation distance between two rooted binary trees. Our result shows that a certain generalized approach to tackling this open problem is not promising. As a corollary of our theorem, we prove that the computation of a combinatorial shortest path between two vertices of a polymatroid base polytope cannot be done in polynomial time unless P = NP. Since a combinatorial shortest path on the matroid base polytope can be computed in polynomial time, our result reveals an unexpected contrast between matroids and polymatroids.

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 82:1-82:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ICALP.2023.82, author = {Ito, Takehiro and Kakimura, Naonori and Kamiyama, Naoyuki and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio}, title = {{Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {82:1--82:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.82}, URN = {urn:nbn:de:0030-drops-181344}, doi = {10.4230/LIPIcs.ICALP.2023.82}, annote = {Keywords: Graph associahedra, combinatorial shortest path, NP-hardness, polymatroids} }

Document

**Published in:** LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

In 1973, Fisk proved that any 4-coloring of a 3-colorable triangulation of the 2-sphere can be obtained from any 3-coloring by a sequence of Kempe-changes. On the other hand, in the case where we are only allowed to recolor a single vertex in each step, which is a special case of a Kempe-change, there exists a 4-coloring that cannot be obtained from any 3-coloring.
In this paper, we present a linear-time checkable characterization of a 4-coloring of a 3-colorable triangulation of the 2-sphere that can be obtained from a 3-coloring by a sequence of recoloring operations at single vertices. In addition, we develop a quadratic-time algorithm to find such a recoloring sequence if it exists; our proof implies that we can always obtain a quadratic length recoloring sequence. We also present a linear-time checkable criterion for a 3-colorable triangulation of the 2-sphere that all 4-colorings can be obtained from a 3-coloring by such a sequence. Moreover, we consider a high-dimensional setting. As a natural generalization of our first result, we obtain a polynomial-time checkable characterization of a k-coloring of a (k-1)-colorable triangulation of the (k-2)-sphere that can be obtained from a (k-1)-coloring by a sequence of recoloring operations at single vertices and the corresponding algorithmic result. Furthermore, we show that the problem of deciding whether, for given two (k+1)-colorings of a (k-1)-colorable triangulation of the (k-2)-sphere, one can be obtained from the other by such a sequence is PSPACE-complete for any fixed k ≥ 4. Our results above can be rephrased as new results on the computational problems named k-Recoloring and Connectedness of k-Coloring Reconfiguration Graph, which are fundamental problems in the field of combinatorial reconfiguration.

Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Reconfiguration of Colorings in Triangulations of the Sphere. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.SoCG.2023.43, author = {Ito, Takehiro and Iwamasa, Yuni and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta}, title = {{Reconfiguration of Colorings in Triangulations of the Sphere}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {43:1--43:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.43}, URN = {urn:nbn:de:0030-drops-178936}, doi = {10.4230/LIPIcs.SoCG.2023.43}, annote = {Keywords: Graph coloring, Triangulation of the sphere, Combinatorial reconfiguration} }

Document

**Published in:** LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

For an undirected graph G and distinct vertices s₁, t₁, … , s_k, t_k called terminals, the shortest k-disjoint paths problem asks for k pairwise vertex-disjoint paths P₁, … , P_k such that P_i connects s_i and t_i for i = 1, … , k and the sum of their lengths is minimized. This problem is a natural optimization version of the well-known k-disjoint paths problem, and its polynomial solvability is widely open. One of the best results on the shortest k-disjoint paths problem is due to Datta et al. [Datta et al., 2018], who present a polynomial-time algorithm for the case when G is planar and all the terminals are on one face. In this paper, we extend this result by giving a polynomial-time randomized algorithm for the case when all the terminals except one are on some face of G. In our algorithm, we combine the arguments of Datta et al. with some results on the shortest disjoint (A + B)-paths problem shown by Hirai and Namba [Hirai and Namba, 2018]. To this end, we present a non-trivial bijection between k disjoint paths and disjoint (A + B)-paths, which is a key technical contribution of this paper.

Yusuke Kobayashi and Tatsuya Terao. One-Face Shortest Disjoint Paths with a Deviation Terminal. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2022.47, author = {Kobayashi, Yusuke and Terao, Tatsuya}, title = {{One-Face Shortest Disjoint Paths with a Deviation Terminal}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {47:1--47:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.47}, URN = {urn:nbn:de:0030-drops-173322}, doi = {10.4230/LIPIcs.ISAAC.2022.47}, annote = {Keywords: shortest disjoint paths, polynomial time algorithm, planar graph} }

Document

**Published in:** LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional allocations do not always exist when goods are indivisible, approximate notions of proportionality have been considered in the previous work. Among them, proportionality up to the maximin good (PROPm) has been the best approximate notion of proportionality that can be achieved for all instances. In this paper, we introduce the notion of proportionality up to the least valued good on average (PROPavg), which is a stronger notion than PROPm, and show that a PROPavg allocation always exists. Our results establish PROPavg as a notable non-trivial fairness notion that can be achieved for all instances. Our proof is constructive, and based on a new technique that generalizes the cut-and-choose protocol.

Yusuke Kobayashi and Ryoga Mahara. Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2022.55, author = {Kobayashi, Yusuke and Mahara, Ryoga}, title = {{Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {55:1--55:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.55}, URN = {urn:nbn:de:0030-drops-173402}, doi = {10.4230/LIPIcs.ISAAC.2022.55}, annote = {Keywords: Discrete Fair Division, Indivisible Goods, Proportionality} }

Document

**Published in:** LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2022.15, author = {Bousquet, Nicolas and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and Ouvrard, Paul and Suzuki, Akira and Wasa, Kunihiro}, title = {{Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {15:1--15:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.15}, URN = {urn:nbn:de:0030-drops-158253}, doi = {10.4230/LIPIcs.STACS.2022.15}, annote = {Keywords: combinatorial reconfiguration, spanning trees, PSPACE, polynomial-time algorithms} }

Document

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

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.

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

**Published in:** LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable to achieve optimal social welfare without a central tie-breaking coordinator. In the case of two buyers with matroid rank valuations, we give polynomial-time algorithms that always find such prices when one of the matroids is a simple partition matroid or both matroids are strongly base orderable. This result partially answers a question raised by Düetting and Végh in 2017. We further formalize a weighted variant of the conjecture of Düetting and Végh, and show that the weighted variant can be reduced to the unweighted one based on the weight-splitting theorem for weighted matroid intersection by Frank. We also show that a similar reduction technique works for M^♮-concave functions, or equivalently, for gross substitutes functions.

Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi. Market Pricing for Matroid Rank Valuations. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.ISAAC.2020.39, author = {B\'{e}rczi, Krist\'{o}f and Kakimura, Naonori and Kobayashi, Yusuke}, title = {{Market Pricing for Matroid Rank Valuations}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.39}, URN = {urn:nbn:de:0030-drops-133833}, doi = {10.4230/LIPIcs.ISAAC.2020.39}, annote = {Keywords: Pricing schemes, Walrasian equilibrium, gross substitutes valuations, matroid rank functions} }

Document

**Published in:** LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Let G be a graph and T₁,T₂ be two spanning trees of G. We say that T₁ can be transformed into T₂ via an edge flip if there exist two edges e ∈ T₁ and f in T₂ such that T₂ = (T₁⧵e) ∪ f. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed in [Takehiro Ito et al., 2011].
We investigate the problem of determining, given two spanning trees T₁,T₂ with an additional property Π, if there exists an edge flip transformation from T₁ to T₂ keeping property Π all along.
First we show that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at most k (for any fixed k ≥ 3) leaves is PSPACE-complete.
We then prove that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at least k leaves (where k is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when k = n-2.

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of Spanning Trees with Many or Few Leaves. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ESA.2020.24, author = {Bousquet, Nicolas and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and Ouvrard, Paul and Suzuki, Akira and Wasa, Kunihiro}, title = {{Reconfiguration of Spanning Trees with Many or Few Leaves}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.24}, URN = {urn:nbn:de:0030-drops-128909}, doi = {10.4230/LIPIcs.ESA.2020.24}, annote = {Keywords: combinatorial reconfiguration, spanning trees, PSPACE, polynomial-time algorithms} }

Document

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

For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. The Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive t-spanners, the Minimum Additive t-Spanner Problem is hard to handle and hence only few results are known for it. In this paper, we study the Minimum Additive t-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter, and give a fixed-parameter algorithm for it. We also extend our result to the case with both a multiplicative approximation factor α and an additive approximation parameter β, which we call (α, β)-spanners.

Yusuke Kobayashi. An FPT Algorithm for Minimum Additive Spanner Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kobayashi:LIPIcs.STACS.2020.11, author = {Kobayashi, Yusuke}, title = {{An FPT Algorithm for Minimum Additive Spanner Problem}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {11:1--11:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.11}, URN = {urn:nbn:de:0030-drops-118729}, doi = {10.4230/LIPIcs.STACS.2020.11}, annote = {Keywords: Graph algorithms, Fixed-parameter tractability, Graph spanner} }

Document

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

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.

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.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

**Published in:** LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

We study two variants of Maximum Cut, which we call Connected Maximum Cut and Maximum Minimal Cut, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas Maximum Cut on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.

Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi. Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eto_et_al:LIPIcs.IPEC.2019.13, author = {Eto, Hiroshi and Hanaka, Tesshu and Kobayashi, Yasuaki and Kobayashi, Yusuke}, title = {{Parameterized Algorithms for Maximum Cut with Connectivity Constraints}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {13:1--13:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.13}, URN = {urn:nbn:de:0030-drops-114747}, doi = {10.4230/LIPIcs.IPEC.2019.13}, annote = {Keywords: Maximum cut, Parameterized algorithm, NP-hardness, Graph parameter} }

Document

**Published in:** LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuristic. In this paper, we prove that this empirically fast algorithm runs in O(3.460^k n) time, where k is the solution size. This improves the previous best O(3.619^k n)-time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf. Process. Lett., 2014).

Yoichi Iwata and Yusuke Kobayashi. Improved Analysis of Highest-Degree Branching for Feedback Vertex Set. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 22:1-22:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{iwata_et_al:LIPIcs.IPEC.2019.22, author = {Iwata, Yoichi and Kobayashi, Yusuke}, title = {{Improved Analysis of Highest-Degree Branching for Feedback Vertex Set}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {22:1--22:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.22}, URN = {urn:nbn:de:0030-drops-114833}, doi = {10.4230/LIPIcs.IPEC.2019.22}, annote = {Keywords: Feedback Vertex Set, Branch and bound, Measure and conquer} }

Document

**Published in:** LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Shortest Reconfiguration of Perfect Matchings via Alternating Cycles. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ESA.2019.61, author = {Ito, Takehiro and Kakimura, Naonori and Kamiyama, Naoyuki and Kobayashi, Yusuke and Okamoto, Yoshio}, title = {{Shortest Reconfiguration of Perfect Matchings via Alternating Cycles}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {61:1--61:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.61}, URN = {urn:nbn:de:0030-drops-111823}, doi = {10.4230/LIPIcs.ESA.2019.61}, annote = {Keywords: Matching, Combinatorial reconfiguration, Alternating cycles, Combinatorial shortest paths} }

Document

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

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.

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.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

**Published in:** LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars.

Takehiro Ito, Naonori Kakimura, and Yusuke Kobayashi. Complexity of the Multi-Service Center Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 48:1-48:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ISAAC.2017.48, author = {Ito, Takehiro and Kakimura, Naonori and Kobayashi, Yusuke}, title = {{Complexity of the Multi-Service Center Problem}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {48:1--48:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.48}, URN = {urn:nbn:de:0030-drops-82536}, doi = {10.4230/LIPIcs.ISAAC.2017.48}, annote = {Keywords: facility location, graph algorithm, multi-service location} }

Document

**Published in:** LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

In the k disjoint shortest paths problem (k-DSPP), we are given a graph and its vertex pairs (s_1, t_1), ... , (s_k, t_k), and the objective is to find k pairwise disjoint paths P_1, ... , P_k such that each path P_i is a shortest path from s_i to t_i, if they exist. If the length of each edge is equal to zero, then this problem amounts to the disjoint paths problem, which is one of the well-studied problems in algorithmic graph theory and combinatorial optimization. Eilam-Tzoreff (1998) focused on the case when the length of each edge is positive, and showed that the undirected version of 2-DSPP can be solved in polynomial time. Polynomial solvability of the directed version was posed as an open problem by Eilam-Tzoreff (1998). In this paper, we solve this problem affirmatively, that is, we give a first polynomial time algorithm for the directed version of 2-DSPP when the length of each edge is positive. Note that the 2 disjoint paths problem in digraphs is NP-hard, which implies that the directed 2-DSPP is NP-hard if the length of each edge can be zero. We extend our result to the case when the instance has two terminal pairs and the number of paths is a fixed constant greater than two. We also show that the undirected k-DSPP and the vertex-disjoint version of the directed k-DSPP can be solved in polynomial time if the input graph is planar and k is a fixed constant.

Kristof Berczi and Yusuke Kobayashi. The Directed Disjoint Shortest Paths Problem. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.ESA.2017.13, author = {Berczi, Kristof and Kobayashi, Yusuke}, title = {{The Directed Disjoint Shortest Paths Problem}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.13}, URN = {urn:nbn:de:0030-drops-78246}, doi = {10.4230/LIPIcs.ESA.2017.13}, annote = {Keywords: Disjoint paths, shortest path, polynomial time algorithm} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Finding edge-disjoint odd cycles is one of the most important problems
in graph theory, graph algorithm and combinatorial optimization. In
fact, it is closely related to the well-known max-cut problem. One of
the difficulties of this problem is that the Erdös-Pósa property does not hold for odd cycles in general. Motivated by this fact, we prove that for any positive integer k, there exists an integer f(k) satisfying the following: For any 4-edge-connected graph G=(V,E),
either G has edge-disjoint k odd cycles or there exists an edge set F
subseteq E with |F| <= f(k) such that G-F is bipartite. We note that
the 4-edge-connectivity is best possible in this statement.
Similar approach can be applied to an algorithmic question. Suppose
that the input graph G is a 4-edge-connected graph with n vertices.
We show that, for any epsilon > 0, if k = O ((log log log n)^{1/2-epsilon}), then the edge-disjoint k odd cycle packing in G can be solved in polynomial time of n.

Ken-ichi Kawarabayashi and Yusuke Kobayashi. Edge-disjoint Odd Cycles in 4-edge-connected Graphs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 206-217, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kawarabayashi_et_al:LIPIcs.STACS.2012.206, author = {Kawarabayashi, Ken-ichi and Kobayashi, Yusuke}, title = {{Edge-disjoint Odd Cycles in 4-edge-connected Graphs}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {206--217}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.206}, URN = {urn:nbn:de:0030-drops-34173}, doi = {10.4230/LIPIcs.STACS.2012.206}, annote = {Keywords: odd-cycles, disjoint paths problem, Erd\"{o}s-Posa property, packing algorithm, 4-edge-connectivity} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

A key theorem in algorithmic graph-minor theory is a min-max relation
between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson
and Seymour, which ultimately proves Wagner's Conjecture about the structure of minor-closed graph properties.
In 2008, Demaine and Hajiaghayi proved a remarkable linear min-max
relation for graphs excluding any fixed minor H: every H-minor-free
graph of treewidth at least c_H r has an r times r-grid minor for some
constant c_H. However, as they pointed out, there is still a major
problem left in this theorem. The problem is that their proof heavily
depends on Graph Minor Theory, most of which lacks explicit bounds and
is believed to have very large bounds. Hence c_H is not explicitly
given in the paper and therefore this result is usually not strong
enough to derive efficient algorithms.
Motivated by this problem, we give another (relatively short and
simple) proof of this result without using big machinery of Graph
Minor Theory. Hence we can give an explicit bound for c_H (an exponential function of a polynomial of |H|). Furthermore, our result
gives a constant w=2^O(r^2 log r) such that every graph of treewidth
at least w has an r times r-grid minor, which improves the previously
known best bound 2^Theta(r^5)$ given by Robertson, Seymour, and Thomas
in 1994.

Ken-ichi Kawarabayashi and Yusuke Kobayashi. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 278-289, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kawarabayashi_et_al:LIPIcs.STACS.2012.278, author = {Kawarabayashi, Ken-ichi and Kobayashi, Yusuke}, title = {{Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {278--289}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.278}, URN = {urn:nbn:de:0030-drops-34165}, doi = {10.4230/LIPIcs.STACS.2012.278}, annote = {Keywords: grid minor, treewidth, graph minor} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail