﻿ Maximum Independent Set Problem

 Student: Sarah Bleiler School: Seton Hall University, Mathematics and Computer Science Dept. Email: bleilesa@dimax.rutgers.edu Research Area(s): Graph Theory Project Name: Applications of the Maximum Independent Set Problem Faculty Advisor: Dr. Vadim Lozin, RUTCOR, Rutgers University Center for Operations Research

### Project Description

My project this summer considers a famous problem in Graph Theory known as the Maximum Independent Set (MIS) problem. Two sets are independent, or disjoint, if their intersection is empty. Consequently, a set of vertices of a graph is an independent set if no two vertices in the set are connected by an edge. A bipartite graph, for example, will always have two independent sets of vertices.

The MIS problem is essentially finding an independent set of a graph G which contains the most possible vertices. The number of vertices in this set is known as the independence number, denoted α (G). In general, the MIS problem is NP-complete. However, there are specific classes of graphs for which the problem can be solved in polynomial time. For all others, it is important to find techniques and algorithms which can efficiently approximate the independence number.

Currently, I am investigating the real-life applications of the Maximum Independent Set problem. The problem is known to have many uses in areas of computer vision, pattern recognition, and information/coding theory. I will be researching its applications in these areas as well as trying to find and explore further practical applications.

My initial powerpoint presentation presented to the REU students on 06-23-05

There were many interesting applications of graph independence that I discovered. Some of these include map labeling, shape matching using shock graphs, and possible relations to fullerene stability in biological applications.

After the first few weeks of the REU we decided to focus our time on more of a research type problem which is described briefly in the above noted powerpoint presentation. The problem essentially asked to solve the MIS problem for graphs with a forbidden induced subgraph. In our case we wanted to solve the problem for the class of graphs which are planar and which forbid an induced S1,2,2 subgraph.

Here I will link most of the work that I did throughout the summer related to this problem. In my second powerpoint presentation there is a more thourough explanation of the problem and its subparts. Each of the attached word documents demonstrate research/brainstorming that I have done. I do not claim these to be solid proofs of the matter at hand:

My final powerpoint presentation presented to the REU students on 07-20-05

June 27, 2005

June 27, 2005

June 28, 2005

June 29, 2005

June 29, 2005

July 03, 2005

July 03, 2005

July 05, 2005

July 05, 2005

July 05, 2005

July 14, 2005