2. A stable set is a set of nodes U CV such that there are no...

Transcribed Image Text:

2. A stable set is a set of nodes U CV such that there are no edges between any two nodes of U. A clique is a set of nodes U CV such that there is an edge between every pair of nodes in U. Show that the problem of finding a maximum cardinality stable set is dual to the problem of finding a minimum cover of the edges by cliques. Use this observation to find bounds on the maximum size of a stable set in the graph shown in Figure 2.5. 74 35 " 14 (13) 2 Fig. 2.5 Stable set instance 4 E 2. A stable set is a set of nodes U CV such that there are no edges between any two nodes of U. A clique is a set of nodes U CV such that there is an edge between every pair of nodes in U. Show that the problem of finding a maximum cardinality stable set is dual to the problem of finding a minimum cover of the edges by cliques. Use this observation to find bounds on the maximum size of a stable set in the graph shown in Figure 2.5. 74 35 " 14 (13) 2 Fig. 2.5 Stable set instance 4 E