# Polynomial Kernels for Tracking Shortest Paths

Article · Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondřej Suchý, Tomáš Valla

- Archive id: arxiv:2202.11927
- Published: 2022-02-24
- Venue: Information Processing Letters
- DOI: https://doi.org/10.1016/j.ipl.2022.106315
- arXiv: https://arxiv.org/abs/2202.11927
- Citations: 3
- Source URL: https://arxiv.org/abs/2202.11927
- PDF: https://arxiv.org/pdf/2202.11927
- Provenance: arxiv

## Abstract

Given an undirected graph $G=(V,E)$, vertices $s,t\\in V$, and an integer $k$, Tracking Shortest Paths requires deciding whether there exists a set of $k$ vertices $T\\subseteq V$ such that for any two distinct shortest paths between $s$ and $t$, say $P\_1$ and $P\_2$, we have $T\\cap V(P\_1)\\neq T\\cap V(P\_2)$. In this paper, we give the first polynomial size kernel for the problem. Specifically we show the existence of a kernel with $\\mathcal{O}(k^2)$ vertices and edges in general graphs and a kernel with $\\mathcal{O}(k)$ vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with $\\mathcal{O}(k^4)$ vertices and edges for Tracking Shortest Paths in general graphs and a kernel with $\\mathcal{O}(k^2)$ vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.