David Eppstein - Publications

Publications with Daniel Lokshtanov

• The parameterized complexity of finding point sets with hereditary properties.
  D. Eppstein and D. Lokshtanov.
  arXiv:1808.02162
  Proc. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2018.
  Leibniz International Proceedings in Informatics (LIPIcs) 115, 2018, pp. 11:1–11:14.

  We exhibit a hereditary property of planar point sets (depending only on the order type of a point set) such that under standard assumptions there is no fixed-parameter-tractable algorithm to find a k-point subset with the property. On the other hand, several natural classes of properties have FPT algorithms for this problem, including the properties that are true for all collinear point sets or false for at least one convex polygon.

  (Slides)