32 citations · 56 across the 11 of their papers we have counts for
14 papers
ALE-Bench: A Benchmark for Long-Horizon Objective-Driven Algorithm Engineering
Yuki Imajuku, Kohki Horie, Yoichi Iwata +3
How well do AI systems perform in algorithm engineering for hard optimization problems in domains such as package-delivery routing, crew scheduling, factory production planning, an…
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen +1
Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can b…
Finding a Shortest Non-zero Path in Group-Labeled Graphs
Yoichi Iwata, Yutaro Yamaguchi
We study a constrained shortest path problem in group-labeled graphs with nonnegative edge length, called the shortest non-zero path problem. Depending on the group in question, th…
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
Yoichi Iwata, Yusuke Kobayashi
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 heuris…
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka
There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of su…
0/1/all CSPs, Half-Integral -path Packing, and Linear-Time FPT Algorithms
Yoichi Iwata, Yutaro Yamaguchi, Yuichi Yoshida
A recent trend in the design of FPT algorithms is exploiting the half-integrality of LP relaxations. In other words, starting with a half-integral optimal solution to an LP relaxat…
Cut Tree Construction from Massive Graphs
Takuya Akiba, Yoichi Iwata, Yosuke Sameshima +2
The construction of cut trees (also known as Gomory-Hu trees) for a given graph enables the minimum-cut size of the original graph to be obtained for any pair of vertices. Cut tree…
Linear-time Kernelization for Feedback Vertex Set
Yoichi Iwata
In this paper, we propose an algorithm that, given an undirected graph of edges and an integer , computes a graph and an integer in time such that (…
On the Equivalence among Problems of Bounded Width
Yoichi Iwata, Yuichi Yoshida
In this paper, we introduce a methodology, called decomposition-based reductions, for showing the equivalence among various problems of bounded-width. First, we show that the follo…
Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover
Takuya Akiba, Yoichi Iwata
We investigate the gap between theory and practice for exact branching algorithms. In theory, branch-and-reduce algorithms currently have the best time complexity for numerous impo…
Fast Dynamic Graph Algorithms for Parameterized Problems
Yoichi Iwata, Keigo Oka
Fully dynamic graph is a data structure that (1) supports edge insertions and deletions and (2) answers problem specific queries. The time complexity of (1) and (2) are referred to…
Half-integrality, LP-branching and FPT Algorithms
Yoichi Iwata, Magnus Wahlström, Yuichi Yoshida
A recent trend in parameterized algorithms is the application of polytope tools (specifically, LP-branching) to FPT algorithms (e.g., Cygan et al., 2011; Narayanaswamy et al., 2012…
Linear-Time FPT Algorithms via Network Flow
Yoichi Iwata, Keigo Oka, Yuichi Yoshida
In the area of parameterized complexity, to cope with NP-Hard problems, we introduce a parameter k besides the input size n, and we aim to design algorithms (called FPT algorithms)…
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
Takuya Akiba, Yoichi Iwata, Yuichi Yoshida
We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search f…