A simple quadratic kernel for Token Jumping on surfaces
<|reference_start|>A simple quadratic kernel for Token Jumping on surfaces: The problem \textsc{Token Jumping} asks whether, given a graph $G$ and two independent sets of \emph{tokens} $I$ and $J$ of $G$, we can transform $I$ into $J$ by changing the position of a single token in each step and having an independent set of tokens throughout. We show that there is a polynomial-time algorithm that, given an instance of \textsc{Token Jumping}, computes an equivalent instance of size $O(g^2 + gk + k^2)$, where $g$ is the genus of the input graph and $k$ is the size of the independent sets.<|reference_end|>
@article{cranston2024a,
    title={A simple quadratic kernel for Token Jumping on surfaces},
    author={Daniel W. Cranston, Moritz M"uhlenthaler, Benjamin Peyrille},
    journal={arXiv preprint arXiv:2408.04743},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.04743},
    primaryClass={cs.DS cs.DM}
}