Problem 4 (20 points) The flag of a certain populous country contains a symbol c

Question

Problem 4 (20 points) The flag of a certain populous country contains a symbol called the "Ashoka Chakra (see the image below). This symbol has a central hub and 24 spokes. Naturally, this reminds us of a graph with 25 nodes and 48 edges, of which 24 nodes are connected by a cycle, and the 25th node is connected to each of the other 24 nodes. A generalised k-chakra is a graph with k 1 nodes and 2k edges such that k nodes lie on a cycle and the k 1st node is connected to each of the other k nodes. Given an undirected graph G and an integer k, prove that the problem of determining if G contains a generalised k-chakra as a subgraph is omplete. (We say that a graph H is a subgraph of a graph G if every node in H is also a node in G and every edge in H is also an edge in G.) I will get you started on the solution. Proving that k-chakra is in NP is easy. A certificate is just a candidate k-chakra. The certifier checks that this chakra contains k 1 nodes and 2k nodes in the right configuration. The certificate takes O(k) time to run Let us move on to proving that some NP-Complete problem is reducible to the k chakra problem. Suppose G has ne 1 nodes. Let us consider the special case that k n. An n-chakra looks suspiciously like a Hamiltonian cycle, except that the chakra has more e Let us reduce Hamiltonian cycle in dges. undirected graphs (which we know to be Complete) to the k-chakra problem. Suppose H is an undirected graph that is an input to the Hamiltonian cycle problem. We want to convert it to a graph G that will be input to the k-chakra problem such that H contains a Hamiltonian cycle iff G contains a n-chakra. To complete the reduction, answer the following three questions: (a) (5 points) Describe how you will convert an arbitrary undirected graph H that is input to the Hamiltonian cycle problem into an undirected graph G that is an input for the chakra problem. (b) (5 points) If H contains a Hamiltonian cycle, prove that G contains a n-chakra. (c) (10 points) If G contains a n-chakra, prove that H contains a Hamiltonian cycle. Note: there is a subtlety here that you have to be careful about

Explanation / Answer

(a) The conversion from H to G goes like this :

We will add an additional n+1th vertex to H and add edges from this n+1th vertext to all other vertices in H, this becomes our G.

(b) if H contains a Hamiltonian cycle then all the n vertices in G are connected by a cycle and by above conversion there is an edge from n+1th vertex to every other vertex. So G contains a n-chakra.

(c) If G contains a n-chakra, there are 2 cases :

case 1) if n+1th vertex is the center of chakra then we are done as the other n vertices are connected by cycle and the edges of these cycle are from H only, since the additional edges added in G are from n+1th to other vertces.

So H coNTANS hAMILTONIAN CYCLE.

case 2) If some vertex in H is the center of the chakra and n+1th vertex is part of the cycle.

Here aslo we can find a cycle of all the n vertices in H, This cycle contains the n-1 vertices from H in the n-chakra cycle and the end vertices connecting to the center vertex by the spokes of the n-chakra. Here also the edges of these cycle are from H only, since the additional edges added in G are from n+1th to other vertces. So H contains Hamiltonian cycle.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.