<p>This problem captures the maximum independent set problem, which is NP-hard, as follows.</p>
<p>Suppose we wish to decide if a graph <span class="math-container">$H = (V_H, E_H)$</span> has an independent set of size <span class="math-container">$\ge k$</span>.</p>
<p>We construct <span class="math-container">$G = (X,Y,E)$</span> so that <span class="math-container">$X = V_H$</span>, <span class="math-container">$Y$</span> is a set of size <span class="math-container">$|V_H|-k$</span>, and <span class="math-container">$E$</span> contains all possible edges between <span class="math-container">$X$</span> and <span class="math-container">$Y$</span>. Now for <span class="math-container">$A \subseteq X$</span>, we have <span class="math-container">$A \in \mathcal{M} \Leftrightarrow |A| \le |V_H|-k$</span>.</p>
<p>We let <span class="math-container">$\Pi$</span> consist of all subsets of <span class="math-container">$V_H$</span> that are independent sets in <span class="math-container">$H$</span>. The set <span class="math-container">$\Pi$</span> is downwards-closed, and whether <span class="math-container">$B \in \Pi$</span> can clearly be decided in polynomial time.</p>
<p>Now there exists a partition <span class="math-container">$A,B$</span> of <span class="math-container">$X$</span> so that <span class="math-container">$A \in \mathcal{M}$</span> and <span class="math-container">$B \in \Pi$</span> if and only if <span class="math-container">$H$</span> has an independent set of size <span class="math-container">$\ge k$</span>.</p>

CC BY-SA 4.0
2024-04-26T12:42:52.913Z
2024-04-26T12:42:52.913Z
Laakeri
<p>Let <span class="math-container">$G = (X,Y,E)$</span> be a bipartite graph. For some <span class="math-container">$A \subseteq X$</span> we say that <span class="math-container">$A$</span> can be <em>perfectly matched</em> if there is a matching <span class="math-container">$M \subseteq E$</span> such that all vertices in <span class="math-container">$A$</span> are matched; that is, for every <span class="math-container">$a \in A$</span> there is <span class="math-container">$e \in M$</span> such that <span class="math-container">$a$</span> is an endpoint of <span class="math-container">$e$</span>. Let <span class="math-container">$\mathcal{M}$</span> be all subsets <span class="math-container">$A \subseteq X$</span> that can be perfectly matched. We can decide in polynomial time if some <span class="math-container">$A \subseteq X$</span> belongs to <span class="math-container">$\mathcal{M}$</span> using maximum matching (while removing the vertices <span class="math-container">$X \setminus A$</span> from the graph).</p>
<p>In addition, let <span class="math-container">$\Pi \subseteq 2^X$</span> be some downward monotone constraint satisfying that there is a polynomial time algorithm that given <span class="math-container">$B \subseteq X$</span> decides if <span class="math-container">$B \in \Pi$</span>. The above constraints <span class="math-container">$\mathcal{M}$</span> and <span class="math-container">$\Pi$</span> are decidable in polynomial time; however, I wonder if we can decide if a partition of <span class="math-container">$X$</span> into a set in <span class="math-container">$\mathcal{M}$</span> and a set in <span class="math-container">$\Pi$</span> can be NP-Hard. Namely,</p>
<p><strong>Question:</strong> Are there examples for <span class="math-container">$\Pi$</span> such that it is NP-Hard to find a partition <span class="math-container">$A,B$</span> of <span class="math-container">$X$</span> such that <span class="math-container">$A \in \mathcal{M}$</span> and <span class="math-container">$B \in \Pi$</span>?</p>

CC BY-SA 4.0
2024-04-23T13:47:10.540Z
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.
Laakeri
CC BY-SA 4.0
2024-04-24T09:09:02.320Z
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
CC BY-SA 4.0
2024-04-24T09:15:06.830Z
Deciding whether a vertex set is an independent set is not NP-hard though. So $B \in \Pi$ can be decided in polynomial time.
badboul
<np-hardness><np-complete><matching><partition-problem><bipartite-graphs>
Constrained Bipartite Matching
John
# Constrained Bipartite Matching

(Asked by: username_0 on 2024-04-23)

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$?

**Tags:** np-hardness, np-complete, matching, partition-problem, bipartite-graphs

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: Deciding whether a vertex set is an independent set is not NP-hard though. So $B \in \Pi$ can be decided in polynomial time.  

---

## 1 answers

### Answer by username_1 on 2024-04-26. Score: 2

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$.


---

