Assignment 3

Type: Individual Assignment
Due: before class on Wednesday, December 8, 2021

Prologue

Suppose your boss asks you to find a fast solution to the maximum_clique problem. Ultimately, she wants you to write a function that matches the following specification:

def maximum_clique(G, k):
    """Checks if the graph G contains a clique of size >= k
    
    Parameters:
        G, a undirected graph (adjacency matrix)
        k, a non-negative integer
        
    Returns:
        True   if G has a clique of size >= k
        False  otherwise"""

The graph G is represented as an adjacency list, so it looks something like the following:

G = [[0, 1, 1],
     [1, 0, 0],
     [1, 0, 0]]

After hours of writing code, the best solution you’ve been able to find is a brute force one that iterates over all possible groups of vertices and checks if they are a clique:

from itertools import combinations

def maximum_clique(G, k):
    # For each subset of vertices with size k...
    for C in combinations(range(len(G)), k):
        # If every pair of vertices, (u,v), is connected...
        if all(G[u][v] == 1 for u, v in combinations(C, 2)):
            # Then it is a clique!
            return True

    # If we get here, no k vertices forms a clique
    return False

Since the number of combinations $n \choose k$ is exponential, your boss isn’t very happy with your algorithm. She wants you to show that the maximum_clique problem is $\text{NP}$-complete before you give up on a polynomial time solution.

NOTE: Before you get started on the two parts of the assignment below, you should first download the starter code linked below.

Part 1: Reducing from Independent Set

You recall that the independent_set problem is related to the maximum_clique problem, so you set out to show that maximum_clique is at least as hard as independent_set. To do so, you need to reduce independent_set to maximum_clique; in other words, you need to solve independent_set using maximum_clique.

For this part of the assignment, you need to finish implementing the following function:

def independent_set(G, k):
    """Checks if G contains an independent set of size >= k
    
    Parameters:
        G, a undirected graph (adjacency matrix)
        k, a non-negative integer
        
    Returns:
        True   if G has an independent set of size >= k
        False  otherwise"""
    # IMPLEMENT ME!

NOTE: You must implement independent_set using maximum_clique. Furthermore, your reduction to maximum_clique must take polynomial time.

Part 2: Reducing from Vertex Cover

After you show your reduction from independent_set to maximum_clique, your boss is still unconvinced because she is unsure that independent_set is a hard problem. However, she knows for certain that the vertex_cover problem is $\text{NP}$-complete because she knows of the following reductions:

\[(\text{every NP problem})\rightarrow \text{SAT} \rightarrow \text{3SAT} \rightarrow \text{VERTEX_COVER}\]

Thus, she also wants you to demonstrate that independent_set is a hard problem by doing a reduction from vertex_cover.

For this part of the assignment, you need to finish implementing the following function:

def vertex_cover(G, k):
    """Checks if G contains a vertex cover of size <= k
    
    Parameters:
        G, a undirected graph (adjacency matrix)
        k, a non-negative integer
        
    Returns:
        True   if G has a vertex cover of size <= k
        False  otherwise"""
    # IMPLEMENT ME!

NOTE: You must implement vertex_cover using independent_set. Furthermore, your reduction to independent_set must take polynomial time.

Starter Code

You should write your solutions in the following Python file and upload them to Gradescope when you are finished:

• reductions.py