2026-07-22T12:37:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10212 2024-03-06T10:44:16Z ddc:004 open_access

The Parameterized Complexity of Finding Point Sets with Hereditary Properties Eppstein, David Lokshtanov, Daniel parameterized complexity fixed-parameter tractability point set pattern matching largest pattern-avoiding subset order type We consider problems where the input is a set of points in the plane and an integer k, and the task is to find a subset S of the input points of size k such that S satisfies some property. We focus on properties that depend only on the order type of the points and are monotone under point removals. We exhibit a property defined by three forbidden patterns for which finding a k-point subset with the property is W[1]-complete and (assuming the exponential time hypothesis) cannot be solved in time n^{o(k/log k)}. However, we show that problems of this type are fixed-parameter tractable for all properties that include all collinear point sets, properties that exclude at least one convex polygon, and properties defined by a single forbidden pattern. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Eppstein and Daniel Lokshtanov 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.11 urn:nbn:de:0030-drops-102121 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.11 eng https://creativecommons.org/licenses/by/3.0/legalcode