2026-07-22T19:23:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8568 2024-03-06T10:41:30Z ddc:004 open_access

On the Parameterized Complexity of Red-Blue Points Separation Bonnet, Édouard Giannopoulos, Panos Lampis, Michael red-blue points separation geometric problem W[1]-hardness FPT algorithm ETH-based lower bound We study the following geometric separation problem: Given a set R of red points and a set B of blue points in the plane, find a minimum-size set of lines that separate R from B. We show that, in its full generality, parameterized by the number of lines k in the solution, the problem is unlikely to be solvable significantly faster than the brute-force n^{O(k)}-time algorithm, where n is the total number of points. Indeed, we show that an algorithm running in time f(k)n^{o(k/log k)}, for any computable function f, would disprove ETH. Our reduction crucially relies on selecting lines from a set with a large number of different slopes (i.e., this number is not a function of k). Conjecturing that the problem variant where the lines are required to be axis-parallel is FPT in the number of lines, we show the following preliminary result. Separating R from B with a minimum-size set of axis-parallel lines is FPT in the size of either set, and can be solved in time O^*(9^{|B|}) (assuming that B is the smallest set). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Panos Giannopoulos and Michael Lampis 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.8 urn:nbn:de:0030-drops-85687 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode