[Solved]: FPT algorithm for point line cover

Problem Detail: 

In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666.

The algorithm chooses each point p from a set S and then subdivides it into k-lines.

This can be seen as a special case of set cover. All points (each p belongs to P) are in a cartesian plane, and the algorithm needs to find if they can be covered by k lines (where each line l belongs to L). This image below clarifies it further:

My question is around what is written in the paper linked above at page 666 regarding where is p taken from: At some point during the text it says "Otherwise, the algorithm chooses an element p ∈ S'". However, further down in the algorithm it says "choose p ∈ S" (without the prime symbol).

Is p taken from S or S' (S prime)?

Thanks!

Asked By : testTester

Answered By : Luke Mathieson

The algorithm should say "choose $p \in S'$", that is, the text is the correct version, rather than the pseudocode.

Note how the algorithm works:

• $S',S_{1},\ldots,S_{k}$ form a partition of $S$ (i.e. every element of $S$ is in exactly one of $S',S_{1},\ldots,S_{k}$).
• At each step it chooses which $S_{i}$ to put $p$ into.
• Initially $S' = S$, and $S_{i} = \emptyset$ for all $i$.

So $S'$ is the set of points that still need to be covered, and $S_{i}$ is the set of points covering by hyperplane $i$, in some abstract sense. Thus the algorithm, at each iteration, picks an uncovered element from $S'$, and puts it in some $S_{i}$.

Interestingly, this error made it all the way to the journal version.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/46866

3.2K people like this

 Download Related Notes/Documents