A polynomial sized kernel for tracking paths problem

DOI10.1007/s00453-019-00602-8zbMath1436.68142OpenAlexW2955033360WikidataQ127563558 ScholiaQ127563558MaRDI QIDQ5919306

Saket Saurabh, Pratibha Choudhary, Aritra Banik, Daniel Lokshtanov, Venkatesh Raman

Publication date: 16 January 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00602-8

zbMATH Keywords

graphkernelfeedback vertex setparameterized complexityFPTtracking pathss-t paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Polynomial Time Algorithms for Tracking Path Problems ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Polynomial time algorithms for tracking path problems ⋮ Improved kernels for tracking paths ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Constant factor approximation for tracking paths and fault tolerant feedback vertex set ⋮ Structural parameterizations of Tracking Paths problem ⋮ Polynomial kernels for tracking shortest paths

Cites Work

• Unnamed Item
• Unnamed Item
• The disjoint paths problem in quadratic time
• Faster deterministic \textsc{Feedback Vertex Set}
• Extremal graph theory for metric dimension and diameter
• Landmarks in graphs
• A 4 k ² kernel for feedback vertex set
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Reducibility among Combinatorial Problems
• Tracking Paths
• Parameterized Algorithms