# Is this graph theory/set theory problem NP-complete?

I'm working on the following problem. Let $G=(V,E)$ be a directed graph. A robber is in the graph and a policeman tries to catch him. Every day the policeman can check if the robber is in one of the $k$ vertexes of the graph. Every night the robber moves along one of the edges. I'm trying to prove that finding the smallest $k$ such that the policeman has a strategy to always catch the robber is NP-complete.

My proof strategy is to first prove that finding the smallest $k$ such that the policeman can catch the robber in 2 days is NP-complete because it is very similar to some known NP-complete problems such as vertex cover or dominant set. Then, I believe that for every graph $G$ I will be able to construct a graph $H$ such that the policeman can catch the robber in $H$ iff he can catch him in $G$ in 2 or less days.

My question is for the 2 day version. Written in the language of set theory:

Let $|S|=n\in \mathbb{N}$ and let there be $n$ subsets of $S$. What is the smallest $k$ such that there exist $n-k$ of those subsets so that their union has at most $k$ elements? How to prove that finding such $k$ is NP-complete?

• Not sure I get what your question is. Can you clarify and perhaps add some thoughts of your own on the problem? – Joffan Dec 23 '17 at 15:08
• I have answered your 2-day subproblem in cs.SE: https://cs.stackexchange.com/a/96944/92914 – user575478 Sep 4 '18 at 11:52