Given a graph with $n$ vertices and $m$ edges, $m \le {n \choose 2}$, we index the vertices from 1 to $n$, and denote every edge by $(l,r)$ where $1\le l < r \le n$. Find the maximum $k$ such that there is a matching consisting of $k$ edges satisfying $l_1<l_2<...<l_k$ and $r_1<r_2<...<r_k$.

This can also be thought of an interval selection problem with some unusual constraints. See each edge in the above graph as an interval $(l,r)$, pick the biggest subset of these intervals such that 1) $l_1<l_2<...<l_k$ and $r_1<r_2<...<r_k$, and 2) $l_i\neq r_j \ \ \forall i,j$.

A few remarks:

  • Note that the picked intervals can overlap, we just require the left and right endpoints to be 'order preserving'. E.g., picking (1,3) and (2,4) together is allowed.
  • If we remove requirement 2) in the interval problem, it then can be solved by dynamic programming. Adding 2) seems to make it very hard for DP as we need to keep track of all the endpoints used in partial solutions.
  • My conjecture is that this problem is NP-hard, but I spent some efforts and haven't been able to prove that.
  • In the graph problem, we can construct a conflict graph between the given edges because these constraints can be decomposed to 2-ary constraints, which means maximum independent set can solve this problem. However, it's hard to construct an instance of this problem to solve arbirary MIS.
  • The interval problem is a selection problem. There can also be a partition problem where we don't care whether each subset is biggest or not, but we want to partition all the intervals to the minimum number of subsets.

A counterexample while trying to follow the algmenting path approach for regular matching. Consider the following graph:

0--2--1--6--5--7  3--4

Let our order-constrained matching be {(1,2), (3,4), (5,6)}. We can find an algmenting path 0->2->1->6->5->7. The resulting new matching is {(0,2), (1,6), (5,7), (3,4)}. Just focusing on the algmenting path, there's no issue. However, there is an issue with the edge outside of the algmenting path, (3,4), because (1,6) and (3,4) violates the order constraint, so we cannot really take this augmenting path. This example shows that there is a certain global-ness in the problem because a local update (via augmenting path) can mess up with the other part of an existing solution.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.