Maximum matching with social distancing

Let $$G = (X\cup Y, E)$$ be a bipartite graph. Suppose $$X$$ contains people, $$Y$$ contains seats in a theatre, and each edge $$(x,y)$$ has a weight representing how much person $$x$$ is willing to pay for seat $$y$$. The goal is to find a maximum-weight matching (to maximize the total profit).

But now there are social distancing constraints: if some seat $$y_k$$ is matched, then seats $$y_{k+1}$$ and $$y_{k-1}$$ must remain unmatched. Is there a polynomial-time algorithm for finding a maximum-weight matching?

WHAT I TRIED

1. In the special case in which $$|Y|=2|X|-1$$ and we also require the matching to also have maximum cardinality, we must match only the odd-indexed vertices of $$Y$$, so the problem reduces to simple maximum-weight matching. But I am interested in maximum weight matching, and in the general case in which $$|Y|$$ may be arbitrary.

2. Suppose all weights are 0 or 1. Without social distancing, the graph can be converted into a flow-network by adding a source node before $$X$$, adding a sink node after $$Y$$, and making the capacity of all edges equal to 1. Then, an integral flow corresponds to a matching. But I do not see how to convert the social distancing constraints to flow constraints.

3. A common technique for finding a maximum-cardinality mathcing is to iteratively apply augmenting paths. But here, an augmenting path might break the distance constraint.

4. Another common technique is to solve a linear program with a variable $$z_{x,y}$$ for each pair $$x\in X, y\in Y$$. Without distance constraints, the problem is to maximize $$\sum_{x\in X, y\in Y} w_{x,y} z_{x,y}$$ subject to the following constraints:

• $$\sum_{y \in Y} z_{x,y} \leq 1$$ for all $$x \in X$$
• $$\sum_{x \in X} z_{x,y} \leq 1$$ for all $$y \in Y$$
• $$0 \leq z_{x,y}\leq 1$$ for all $$x \in X$$ and $$y \in Y$$

The constraint matrix is known to be totally-unimodular, so an integer solution exists. But With gaps, we have to replace the second set of constraints with:

• $$\sum_{x \in X} [z_{x,y} + z_{x,y+1}] \leq 1$$ for all $$y \in Y$$

and I do not know whether the resulting matrix is totally-unimodular.