Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/919408

OpenURL Link
Title
Parameterized complexity of stabbing rectangles and squares in the plane
Author/Creator
Dom, Michael;  Fellows, Michael R.;  Rosamond, Frances A.
Institution
The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
Description
The NP-complete geometric covering problem rectangle stabbing is defined as follows: Given a set of horizontal and vertical lines in the plane, a set of rectangles in the plane, and a positive integer k, select at most k of the lines such that every rectangle is intersected by at least one of the selected lines. While it is known that the problem can be approximated in polynomial time with a factor of two, its parameterized complexity with respect to the parameter k was open so far—only its generalization to three or more dimensions was known to be W[1]-hard. Giving two fixed-parameter reductions, one from the W[1]-complete problem multicolored clique and one to the W[1]-complete problem short turing machine acceptance, we prove that rectangle stabbing is W[1]-complete with respect to the parameter k, which in particular means that there is no hope for fixed-parameter tractability with respect to the parameter k. Our reductions show also the W[1]-completeness of the more general problem set cover on instances that "almost have the consecutive-ones property", that is, on instances whose matrix representation has at most two blocks of 1s per row. For the special case of rectangle stabbing where all rectangles are squares of the same size we can also show W[1]-hardness, while the parameterized complexity of the special case where the input consists of rectangles that do not overlap is open. By giving an algorithm running in (4k+1)k·nO(1) time, we show that rectangle stabbing is fixed-parameter tractable in the still NP-hard case where both these restrictions apply.
Relation
3rd International Workshop, WALCOM Algorithms and Computation. WALCOM Algorithms and Computation: Third International Workshop Proceedings (Kolkata, India 18-20 February, 2009) p. 298-309
Publisher Link
http://dx.doi.org/10.1007/978-3-642-00202-1_26
Date
2009
Publisher
Springer Berlin
Keyword(s)
rectangle stabbing;  multicolored clique;  short turing machine acceptance;  set cover
Resource Type
conference paper
Identifier
http://hdl.handle.net/1959.13/919408
Identifier
ISBN:9783642002014
Reviewed
Reviewed
29 Visitors 33 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"Parameterized complexity of stabbing rectangles and squares in the plane"
 
OR