Bonnet, Édouard ;
Giannopoulos, Panos ;
Lampis, Michael
On the Parameterized Complexity of RedBlue Points Separation
Abstract
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 minimumsize 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 bruteforce 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 axisparallel is FPT in the number of lines, we show the following preliminary result.
Separating R from B with a minimumsize set of axisparallel 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).
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs:2018:8568,
author = {{\'E}douard Bonnet and Panos Giannopoulos and Michael Lampis},
title = {{On the Parameterized Complexity of RedBlue Points Separation}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {8:18:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770514},
ISSN = {18688969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8568},
URN = {urn:nbn:de:0030drops85687},
doi = {10.4230/LIPIcs.IPEC.2017.8},
annote = {Keywords: redblue points separation, geometric problem, W[1]hardness, FPT algorithm, ETHbased lower bound}
}
02.03.2018
Keywords: 

redblue points separation, geometric problem, W[1]hardness, FPT algorithm, ETHbased lower bound 
Seminar: 

12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Issue date: 

2018 
Date of publication: 

02.03.2018 