査読付き論文

1. Deterministic $(2/3 - \varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries arXiv
   Tatsuya Terao
   To appear in Proceedings of the 19th Algorithms and Data Structures Symposium (WADS 2025)
   
   Abstract

   In the matroid intersection problem, we are given two matroids $\mathcal{M}_1 = (V, \mathcal{I}_1)$ and $\mathcal{M}_2 = (V, \mathcal{I}_2)$ defined on the same ground set $V$ of $n$ elements, and the objective is to find a common independent set $S \in \mathcal{I}_1 \cap \mathcal{I}_2$ of largest possible cardinality, denoted by $r$. In this paper, we consider a deterministic matroid intersection algorithm with only a nearly linear number of independence oracle queries. Our contribution is to present a deterministic $O(\frac{n}{\varepsilon} + r \log r)$-independence-query $(2/3-\varepsilon)$-approximation algorithm for any $\varepsilon > 0$. Our idea is very simple: we apply a recent $\tilde{O}(n \sqrt{r}/\varepsilon)$-independence-query $(1 - \varepsilon)$-approximation algorithm of Blikstad [ICALP 2021], but terminate it before completion. Moreover, we also present a semi-streaming algorithm for $(2/3 -\varepsilon)$-approximation of matroid intersection in $O(1/\varepsilon)$ passes.
2. Parameterized Quantum Query Algorithms for Graph Problems † arXiv proceeding slides@ESA
   Tatsuya Terao, Ryuhei Mori
   Proceedings of the 32nd Annual European Symposium on Algorithms (ESA 2024)
   
   Abstract

   In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for $k$-vertex cover and $k$-matching problems, and present lower bounds on the parameterized quantum query complexity. Then, we show that our quantum query algorithms are optimal up to a constant factor when the parameters are small. Our main results are as follows.
   Parameterized quantum query complexity of vertex cover. In the $k$-vertex cover problem, we are given an undirected graph $G$ with $n$ vertices and an integer $k$, and the objective is to determine whether $G$ has a vertex cover of size at most $k$. We show that the quantum query complexity of the $k$-vertex cover problem is $O(\sqrt{k}n + k^{3/2}\sqrt{n})$ in the adjacency matrix model. For the design of the quantum query algorithm, we use the method of kernelization, a well-known tool for the design of parameterized classical algorithms, combined with Grover's search.
   Parameterized quantum query complexity of matching. In the $k$-matching problem, we are given an undirected graph $G$ with $n$ vertices and an integer $k$, and the objective is to determine whether $G$ has a matching of size at least $k$. We show that the quantum query complexity of the $k$-matching problem is $O(\sqrt{k}n + k^{2})$ in the adjacency matrix model. We obtain this upper bound by using Grover's search carefully and analyzing the number of Grover's searches by making use of potential functions. We also show that the quantum query complexity of the maximum matching problem is $O(\sqrt{p}n + p^{2})$ where $p$ is the size of the maximum matching. For small $p$, it improves known bounds $\tilde{O}(n^{3/2})$ for bipartite graphs [Blikstad--v.d.Brand--Efron--Mukhopadhyay--Nanongkai, FOCS 2022] and $O(n^{7/4})$ for general graphs [Kimmel--Witter, WADS 2021].
   Lower bounds on parameterized quantum query complexity. We also present lower bounds on the quantum query complexities of the $k$-vertex cover and $k$-matching problems. The lower bounds prove the optimality of the above parameterized quantum query algorithms up to a constant factor when $k$ is small. Indeed, the quantum query complexities of the $k$-vertex cover and $k$-matching problems are both $\Theta(\sqrt{k} n)$ when $k = O(\sqrt{n})$ and $k = O(n^{2/3})$, respectively.
3. Subquadratic Submodular Maximization with a General Matroid Constraint arXiv proceeding slides@ICALP
   Yusuke Kobayashi, Tatsuya Terao
   Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024)
   
   Abstract

   We consider fast algorithms for monotone submodular maximization with a general matroid constraint. We present a randomized $(1 - 1/e - \varepsilon)$-approximation algorithm that requires $\tilde{O}_{\varepsilon}(\sqrt{r} n)$ independence oracle and value oracle queries, where $n$ is the number of elements in the matroid and $r \leq 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 $\tilde{O}_{\varepsilon}(r^2 + \sqrt{r}n)$ 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 $\tilde{O}(r^{3/2} t)$ independence oracle queries, while the previously best rounding algorithm by Chekuri-Vondrák-Zenklusen [FOCS 2010] requires $O(r^2 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.
4. Faster Matroid Partition Algorithms journal arXiv proceeding slides@ICALP poster(ja)
   Tatsuya Terao
   ACM Transactions on Algorithms (TALG), 2025
   A preliminary version appeared in Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023)
   
   Abstract

   In the matroid partitioning problem, we are given $k$ matroids $\mathcal{M}_1 = (V, \mathcal{I}_1), \dots , \mathcal{M}_k = (V, \mathcal{I}_k)$ defined over a common ground set $V$ of $n$ elements, and we need to find a partitionable set $S \subseteq V$ of largest possible cardinality, denoted by $p$. Here, a set $S \subseteq V$ is called partitionable if there exists a partition $(S_1, \dots , S_k)$ of $S$ with $S_i \in \mathcal{I}_i$ for $i = 1, \ldots, k$. In 1986, Cunningham [SICOMP 1986] presented a matroid partition algorithm that uses $O(n p^{3/2} + k n)$ independence oracle queries, which was the previously known best algorithm. This query complexity is $O(n^{5/2})$ when $k \leq n$.
   Our main result is to present a matroid partition algorithm that uses $\tilde{O}(k'^{1/3} n p + k n)$ independence oracle queries, where $k' = \min\{k, p\}$. This query complexity is $\tilde{O}(n^{7/3})$ when $k \leq n$, which improves upon that of Cunningham's algorithm. To obtain our algorithm, we present a new approach edge recycling augmentation, which can be attained through new ideas: an efficient utilization of the binary search technique by Nguyen [2019] and Chakrabarty-Lee-Sidford-Singla-Wong [FOCS 2019] and a careful analysis of the independence oracle query complexity. Our analysis differs significantly from the one for matroid intersection algorithms, because of the parameter $k$. We also present a matroid partition algorithm that uses $\tilde{O}((n + k) \sqrt{p})$ rank oracle queries.
5. One-Face Shortest Disjoint Paths with a Deviation Terminal proceeding slides@ISAAC poster(ja)
   Yusuke Kobayashi, Tatsuya Terao
   Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
   
   Abstract

   For an undirected graph $G$ and distinct vertices $s_1, t_1, \dots, s_k, t_k$ called terminals, the shortest $k$-disjoint paths problem asks for $k$ pairwise vertex-disjoint paths $P_1, \dots , P_k$ such that $P_i$ connects $s_i$ and $t_i$ for $i = 1, \dots , 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. [FSTTCS 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 [Algorithmica 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.

プレプリント

Coming soon.

国際学会発表

• Tatsuya Terao: Deterministic $(2/3 - \varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
  • The 19th Algorithms and Data Structures Symposium (WADS 2025), Toronto, Canada, August, 2025.
• Tatsuya Terao, Ryuhei Mori: Parameterized Quantum Query Algorithms for Graph Problems
  • The 32nd Annual European Symposium on Algorithms (ESA 2024), Egham, United Kingdom, Sep 4, 2024. slides
• Yusuke Kobayashi, Tatsuya Terao: Subquadratic Submodular Maximization with a General Matroid Constraint
  • The 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024), Tallinn, Estonia, July 9, 2024. slides
• Tatsuya Terao: Faster Matroid Partition Algorithms
  • The 13th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan, May 26, 2025.
  • The 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), Paderborn, Germany, July 14, 2023. slides
• Yusuke Kobayashi, Tatsuya Terao: One-Face Shortest Disjoint Paths with a Deviation Terminal
  • The 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Seoul, Korea, Dec 20, 2022. slides

国内学会発表

• 寺尾樹哉: 「準線形回の独立性オラクルへのクエリを使用するマトロイド交叉問題の決定的な$(2/3-\varepsilon)$-近似アルゴリズム」
  • 最適化の理論とアルゴリズム:未来を担う若手研究者の集い 2025, 2025年5月, 筑波大学.
• 寺尾樹哉, 森立平: 「グラフの問題に対するパラメータ化量子クエリ計算量」
  • 第51回量子情報技術研究会 (QIT51), 2024年11月27日, サンポートホール高松. slides
  • 2023年度冬のLAシンポジウム, 2024年2月20日, 京都大学. (発表時のタイトルは「頂点被覆とマッチングに対する最適なパラメータ化量子クエリ計算量」) slides
• 寺尾樹哉, 小林佑輔: 「マトロイド制約下での劣モジュラ関数最大化に対する高速なアルゴリズム」
  • 日本応用数理学会 2024年度年会 離散システム研究部会, 2024年9月16日, 京都大学. slides
  • 最適化の理論とアルゴリズム:未来を担う若手研究者の集い 2024, 2024年5月19日, 筑波大学. slides
• 寺尾樹哉: 「マトロイド分割問題に対する高速なアルゴリズム」
  • 離散数学とその応用研究集会2023 (JCCA 2023), 2023年8月30日, 愛知教育大学. slides
  • 最適化の理論とアルゴリズム:未来を担う若手研究者の集い 2023, 2023年5月20日, 筑波大学. slides
• 寺尾樹哉, 小林佑輔: 「除外ターミナルを含む同一面最短点素パス問題に対するアルゴリズム」
  • 日本応用数理学会第19回研究部会連合発表会, 離散システム研究部会, 2023年3月9日, 岡山理科大学. slides
  • 2022年度OR学会関西支部, 若手研究発表会, 2022年10月29日, 大阪大学. slides