Document

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

Given a directed edge-weighted graph G = (V, E) with beer vertices B ⊆ V, a beer path between two vertices u and v is a path between u and v that visits at least one beer vertex in B, and the beer distance between two vertices is the shortest length of beer paths. We consider indexing problems on beer paths, that is, a graph is given a priori, and we construct some data structures (called indexes) for the graph. Then later, we are given two vertices, and we find the beer distance or beer path between them using the data structure. For such a scheme, efficient algorithms using indexes for the beer distance and beer path queries have been proposed for outerplanar graphs and interval graphs. For example, Bacic et al. (2021) present indexes with size O(n) for outerplanar graphs and an algorithm using them that answers the beer distance between given two vertices in O(α(n)) time, where α(⋅) is the inverse Ackermann function; the performance is shown to be optimal. This paper proposes indexing data structures and algorithms for beer path queries on general graphs based on two types of graph decomposition: the tree decomposition and the triconnected component decomposition. We propose indexes with size O(m+nr²) based on the triconnected component decomposition, where r is the size of the largest triconnected component. For a given query u,v ∈ V, our algorithm using the indexes can output the beer distance in query time O(α(m)). In particular, our indexing data structures and algorithms achieve the optimal performance (the space and the query time) for series-parallel graphs, which is a wider class of outerplanar graphs.

Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama. Shortest Beer Path Queries Based on Graph Decomposition. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2023.37, author = {Hanaka, Tesshu and Ono, Hirotaka and Sadakane, Kunihiko and Sugiyama, Kosuke}, title = {{Shortest Beer Path Queries Based on Graph Decomposition}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {37:1--37:20}, 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.37}, URN = {urn:nbn:de:0030-drops-193397}, doi = {10.4230/LIPIcs.ISAAC.2023.37}, annote = {Keywords: graph algorithm, shortest path problem, SPQR tree} }

Document

**Published in:** LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)

We study the approximability of the Longest Run Subsequence problem (LRS for short). For a string S = s_1 ⋯ s_n over an alphabet Σ, a run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S' of S is a sequence in which every symbol σ ∈ Σ occurs in at most one run. Given a string S, the goal of LRS is to find a longest run subsequence S^* of S such that the length |S^*| is maximized over all the run subsequences of S. It is known that LRS is APX-hard even if each symbol has at most two occurrences in the input string, and that LRS admits a polynomial-time k-approximation algorithm if the number of occurrences of every symbol in the input string is bounded by k. In this paper, we design a polynomial-time (k+1)/2-approximation algorithm for LRS under the k-occurrence constraint on input strings. For the case k = 2, we further improve the approximation ratio from 3/2 to 4/3.

Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka. Approximation Algorithms for the Longest Run Subsequence Problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 259, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{asahiro_et_al:LIPIcs.CPM.2023.2, author = {Asahiro, Yuichi and Eto, Hiroshi and Gong, Mingyang and Jansson, Jesper and Lin, Guohui and Miyano, Eiji and Ono, Hirotaka and Tanaka, Shunichi}, title = {{Approximation Algorithms for the Longest Run Subsequence Problem}}, booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)}, pages = {2:1--2:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-276-1}, ISSN = {1868-8969}, year = {2023}, volume = {259}, editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.2}, URN = {urn:nbn:de:0030-drops-179560}, doi = {10.4230/LIPIcs.CPM.2023.2}, annote = {Keywords: Longest run subsequence problem, bounded occurrence, approximation algorithm} }

Document

**Published in:** LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)

The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this paper, we study four variants of LCS: the Repetition-Bounded Longest Common Subsequence problem (RBLCS) [Yuichi Asahiro et al., 2020], the Multiset-Restricted Common Subsequence problem (MRCS) [Radu Stefan Mincu and Alexandru Popa, 2018], the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS) [Mauro Castelli et al., 2017; Mauro Castelli et al., 2019]. Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225ⁿ)-time, dynamic programming (DP)-based algorithm for RBLCS was proposed [Yuichi Asahiro et al., 2020], where the two input sequences have lengths n and poly(n). We first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422ⁿ) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422ⁿ) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS.

Yuichi Asahiro, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Tadatoshi Utashima. Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{asahiro_et_al:LIPIcs.CPM.2022.15, author = {Asahiro, Yuichi and Jansson, Jesper and Lin, Guohui and Miyano, Eiji and Ono, Hirotaka and Utashima, Tadatoshi}, title = {{Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {15:1--15:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.15}, URN = {urn:nbn:de:0030-drops-161424}, doi = {10.4230/LIPIcs.CPM.2022.15}, annote = {Keywords: Repetition-bounded longest common subsequence problem, multiset restricted longest common subsequence problem, one-side-filled longest common subsequence problem, two-side-filled longest common subsequence problem, exact algorithms, and approximation algorithms} }

Document

**Published in:** LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in O(n log n) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For sqrt(n) <= s <= n, we present algorithms that use O(s log n) bits and O(1/s n^2 log n) time for computing the length of a longest increasing subsequence, and O(1/s n^2 log^2 n) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, and Jun Tarui. Space-Efficient Algorithms for Longest Increasing Subsequence. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kiyomi_et_al:LIPIcs.STACS.2018.44, author = {Kiyomi, Masashi and Ono, Hirotaka and Otachi, Yota and Schweitzer, Pascal and Tarui, Jun}, title = {{Space-Efficient Algorithms for Longest Increasing Subsequence}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {44:1--44:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.44}, URN = {urn:nbn:de:0030-drops-84911}, doi = {10.4230/LIPIcs.STACS.2018.44}, annote = {Keywords: longest increasing subsequence, patience sorting, space-efficient algorithm} }

Document

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

In this paper, we study covering and domination problems on directed graphs.
Although undirected Vertex Cover and Edge Dominating Set are well-studied classical graph problems, the directed versions have not been studied much due to the lack of clear definitions.
We give natural definitions for Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set as directed generations of Vertex Cover and Edge Dominating Set.
For these problems, we show that
(1) Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set are NP-complete on planar directed acyclic graphs except when r=1 or (p,q)=(0,0),
(2) if r>=2, Directed r-In (Out) Vertex Cover is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs,
(3) if either p or q is greater than 1, Directed (p,q)-Edge Dominating Set is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs,
(4) all problems can be solved in polynomial time on trees, and
(5) Directed (0,1),(1,0),(1,1)-Edge Dominating Set are fixed-parameter tractable in general graphs.
The first result implies that (directed) r-Dominating Set on directed line graphs is NP-complete even if r=1.

Tesshu Hanaka, Naomi Nishimura, and Hirotaka Ono. On Directed Covering and Domination Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2017.45, author = {Hanaka, Tesshu and Nishimura, Naomi and Ono, Hirotaka}, title = {{On Directed Covering and Domination Problems}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {45:1--45: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.45}, URN = {urn:nbn:de:0030-drops-82460}, doi = {10.4230/LIPIcs.ISAAC.2017.45}, annote = {Keywords: directed graph, vertex cover, dominating set, edge dominating set, fixed-parameter algorithms} }

Document

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

In the economic activities,
the central bank has an important role to cover payments of banks,
when they are short of funds to clear their debts.
For this purpose, the central bank timely puts funds so that the economic activities go smooth.
Since payments in this mechanism are processed sequentially,
the total amount of funds put by the central bank critically
depends on the order of the payments.
Then an interest goes to the amount to prepare
if the order of the payments can be controlled by the central bank,
or if it is determined under the worst case scenario.
This motivates us to introduce a brand-new problem,
which we call the settlement fund circulation problem.
The problems are formulated as follows:
Let G=(V,A) be a directed multigraph with a vertex set V and an arc set A.
Each arc a\in A is endowed debt d(a)\ge 0,
and the debts are settled sequentially under a sequence \pi of arcs.
Each vertex v\in V is put fund in the amount of p_{\pi}(v)\ge 0
under the sequence.
The minimum/maximum settlement fund circulation problem (Min-SFC/Max-SFC)
in a given graph G with debts d: A\rightarrow \mathbb{R}_{+}\cup \{0\}
asks to find a bijection \pi:A\to \{1,2,\dots,|A|\}
that minimizes/maximizes the total funds \sum _{v\in V}p_{\pi }(v).
In this paper, we show that
both Min-SFC and Max-SFC are NP-hard;
in particular, Min-SFC is
(I) strongly NP-hard even if G is
(i) a multigraph with |V|=2 or (ii) a simple graph with treewidth at most two,and is (II) (not necessarily strongly) NP-hard for simple trees of diameter four,
while it is solvable in polynomial time for stars.
Also, we identify several polynomial time solvable cases for both problems.

Hitoshi Hayakawa, Toshimasa Ishii, Hirotaka Ono, and Yushi Uno. Settlement Fund Circulation Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hayakawa_et_al:LIPIcs.ISAAC.2017.46, author = {Hayakawa, Hitoshi and Ishii, Toshimasa and Ono, Hirotaka and Uno, Yushi}, title = {{Settlement Fund Circulation Problem}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {46:1--46:13}, 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.46}, URN = {urn:nbn:de:0030-drops-82351}, doi = {10.4230/LIPIcs.ISAAC.2017.46}, annote = {Keywords: Fund settlement, Algorithm, Digraph, Scheduling} }

Document

**Published in:** LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3^k n k^{O(1)}) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56^k n^{O(1)}-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. A Faster Parameterized Algorithm for Pseudoforest Deletion. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2016.7, author = {Bodlaender, Hans L. and Ono, Hirotaka and Otachi, Yota}, title = {{A Faster Parameterized Algorithm for Pseudoforest Deletion}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {7:1--7:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.7}, URN = {urn:nbn:de:0030-drops-69246}, doi = {10.4230/LIPIcs.IPEC.2016.7}, annote = {Keywords: pseudoforest deletion, graph class, width parameter, parameterized complexity} }

Document

**Published in:** LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

The problem Max W-Light (Max W-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set.
In this paper, we show that for any fixed constant W, Max W-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width.
To have a polynomial-time algorithm for Max W-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin, Todinca, and Villanger [SIAM J. Comput., 44(1):57-87, 2015]. The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too.
We also study the parameterized complexity of the problems and show some tractability and intractability results.

Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.ISAAC.2016.20, author = {Bodlaender, Hans L. and Ono, Hirotaka and Otachi, Yota}, title = {{Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {20:1--20:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.20}, URN = {urn:nbn:de:0030-drops-67898}, doi = {10.4230/LIPIcs.ISAAC.2016.20}, annote = {Keywords: orientation, graph class, width parameter, parameterized complexity} }