# The Maximum Independent Set Problem For Cubic Planar Graphs

Original Publication Date: 1985-Aug-31

Included in the Prior Art Database: 2007-Mar-30

## Publishing Venue

Software Patent Institute

## Related People

Burns, James E.: AUTHOR [+2]

## Abstract

by James E. Bum Computer Science Department Indiana University Bloomington, IN 47405 by TECHJSlICAL REPORT NO. 177 The Maximum Independent Set Problem For Cubic Planar Graphs James E, Burns August, 1985 THE MAXIMUM INDEPENDENT SET PROBLEM FOR CUBIC PLANAR GRAPHS James E. Burns June 1985 A maximum independent set of a graph is a set of verticm with maximum cardinal- ity such that no pair of vertices is connected by an edge. Choukhmane and b c o have presented a polynomial time approximation algorithm for the maximum inde- pendent set problem in cubic planar graphs. If M ia taken as the ratio of the sise of the independent set produced by their algorithm to the siee of a mdmum inde- pendent set of the input graph, then they show that their algorithm gives M 2 617 for any cubic planar graph and M 2 7/8 for a triangle-free cubic planar graph. We show that their algorithm gives M 2 7/8 for all cubic planar graphs. 1. INTRODUCTION The maximum independent set problem, defined formally in the next section, is a problem of wide interest. Unfortunately, it is known to be an NP-complete problem, so there is little hope for an algorithm which can compute an exact solution in polynomial time. (For a comprehensive treatment of NP-complete problems, see Garey and Johnsoni7].) It is therefore useful to consider solutions which are approximate, but can be computed efficiently.

**This text was extracted from a PDF file.**

**At least one non-text object (such as an image or picture) has been suppressed.**

**This is the abbreviated version, containing approximately 24% of the total text.**

__Page 1 of 7__**The ****Maximum ****Independent ****Set ****Problem ****For ****Cubic ****Planar ****Graphs **

**by**

**James**

**E.**

**Bum**

**Computer**

**Science**

**Department**

**Indiana University**

**Bloomington,**

**IN**

**47405**

**TECHJSlICAL ****REPORT ****NO. ****177 **

**The ****Maximum Independent ****Set ****Problem ****For ****Cubic ****Planar ****Graphs **

**by **

**James ****E, ****Burns ****August, ****1985 **

__[This page contains 1 picture or other non-text object]__

__Page 2 of 7__**THE ****MAXIMUM INDEPENDENT SET PROBLEM FOR ****CUBIC ****PLANAR GRAPHS **

**James ****E. ****Burns **

June 1985

**ABSTRACT' **

A maximum independent set of a graph is a set of verticm with maximum cardinal- ity such that no pair of vertices is connected by **an **edge. Choukhmane and b c o have presented a polynomial time approximation algorithm for the maximum inde- pendent set problem in cubic planar graphs. If ** M **ia taken as the ratio of the sise of the independent set produced by their algorithm to the siee of a mdmum inde- pendent set of the input graph, then they show that their algorithm gives

*M*

*2***for any cubic planar graph and M**

*617**2*7/8 for a triangle-free cubic planar graph. We show that their algorithm gives

*M**2*7/8 for

**all**cubic planar graphs.

**1. ****INTRODUCTION **

The maximum independent set problem, defined formally in the next section, is a problem of **wide **interest. Unfortunately, it is known to be an NP-complete problem, so there is little hope for an algorithm which can compute an exact solution in polynomial time. (For a comprehensive treatment of NP-complete problems, see Garey and Johnsoni7].) It is therefore useful to consider solutions which are approximate, but can be computed efficiently.

For any algorithm W which produces an independent set I for some input graph

G, let *Mw(G) *

be the ratio of the sire of I to the **sise **of a maximum independent set of G. For any clasa of **graph ****5, **let **Adw($) **be! the minimum value of ** Mw(@) **over

**all**G

*E***5.**We define

**= {planar graphs), = (cubic planar graphs), and**

*QP***= {cubic triangle-free planar graphs). Lipton**

*$3TFP***and**%&rjan[lO]

give

**an**

**O(n **log **n) **time algorithm, L, which **is **shown to give an approximation **euch **that

*M'(gp) ***> **(1 **- **O ( l / 4 i j ) , where **n ****t **the number of verticea in the input graph. Unfortunately, **aa ****&own **by **Chiba ***et *** d[2], **n must be rather

**large**before

*ML(gP) *

**> **1/2. Chiba **et **** d **then describe an algorithm,

**which**

*C,***executes**

**in**Author's addresses:

**J.E.**Burns, Computer Science Department, 101 Lindley

**Hall, **Indiana University, Bloomington, Indiana 47405.

__[This page contains 1 picture or other non-text object]__

__Page 3 of 7__**Barns ****The ****Maximum ****Independent Set ****Problem ****tot ****Cnbk ****Ptaaar ****Graphs **

time O(nlogn) and show *M~(fip) *

> **1/2. **B&er[l] improve thia result by giving a family of algorithms, Bd, for the maximum independent set problem such that

*MBd(gP) *

**> ***d/(d ***+ **I), and which execute in time O(sddn). Note that Baker's algorithms are linear for any fixed d.

Choukhmane and Franco[3] describe a polynomial algorithm, A, for the **max- **imum independent set and show that *MA(&P) *** 1 **6/...