English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Tracking of moving objects is crucial to security systems and networks. Givena graph $G$, terminal vertices $s$ and $t$, and an integer $k$, the\textsc{Tracking Paths} problem asks whether there exists at most $k$ vertices,which if marked as trackers, would ensure that the sequence of trackersencountered in each s-t path is unique. It is known that the problem is NP-hardand admits a kernel (reducible to an equivalent instance) with$\mathcal{O}(k^6)$ vertices and $\mathcal{O}(k^7)$ edges, when parameterized bythe size of the output (tracking set) $k$ [5]. An interesting question thatremains open is whether the existing kernel can be improved. In this paper weanswer this affirmatively: (i) For general graphs, we show the existence of akernel of size $\mathcal{O}(k^2)$, (ii) For planar graphs, we improve thisfurther by giving a kernel of size $\mathcal{O}(k)$. In addition, we also showthat finding a tracking set of size at most $n-k$ for a graph on $n$ verticesis hard for the parameterized complexity class W[1], when parameterized by $k$.

Improved Kernels for Tracking Path Problem