David Eppstein – Publications

Publications with James A. Liu

• Tracking paths in planar graphs.
  D. Eppstein, M. T. Goodrich, P. Matias, and J. A. Liu.
  arXiv:1908.05445.
  Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
  Leibniz International Proceedings in Informatics (LIPIcs) 149, 2019, pp. 54:1–54:17.

  A tracking set for a given graph, with designated start and destination vertices, is a set of vertices such that any path from start to destination is determined by the subsequence of its vertices that belong to the tracking set. We show that finding the smallest tracking set is NP-hard but has a constant factor approximation, and can be solved exactly in fixed-parameter-tractable time for graphs of bounded width.