Masaaki Kanzaki

dblp:266/2235 · DBLP profile ↗
← Back
4ranked-venue papers
2as first author
3since 2021 · last 2024
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 4 · 2 first-author · 3 since 2021
YearPublicationVenuePosition
2024 Computational complexity of jumping block puzzles
Masaaki Kanzaki, Yota Otachi, Giovanni Viglietta, Ryuhei Uehara
Theor. Comput. Sci.1
2022 Parameterized Complexity of (A, ℓ )-Path Packing
abstract
Abstract Given a graph $$G = (V,E)$$ G = ( V , E ) , $$A \subseteq V$$ A ⊆ V , and integers k and $$\ell $$ ℓ , the $$(A,\ell )$$ ( A , ℓ ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly $$\ell $$ ℓ that have endpoints in A and internal points in $$V{\setminus }A$$ V \ A . We study the parameterized complexity of this problem with parameters |A|, $$\ell $$ ℓ , k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when $$\ell \le 3$$ ℓ ≤ 3 , while it is NP-complete for constant $$\ell \ge 4$$ ℓ ≥ 4 . We also show that the problem is W[1]-hard parameterized by pathwidth $${}+|A|$$ + | A | , while it is fixed-parameter tractable parameterized by treewidth $${}+\ell $$ + ℓ . Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at most $$\ell $$ ℓ . We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or $$\ell $$ ℓ is a constant.
Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Michael Lampis, Hirotaka Ono 0001, Yota Otachi
Algorithmica3
2021 Computational Complexity of Jumping Block Puzzles
Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara
COCOON1
2020 Parameterized Complexity of (A, ℓ )-Path Packing
Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi 0001, Michael Lampis, Hirotaka Ono 0001, Yota Otachi
IWOCA3