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.
