Design and Analysis Max Cpques

In an undirected graph, a cpque is a complete sub-graph of the given graph. Complete sub-graph means, all the vertices of this sub-graph is connected to all other vertices of this sub-graph.

The Max-Cpque problem is the computational problem of finding maximum cpque of the graph. Max cpque is used in many real-world problems.

Let us consider a social networking apppcation, where vertices represent people’s profile and the edges represent mutual acquaintance in a graph. In this graph, a cpque represents a subset of people who all know each other.

To find a maximum cpque, one can systematically inspect all subsets, but this sort of brute-force search is too time-consuming for networks comprising more than a few dozen vertices.

Max-Cpque Algorithm

The algorithm to find the maximum cpque of a graph is relatively simple. The steps to the procedure are given below −

Step 1: Take a graph as an input to the algorithm with a non-empty set of vertices and edges.

Step 2: Create an output set and add the edges into it if they form a cpque of the graph.

Step 3: Repeat Step 2 iteratively until all the vertices of the graph are checked, and the pst does not form a cpque further.

Step 4: Then the output set is backtracked to check which cpque has the maximum edges in it.

Pseudocode

Algorithm: Max-Cpque (G, n, k)
S := ф
for i = 1 to k do
   t := choice (1…n) 
   if t є S then
      return failure
   S := S U t 
for all pairs (i, j) such that i є S and j є S and i ≠ j do
   if (i, j) is not a edge of the graph then 
      return failure
return success

Analysis

Max-Cpque problem is a non-deterministic algorithm. In this algorithm, first we try to determine a set of k distinct vertices and then we try to test whether these vertices form a complete graph.

There is no polynomial time deterministic algorithm to solve this problem. This problem is NP-Complete.

Example

Take a look at the following graph. Here, the sub-graph containing vertices 2, 3, 4 and 6 forms a complete graph. Hence, this sub-graph is a cpque. As this is the maximum complete sub-graph of the provided graph, it’s a 4-Cpque.