These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.We prove that n/2-clique is NP-Complete in two steps, as the lecture shows.
1). n/2-clique is in NP class
2). n/2-clique is in NP-Hard
For the step 1), we make a “guess” of a sequence of vertices for a graph provided as input and we verify whether the size of the sequence is n/2 and whether there is a clique determined by these n/2 vertices. Since each of these can be done in polynomial time (assuming that n is finite, then n/2 is also finite and gives the input size since the number of edges in this case is (n/2)*(n/2 -1)), it follows that our problem is in NP.
For step 2), we need to build a reduction in polynomial time from another known NP-Complete problem. We use n/3-clique problem in this case....
By purchasing this solution you'll be able to access the following files: