2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Laakeri
    Commented Apr 23 at 13:47
  • $\begingroup$ 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. $\endgroup$
    – John
    Commented Apr 24 at 9:09
  • 2
    $\begingroup$ Deciding whether a vertex set is an independent set is not NP-hard though. So $B \in \Pi$ can be decided in polynomial time. $\endgroup$
    – badboul
    Commented Apr 24 at 9:15

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.