1
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.