| Given a graph G = (V, E), a vertex cover in G is a subset...

Transcribed Image Text:

| Given a graph G = (V, E), a vertex cover in G is a subset V'≤V such that for all (u,w) € E, u € V' or w € whin V'. 1 3 Figure 1 5 Figure 1 shows an undirected graph including 6 nodes. Answer the questions below: 1. Does Figure 1 have a vertex cover including four nodes? If so, given an example of 4-node vertex cover? 2. Does Figure 1 have a vertex cover including three nodes? If so, given an example of 3-node vertex cover? 3. What is the minimum vertex cover (including least nodes) in Figure 1? 4. Let VC = {<<G, k> | G has a VC of size <k}. Is this problem a NP problem? Prove your conclusion. 5. Is VC a NP-complete problem? Why? | Given a graph G = (V, E), a vertex cover in G is a subset V'≤V such that for all (u,w) € E, u € V' or w € whin V'. 1 3 Figure 1 5 Figure 1 shows an undirected graph including 6 nodes. Answer the questions below: 1. Does Figure 1 have a vertex cover including four nodes? If so, given an example of 4-node vertex cover? 2. Does Figure 1 have a vertex cover including three nodes? If so, given an example of 3-node vertex cover? 3. What is the minimum vertex cover (including least nodes) in Figure 1? 4. Let VC = {<<G, k> | G has a VC of size <k}. Is this problem a NP problem? Prove your conclusion. 5. Is VC a NP-complete problem? Why?

Answer rating: 100% (QA)

determining whether a of a given size k for a graph Solution verter cover problem i... View the full answer