Let bipartite graph, $G(U,W,E)$ such that $|U|=|W|=n$. vertices in each sides marked with number from $1$ to $n$.
Definition: An uncut match is a match such that if $(u_i, w_j), (u_a, w_b)$ are in the match then it can't be that $i>a$ and $b>j$ nor, $i<a$ and $b<j$.
Describe an algorithm to find a maximum "uncut match".
So I started defining the problem like this: $c[i,j]$ represents the size of the maximal "uncut match" such that the participated vertices from $U$ are from $1,\ldots, i$ (and same idea $j$).
We want to find $c[n,n]$.
Also, the smallest problems are: $c[1,j] = 1$ and $c[i, 1] = 1$.
- I'd be glad if you could help me define the recurrence function/
- Also, the recurrence as it is right now only finds the size of the match but not the match itself. How can I combine that information?
If you remove the "uncut" constraint, there are a few algorithms to find a maximal matching, for example the Hopcroft–Karp algorithm. After you have a maximal matching, you can make it uncut by removing cuts one by one. This might be a good algorithm for this problem.
On the other hand, Dynamic programming should work in this problem. Your idea seems fine, except that you can not say $c[1, i]=1$ etc. unless you have an edge between $1$ and $i$. What you have is: $$c[i+1, j+1] = max(c[i, j+1], c[i+1, j], c[i, j] + e(i+1, j+1)), $$ where $e(i+1, j+1)=1$ if there is an edge between them, otherwise $0$. A good addition is add a link from $c[i+1, j+1]$ to the one that make the maximum happen (for example, if $c[i+1, j+1]=c[i,j]+1$, then point to $(i,j)$). This will help find the maximal matching later.
Then $c[n, n]$ is the maximal matching number, but you still need to come back to the $c[i,j]$'s to find a matching.