Constrained Bipartite Matching

Let $$G = (X,Y,E)$$ be a bipartite graph. For some $$A \subseteq X$$ we say that $$A$$ can be perfectly matched if there is a matching $$M \subseteq E$$ such that all vertices in $$A$$ are matched; that is, for every $$a \in A$$ there is $$e \in M$$ such that $$a$$ is an endpoint of $$e$$. Let $$\mathcal{M}$$ be all subsets $$A \subseteq X$$ that can be perfectly matched. We can decide in polynomial time if some $$A \subseteq X$$ belongs to $$\mathcal{M}$$ using maximum matching (while removing the vertices $$X \setminus A$$ from the graph).

In addition, let $$\Pi \subseteq 2^X$$ be some downward monotone constraint satisfying that there is a polynomial time algorithm that given $$B \subseteq X$$ decides if $$B \in \Pi$$. The above constraints $$\mathcal{M}$$ and $$\Pi$$ are decidable in polynomial time; however, I wonder if we can decide if a partition of $$X$$ into a set in $$\mathcal{M}$$ and a set in $$\Pi$$ can be NP-Hard. Namely,

Question: Are there examples for $$\Pi$$ such that it is NP-Hard to find a partition $$A,B$$ of $$X$$ such that $$A \in \mathcal{M}$$ and $$B \in \Pi$$?

• By using the bipartite graph, we can encode a constraint saying $|A| \le k$, for a number $k$. Therefore, an example of an NP-hard case is if we have another graph $H$ with the vertex set $X$, and $\Pi$ is the family of independent sets of $H$. In particular, this encodes the maximum independent set problem. Commented Apr 23 at 13:47
• I am not sure this is good enough: the independent set problem is NP-Hard and we want $\Pi$ to be solvable in polynomial time.
– John
Commented Apr 24 at 9:09
• Deciding whether a vertex set is an independent set is not NP-hard though. So $B \in \Pi$ can be decided in polynomial time. Commented Apr 24 at 9:15

1 Answer

This problem captures the maximum independent set problem, which is NP-hard, as follows.

Suppose we wish to decide if a graph $$H = (V_H, E_H)$$ has an independent set of size $$\ge k$$.

We construct $$G = (X,Y,E)$$ so that $$X = V_H$$, $$Y$$ is a set of size $$|V_H|-k$$, and $$E$$ contains all possible edges between $$X$$ and $$Y$$. Now for $$A \subseteq X$$, we have $$A \in \mathcal{M} \Leftrightarrow |A| \le |V_H|-k$$.

We let $$\Pi$$ consist of all subsets of $$V_H$$ that are independent sets in $$H$$. The set $$\Pi$$ is downwards-closed, and whether $$B \in \Pi$$ can clearly be decided in polynomial time.

Now there exists a partition $$A,B$$ of $$X$$ so that $$A \in \mathcal{M}$$ and $$B \in \Pi$$ if and only if $$H$$ has an independent set of size $$\ge k$$.