3
$\begingroup$

I'm trying to identify an algorithm to solve this computational problem

Input:

  • Bipartite graph (V, W, E), with E ⊆ V×W
  • A fixed order for both V and W: V = (v1, ..., vn) and W = (w1, ..., wm)

Output:

  • The subset of E of maximum cardinality in which there are no crossing edges.

The mental image is that the two vertex sets are arranged in two parallel arrays with edges between them, which may or may not cross. More formally, edges (vk, wl) and (vp, wq) cross if either 1) k < l and p > q, or 2) k > l and p < q.

Does anyone know about any published literature on this problem?

It seems that there is a much larger body of literature on the problem of choosing permutations of V and W to minimize edge crossing, which is NP-Hard. However, I'm working with a fixed permutation for both sets.

I've also identified a few papers that count the number of edge crossings under a fixed permutation:

However, none of these papers discuss the problem of minimizing edge crossings by removing edges.

There are a few more papers in which the algorithm selects a maximum non-crossing matching under a fixed permutation.

This is closer to the mark since it's maximizing the cardinality of an edge set, but I don't want to restrict the edge set to being a matching. Any leads?

$\endgroup$

1 Answer 1

1
$\begingroup$

Without loss of generality, assume every vertex has degree 1. Create $\deg(u)$ copies of a vertex $u$, then sort the created vertices in the order of the opposite vertex of the corresponding edge.

Then, the bipartite graph can be represented by a permutation as in permutation graphs. Now, a set of edges in the bipartite graph is non-crossing if and only if the corresponding sub-sequence of the permutation is increasing. This longest increasing subsequence problem is solvable in $O(n \log n)$ time, therefore the original problem is solvable in $O((|V| + |W| + |E|) \log (|V| + |W| + |E|))$ time.

$\endgroup$
1
  • $\begingroup$ That's perfect. Thanks! $\endgroup$
    – Jordan
    Aug 7 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.