NP-completeness and FPT Results for Rectilinear Covering Problems

File Size Format
63385_1.pdf 450Kb Adobe PDF View
Title NP-completeness and FPT Results for Rectilinear Covering Problems
Author Estivill-Castro, Vladimir; Heednacram, Apichat; Suraweera, Francis
Journal Name Journal of Universal Computer Science
Editor Hermann Maurer
Year Published 2010
Place of publication Austria
Publisher Verlag der Technischen Universität Graz
Abstract This paper discusses three rectilinear (that is, axis-parallel) covering problems in d dimensions and their variants. The first problem is the RECTILINEAR LINE COVER where the inputs are n points in ℝd and a positive integer k, and we are asked to answer if we can cover these n points with at most k lines where these lines are restricted to be axis parallel. We show that this problem has efficient fixed-parameter tractable (FPT) algorithms. The second problem is the RECTILINEAR k-LINKS SPANNING PATH PROBLEM where the inputs are also n points in ℝd and a positive integer k but here we are asked to answer if there is a piecewise linear path through these n points having at most k line-segments (links) where these line-segments are axisparallel. We prove that this second problem is FPT under the assumption that no two line-segments share the same line. The third problem is the RECTILINEAR HYPERPLANE COVER problem and we are asked to cover a set of n points in d dimensions with k axis-parallel hyperplanes of d - 1 dimensions. We also demonstrate this has an FPT-algorithm. Previous to the results above, only conjectures were enunciated over several years on the NP-completeness of the RECTILINEAR MINIMUM LINK TRAVELING SALESMAN PROBLEM, the MINIMUM LINK SPANNING PATH PROBLEM and the RECTILINEAR HYPERPLANE COVER. We provide the proof that the RECTILINEAR MINIMUM LINK TRAVELING SALESMAN PROBLEM and the RECTILINEAR MINIMUM LINK SPANNING PATH PROBLEM are NP-complete by a reduction from the ONE-IN-THREE 3-SAT problem. The NP-completeness of the RECTILINEAR HYPERPLANE COVER problem is proved by a reduction from 3-SAT. This suggests dealing with the intractability just discovered with fixed-parameter tractability. Moreover, if we extend our problems to a finite set of orientations, our approach proves these problems remain FPT.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.3217/jucs-016-05
Copyright Statement Copyright 2010 J.UCS. The attached file is reproduced here in accordance with the copyright policy of the publisher. Please refer to the journal's website for access to the definitive, published version.
Volume 15
Issue Number 5
Page from 622
Page to 652
ISSN 0948-695X
Date Accessioned 2010-08-14
Date Available 2010-09-30T09:13:47Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Analysis of Algorithms and Complexity
URI http://hdl.handle.net/10072/34022
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice