1 citations · 1 across the 10 of their papers we have counts for
3 papers · 2 filters
Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi
We study the parameterized complexity of two classic problems on directed graphs: Hamiltonian Cycle and its generalization {\sc Longest Cycle}. Since 2008, it is known that Hamilto…
Expansion Lemma -- Variations and Applications to Polynomial-Time Preprocessing
Ashwin Jacob, Diptapriyo Majumdar, Venkatesh Raman
In parameterized complexity, it is well-known that a parameterized problem is fixed-parameter tractable if and only if it has a kernel - an instance equivalent to the input instanc…
Long Directed Detours: Reduction to -Disjoint Paths
Ashwin Jacob, Michał Włodarczyk, Meirav Zehavi
We study an "above guarantee" version of the {\sc Longest Path} problem in directed graphs: We are given a graph , two vertices and of , and a non-negative integer $k…