2008
12.17

Here is a problem that occurred to me while doing nothing (i.e., writing a proposal). Consider a given set of segments S={s1, …, sn} in the plane:

We are interested in finding a maximum independent set of segments out of this set of segments. Naturally, two segments are independent if they do not intersect. A possible solution might be for example:

Since finding this set is probably NPC, we are looking for an approximation to the maximum set.

Currently, the only result I am aware of, is the cute but somewhat unsatsifying solution of Independent set of intersection graphs of convex objects in 2D, by Agarwal and Mustafa. They provide a roughly O(sqrt( opt )) approximation by using Dilworth’s theorem.

It is of course an interesting and natural open problem to improve the approximation or provide hardness of approximation for this problem.

But this seems somewhat challenging (it would require thinking and other headache-inducing operations). So, consider the following variant, which seems to be new. We would like to choose a subsegement ti contained inside si, for i=1,…, n, such that:

  1. They are interior disjoint,
  2. and the total length of these segments is maximized (lets z denote the value of this optimal solution).

For example, a possible solution might look like:

I currently have an approximation for this that outputs a collection of segments of total length Omega(L / sqrt(n)), where L is the total length of the segments of S.

My question: Can you do better than this? Are you aware of any related work on this problem?

  1. Your problem hasn’t instantly solved itself for me yet. But the likely NP-completeness you mention for max independent set in intersection graphs of line segments is in fact known. The reference is Imai and Asano, Finding the connected components
    and a maximum clique of an intersection graph of rectangles in the plane, J. Algorithms 4:310-323, 1983. Although I think their reduction produces segments that overlap along nonzero length, and that’s why we reproved it for segments that only cross properly in our recent Geometry Processing paper on motorcycle graphs (which your non-crossing segment solution resembles, by the way), http://www.ics.uci.edu/~goodrich/pubs/geomproc.pdf. The proof is an easy reduction from independent set in cubic planar graphs.

  2. Thanks for the info David. I noticed the similarity to motorcycle graphs, but I did not see a direct connection except the visual similarity.

    I also fixed the figures. There was some wackiness going on with the links…

  3. Here are references on the FP tractability of the independent set problem in segment intersection graphs :
    D. Marx: Parametrized Complexity of Independence and Domination on Geometric Graphs, IWPEC 2006
    J. Kára and J. Kratochvíl: Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs, IWPEC 2006

  4. Actually, yesterday I read that a problem in the vecinity is open:
    find a largest clique in the intersection graph of segments.

  5. Yeh, it is an interesting problem. Do you have/know a reference?

  6. Check http://drops.dagstuhl.de/opus/volltexte/2007/1254/pdf/07281.SWM.Paper.1254.pdf , pages 4-5.