[HTML][HTML] Fixed-parameter tractability and lower bounds for stabbing problems

P Giannopoulos, C Knauer, G Rote, D Werner - Computational Geometry, 2013 - Elsevier
P Giannopoulos, C Knauer, G Rote, D Werner
Computational Geometry, 2013Elsevier
We study the following general stabbing problem from a parameterized complexity point of
view: Given a set S of n translates of an object in Rd, find a set of k lines with the property
that every object in S is “stabbed”(intersected) by at least one line. We show that when S
consists of axis-parallel unit squares in R2 the (decision) problem of stabbing S with axis-
parallel lines is W [1]-hard with respect to k (and thus, not fixed-parameter tractable unless
FPT= W [1]) while it becomes fixed-parameter tractable when the squares are disjoint. We …
We study the following general stabbing problem from a parameterized complexity point of view: Given a set S of n translates of an object in Rd, find a set of k lines with the property that every object in S is “stabbed” (intersected) by at least one line. We show that when S consists of axis-parallel unit squares in R2 the (decision) problem of stabbing S with axis-parallel lines is W[1]-hard with respect to k (and thus, not fixed-parameter tractable unless FPT=W[1]) while it becomes fixed-parameter tractable when the squares are disjoint. We also show that the problem of stabbing a set of disjoint unit squares in R2 with lines of arbitrary directions is W[1]-hard with respect to k. Several generalizations to other types of objects and lines with arbitrary directions are also presented. Finally, we show that deciding whether a set of unit balls in Rd can be stabbed by one line is W[1]-hard with respect to the dimension d.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果