Circular graph common inner nodes, in NP

user_17091567 0
Viewed 64

I am having a hard time figuring out this problem.

The problem is: We have a circular undirected graph G. We start at some node, and then take circular paths throughout the graph to arrive back at the starting node. We want to know if there is some list of k nodes inside the graph that must always be taken for every path in the graph. The problem is pretty much, do these k nodes exist?

I need to prove that this problem is in NP. However, not too sure how to do this.

To prove it's in NP, I need to be able to verify the solution. However, I'm not even sure how to start with the problem itself as I haven't seen something similar to this before. Could anyone lend some advice? Does anyone know an equivalent problem to this that could help with the verification?

enter image description here

For example, for starting node s, we always need to traverse b. So the set k = {b}

Input: Undirected graph G = (V, E), integer k. Question: Is there a set S of k vertices such that every cycle in the graph includes at least one vertex of S?

A verifier algorithm can't simply take a set S of k nodes and enumerate every cycle in the graph to check if it contains at least one vertex in S. There may be exponentially many cycles in the graph, and the verifier algorithm needs to run in polynomial time. It needs to be smarter than this.

np graph-theory complexity-theory algorithm
1 Answers

To verify a problem is in NP (Not NPC), you need to get the input of the problem, and a polynomial size verification input - and using it, determine if the answer to the decision problem of the original input is true or false, in Polynomial time (This is equivalent definition to using Non-deterministic turing machine).

  • In your case, the input to the problem is G=(V,E), and some integer k.
  • The verifying string will be a set S with the candidate set of nodes.

Now, given these inputs - first check |S| = k, and then create G' = (V', E'), where:

V' = V\S
E' = { (u,v) | (u,v) in E and u in V' and v in V' }

Now, do a DFS form each of the nodes in V'. DFS takes polynomial time, and you need to do it polynomial number of times - so still polynomial time complexity. You are searching if there is a cycle in V' (reaching the same node you started from).

  • If you find such, the answer to the problem is true (there is such set of size k).
  • Otherwise, it's false (there isn't such set).
user_5726700
Related