The Vertex Cover Problem

• Download source code - 54.3 KB

Introduction

This project discusses different techniques and algorithms used to solve the parameterized Vertex Cover problem. A vertex cover of a graph G(V,E) is a subset of vertices V such that for every edge (u, v) ⊆ E, at least one of the vertices u or v is in the vertex cover. The best algorithm for this problem is known to run at O(1.2852k + kn). The optimal solution is intractable, thus optimization strategies in solving the vertex cover problem are brought off-the-shelves, including pre-processing, kernelization, and branching methodologies. A performance bound is considered for approximation algorithms listed in this research.

Background

Vertex cover problem is a Fixed Parameter Tractable (FPT) problem, where an input k, usually an integer in our case, can be used to minimize the computational density of a problem x. For example, if we have a table with n records and a query of size k, then finding objects in the table that suit the query k can be done in time O(n k). When parameter k is small, this solution can be feasible. Sometimes, it is possible to write a O(n 2 k) algorithm for special tasks; this will also be feasible when the parameter is small. Moreover, a problem with a parameter k is called Fixed Parameter Tractable (FPT) if it can be solved or decided by an algorithm within a running time O(f(k).poly(n)), for some function f. That was the basic approach of Robert Downey and Michael Fellows; they took into consideration the Vertex Cover problem as follows:

Case: An undirected graph G = (V,E) and a positive integer k.

Question: Does G have a vertex cover of size at most k? (Where vertex cover is a set of vertices V’ ∈ V such that, for every edge uv ∈ E, either vertex u or v ∈ V’).

A very easy analogy can be seen in case you have a floor with lots of corridors and paths, and you want to find the minimum number of cameras to watch over all the paths. In addition to this very simple example, a vertex cover is widely implemented in the bioinformatics field and other biochemical related issues. We are interested in finding a minimum set of vertices that will cover all the edges in a graph. Many approximation algorithms have been written to produce a vertex cover twice the optimal one. An algorithm that returns an answer C (any vertex cover) which is close or near the optimal solution C* (minimum vertex cover in a graph) is called an approximation algorithm. Closeness is usually measured by the ratio bound ρ(n) the algorithm produces, which is in turn a function that satisfies, for any input size n, 1 ≤ max{C/C*,C*/C} ≤ ρ(n). A 1-approximation algorithm is optimal, and the larger the ratio, the worse the solution.

Using the code

A solution for the Vertex Cover problem is decomposition and search. It consists of decomposing the problem and searching for the vertex cover. We use a tree structure where each node represents a choice. The user should know the expected cover, and the algorithm checks if this cover is possible with any combination. The algorithm applies a depth first search to find the cover. The algorithm begins with the vertex with the highest degree, and then, each left leaf represents the cover with the selected vertex and the vertices with the next highest degree. The right child represents the cover that does not contain the left child, rather its neighbors.

bool edgeInCover = false;
int conditionViolated = 0;

for(int i=0;i<dimension;i++)
{
    for(int j=0;j<dimension;j++)
    {
        if(edges[i,j] == true)
        {
            edgeInCover = false;
            for(int v=0;v<cover.Length;v++)
            {
                if((cover[v] == i) || (cover[v] == j))
                {
                    edgeInCover = true;
                    break;
                }
            }
            if(edgeInCover == false)
            {
                conditionViolated = 3;
                break;
            }
        }//if there is a connection between i and j
    }
}

How to use the code

The program reads a graph from an adjacency list stored in an Access database, and it also reads the constant k from a variable in the same database. The program is deployed using Microsoft Visual Studio .NET and C#. The computer used in constructing the code has a processor of 850 MHZ and 256 MB physical memory, the virtual memory is 512 MB. We have defined the following static variables:

• Edges: A two dimensional array representing the adjacency matrix of the vertices in the graph.
• Dimension: Contains the dimensions of the 2D array, which is the number of vertices.
• CoverToFind: the cover that we want to find.

The argument “cover” in FindCover() denotes the one dimensional array that contains the vertices that are present in the cover. We then connect to the database to get the adjacency matrix and the cover, and then we close the connection and store the adjacency matrix in “edges”. When the user clicks on “Find Cover”, the function FindCover() is called with the following arguments:

• An empty 1-dimensional array that denotes the vertices in the cover. It is empty because in the first call, we have no cover.
• An integer that denotes the number of nodes that we should add to the cover to obtain the desired cover.

First of all, the function checks if k is zero. If it is the case, this means that we have reached the limit in our vertex cover, and now we must check if the selected nodes cover all the edges in the graph. The code first checks if the entry in the adjacency matrix is true, which means that there is a connection between the nodes. It then checks if any of the two nodes is in the cover; if it is, then the edge is covered. If both nodes are not present in the cover, then the edge is not covered, and the solution that we get does not cover all the edges. The first part of the code finds a node that is not in the cover, because the node that has the highest degree should not be in the cover. Then, we search for a true value in the vertex cover. If both nodes are not in the cover, then we increment the degree of this node by 1. We take max to be the node with the highest degree. We now recursively call findCover(cover,K), with cover being the old cover + the node with the highest degree, and k = old k – 1. Now, we have to find the neighbors of this node to add to the cover and call findCover(cover, k), where cover = old cover + neighbors of the node that have the highest degree, and k = old k – number of neighbors of the node with the highest degree.

{
    inCover = true;
    while((inCover == true) && i<dimension)
    {
        inCover = false;
        for(int v=0;v<cover.Length;v++)
        {
            if(i == cover[v])
            {
                inCover = true;
                i++;
                break;
            }
        }
    }// end while

    if(i>=dimension) break;
    if(inCover == true) break;

    for(int j=0;j<dimension;j++)
    {
        if(edges[i,j] == true)
        {
            neighborInCover = false;
            for(int v=0;v<cover.Length;v++)
            {
                if((i == cover[v]) || (j == cover[v]))
                {
                    neighborInCover = true;
                    break;
                }
            }
            if(neighborInCover == false)
                count++;
        }
    }

    if (count>max)
    {
        max = count;
        nodeIndex = i;//nodeIndex is highest degree
    }
    count = 0;
}//end for