GreedyMAX-type Algorithms for the Maximum Independent Set Problem

A maximum independent set problem for a simple graph

G

 = (

V

,

E

) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued function

p

defined on the vertex set

V

(

G

) and called a potential function of a graph

G

, while

P

(

G

) =  max

v

 ∈ 

V

(

G

)

p

(

v

) is called a potential of

G

. For any graph

P

(

G

) ≤ Δ(

G

), where Δ(

G

) is the maximum degree of

G

. Moreover, Δ(

G

) − 

P

(

G

) may be arbitrarily large. A potential of a vertex lets us get a closer insight into the properties of its neighborhood which leads to the definition of the family of

GreedyMAX

-type algorithms having the classical

GreedyMAX

algorithm as their origin. We establish a lower bound 1/(

P

 + 1) for the performance ratio of

GreedyMAX

-type algorithms which favorably compares with the bound 1/(Δ + 1) known to hold for

GreedyMAX

. The cardinality of an independent set generated by any

GreedyMAX

-type algorithm is at least

$\sum_{v\in V(G)} (p(v)+1)^{-1}$

, which strengthens the bounds of Turán and Caro-Wei stated in terms of vertex degrees.