是的，這是一個 NP 的問題。意思也就是說，如果告訴你哪幾間房間是準備室的話，檢查這樣有無符合限制僅需要 P 的時間。(先檢查每條邊是否至少有一的頂點是準備室，檢查的時候順便將另外一個頂點標記，然後再檢查所有的頂點是不是都有標記或是自己就是準備室, n + m)
先看簡單一點的，如果整能有一間準備室。 那麼隨便挑一個邊，這個邊的兩邊至少有一個頂點得要是準備室。那先試試看把其中一個頂點當準備室，這樣合不合法，不行的話再把另外一個頂點當準備室看看合不合法。如果兩個放法都不行，這圖鐵定無解。
那麼如果可以擺放兩間準備室呢？隨便挑兩個沒有重疊到的邊 (v1, v2), (v3, v4) ，v1 ~ v4 都不相等，分別嘗試 [v1, v3], [v1, v4], [v2, v3], [v2, v4] 當準備室，如果這四種方法都不行，那這圖肯定無法解。
不管你取出哪兩條邊，只要這兩條邊的四個頂點都不相等，就可以得出這樣的推論。
我想嘗試說明的是，如果你能找出 8 的地方讓你選擇，每個地方必須保證一定會有一個準備室，那麼當你在這 8 個地方爆搜完後發覺還是無解的時候，你就可以肯定這絕對無解。那麼可能會花 2^8 (n + m) = 256(n + m) 。
實際上做的時候到也不用這麼麻煩 :)