Eiben, Eduard ;
Kanj, Iyad
How to Navigate Through Obstacles?
Abstract
Given a set of obstacles and two points in the plane, is there a path between the two points that does not cross more than k different obstacles? This is a fundamental problem that has undergone a tremendous amount of work by researchers in various areas, including computational geometry, graph theory, wireless computing, and motion planning. It is known to be NPhard, even when the obstacles are very simple geometric shapes (e.g., unitlength line segments). The problem can be formulated and generalized into the following graph problem: Given a planar graph G whose vertices are colored by color sets, two designated vertices s, t in V(G), and k in N, is there an st path in G that uses at most k colors? If each obstacle is connected, the resulting graph satisfies the colorconnectivity property, namely that each color induces a connected subgraph.
We study the complexity and design algorithms for the above graph problem with an eye on its geometric applications. We prove a set of hardness results, among which a result showing that the colorconnectivity property is crucial for any hope for fixedparameter tractable (FPT) algorithms, as without it, the problem is W[SAT]hard parameterized by k. Previous results only implied that the problem is W[2]hard. A corollary of this result is that, unless W[2] = FPT, the problem cannot be approximated in FPT time to within a factor that is a function of k. By describing a generic plane embedding of the graph instances, we show that our hardness results translate to the geometric instances of the problem.
We then focus on graphs satisfying the colorconnectivity property. By exploiting the planarity of the graph and the connectivity of the colors, we develop topological results that allow us to prove that, for any vertex v, there exists a set of paths whose cardinality is upper bounded by a function of k, that "represents" the valid st paths containing subsets of colors from v. We employ these structural results to design an FPT algorithm for the problem parameterized by both k and the treewidth of the graph, and extend this result further to obtain an FPT algorithm for the parameterization by both k and the length of the path. The latter result generalizes and explains previous FPT results for various obstacle shapes, such as unit disks and fat regions.
BibTeX  Entry
@InProceedings{eiben_et_al:LIPIcs:2018:9052,
author = {Eduard Eiben and Iyad Kanj},
title = {{How to Navigate Through Obstaclesl}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {48:148:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9052},
URN = {urn:nbn:de:0030drops90528},
doi = {10.4230/LIPIcs.ICALP.2018.48},
annote = {Keywords: parameterized complexity and algorithms, motion planning, barrier coverage, barrier resilience, colored path, minimum constraint removal, planar graph}
}
04.07.2018
Keywords: 

parameterized complexity and algorithms, motion planning, barrier coverage, barrier resilience, colored path, minimum constraint removal, planar graph 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 