Haoran Qi

collaborators

2 papers

cs.DS2026

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths

Yang Cao, Haoran Qi, Hanzhi Wang

For $k$ vertex-disjoint paths with prescribed endpoints in a directed acyclic graph (DAG), the $O (m n^{k - 1})$ -time pebbling algorithm of Fortune, Hopcroft, and Wyllie [TCS 1980] has…

cs.CC2026

$ℓ_{p}$ -Norm Maximization over Zonotopes Is W[1]-Hard

Yang Cao, Haoran Qi, Hanzhi Wang

We study $ℓ_{p}$ -norm maximization over zonotopes given by rational generators, with input length $L$ . For fixed $p = a / b > 1$ , the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mat…

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths

ℓp​-Norm Maximization over Zonotopes Is W[1]-Hard

$ℓ_{p}$ -Norm Maximization over Zonotopes Is W[1]-Hard