Algorithm for Least Edge Intersections

(Before anyone asks, it's not homework.)

Say you have 2 Arrays y0 and y1 where

y0 = [1,2,3,4,5,6] and y1 = [2,1,6,3,4,5]

Notice y0[0] = y1[1] = 1, it essentially means y0[0] is connected to y1[1]. Similarly, y0[2] = y1[3] = 3 so they are "connected" as well.

Each element in one array has a corresponding entry in the second array. Imagine each element in the array as a vertex, and these connections as Edges being drawn 开发者_开发问答from one array to the other.

I need to find a set of edges (of maximum size) such that none of the "edges" (or lines) will intersect.

In the above example, notice,

1. Edge 1 and Edge 2 will intersect.
2. Edge 6 will intersect with Edge 3, Edge 4, Edge 5.

Therefore, the solution can be be 1,3,4,5 or 2,3,4,5 (size = 4) since none of those lines will intersect each other. There can be multiple solutions, but I need just one.

My Question, Is there any known CS Problem that resembles this? What algorithm should i be using?

I've tried to explain my problem with an example, however, incase it's still not clear i'll clarify any queries. Thanks in advance.

Assuming that no element is repeated in a single array, this is simply longest increasing subsequence.

Without loss of generality, assume that the first array, A1, is just [1, 2, 3, ..., n]. This transformation can be done in O(n) with a hash-set, or O(nlogn) with a BST.

Note that our set has a crossing if and only if it contains i and j with i < j but j appearing before i in the second array A2 (we know since i < j that i appears before j in A1).

Then if a set has no crossing it clearly corresponds to an increasing subsequence of A2 and vice versa.

Longest increasing subsequence has a simple O(n^2) solution and a slightly more complex O(nlogn) solution.

It is basically counting number of inversions problem.[Source - Section 5.3, Algorithm Design, Kleinberg and Tardos. http://books.google.co.in/books/about/Algorithm_Design.html?id=25p3mHu3ij8C]

What you are describing is known as the matching problem for bipartite graphs. I suspect there is something (as yet unstated) about the problem which makes it difficult to solve. So far you really haven't placed any restriction on what edges can be used. Supposing that there are certain edges (not all) available, those "possible" edges form a graph, and the ones you decide to use form a maximum matching. Finding a maximum matching in a graph is a polynomial time algorithm, and it is particularly easy to code for the bipartite case.

The title makes it sound as though circumstances might impose some circumstance so that "disjoint" edges might not be feasible ("least edge intersections"). Perhaps you want edge covering (or 1-cover), i.e. that every vertex belongs to at least one edge. Then, if the two "vertex" arrays are of different length, there will not be a "perfect matching", i.e. a matching that is also a cover. A classic result Hall's Marriage Theorem characterizes when there are perfect matchings in a bipartite graph. If the graph is regular (all vertices have equal degree), then König's Theorem tells us there is perfect matching (and more).

Added:

It may be worth stating what the picture seems to say about the restrictions on choosing edges. Two sets of vertices have coordinates {(i,0) | i=1,..,N} and {(j,1) | j=1,..,N}. There are N available edges, line segments that connect (i,0) and (j,1) whenever y0[i] = y1[j]. Although the subject line says "least edge intersections", a solution is a maximum subset of these edges that admits no intersections, a largest planar straight-line graph contained in a given permutation graph.

It is related to the 2-level crossing minimization problem considered here:

An Alternative Method to Crossing Minimization on Hierarchical Graphs -- P. Mutzel

"We suggest... removing the minimal number of edges such that the resulting graph is k-level planar... In this paper we address the case k = 2... [W]e address the problem of extracting a 2-level planar subgraph of maximum weight in a given 2-level graph. This problem is NP-hard."

The present problem imposes an equal number of points in the two vertex sets, the base graph is regular of degree 1, and no choice is allowed in the numbering or positioning of points. So it is not possible to conclude it is as hard as the one described in the above paper. However it does direct us to so-called "branch and bound" methods for the exact solution of such problems.

Let's consider the "edges" of the original problem as "nodes" of a new graph where two nodes are adjacent iff the original edges intersect. [This is an example of an intersection graph.] The problem as restated is now to find a maximum independent set of the new graph. The problems of that kind are in general NP-hard, but again we suspect the extent of the present problems may not be so general.

One reason to suspect a polynomial time algorithm could exist is the availability of polynomial time approximation algorithms for maximum independent subsets of intersection graphs for finite collections of planar convex sets:

Independent Set of Intersection Graphs of Convex Objects in 2D -- P. Agarwal and M Mustafa

"In this paper, we present approximation algorithms for the independent-set problem on intersection graphs of line segments and convex objects in the plane."

There is one further observation about the specialness of the present problem that seems to make it solvable in polynomial time. A circle graph is the intersection graph of line segments that can be drawn as chords of a circle. By a pertubation argument the straight-line edges of a permutation graph can be so drawn, without loss or introduction of intersections.

Now the maximum independent set problem for circle graphs can be solved in polynomial time. The Wikipedia article linked above gives this reference:

Nash, Nicholas; Gregg, David (2010), "An output sensitive algorithm for computing a maximum independent set of a circle graph", Information Processing Letters 116 (16): 630–634

I also found this reference in Google Books:

Valiente, Gabriel (2003), "A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs", Algorithms and computation: 14th Symposium, ISAAC 2003 Kyoto