[comp.theory] Max. Indep. Set

lucas@PSUVAX1.BITNET (01/09/90)

        Does anyone have pointers to a practical approximation
algorithm for the maximum independent set problem?

                                Thanks,  Joan Lucas

halldors@paul.rutgers.edu (Magnus M Halldorsson) (01/09/90)

In article <9001072141.AA22393@porthos.rutgers.edu> lucas@PSUVAX1.BITNET writes:

>         Does anyone have pointers to a practical approximation
> algorithm for the maximum independent set problem?

If you're looking for *performance guarantees* on general graphs,
you're out of luck: there are no polynomial algorithms known.

If you're thinking about good average case behaviour, the greedy
method does within a factor of 2 on random graphs.

Magnus

patrick@OKANE.CS.UMASS.EDU (Patrick Healy) (01/10/90)

>        Does anyone have pointers to a practical approximation
>algorithm for the maximum independent set problem?

>                                Thanks,  Joan Lucas


I would be interested in approximation algorithms (or references) to the
weighted version of ths problem i.e., Maximum Weighted Independent Set.  I've
seen references to some special cases of the related problem: Maximum Weighted
Clique, but nothing for the general case.

Any pointers would be appreciated.  Thanks,
Pat Healy,
Univ. of Mass, Amherst.

levinson@saturn.ucsc.edu (Robert) (01/11/90)

The following references may help. [3] has the best known approximation 
lgorithms. I have a polynomial-time algorithm for finding maximum (optimal)
independent sets of graphs that have no oddcycles that share an edge, in
case you are interested.

Bob

[1]   \s-2BAR-YEHUDA AND S. EVEN,\s+2 \f2A linear time approximation
algorithm for the weighted vertex cover problem\f1, J. Algorithms,
2(1981), pp. 198-203.
.XP
[2]   \s-2D. S. HOCHBAUM,\s+2 \f2Approximation algorithms for the
set covering and vertex cover problems\f1, Siam J. Comput.
11, no. 3 (1982), pp. 555-56.
.XP
[3]   \s-2B. MONIEN, AND E. SPECKENMEYER,\s+2 \f2Some Further Approximation Algorithms for the Vertex Cover Problem,\f1 Lecture Notes in
Computer Science 159 (1983) pp. 341-9.
.XP
[4]   \s-2C. SAVAGE\s+2, \f2Depth-First Search and the Vertex
Cover Problem\f1, Information Processing Letters, 14, no. 5, (1982).
Science, Gyor, (Hungary), 1983.
.XP
    Prof. Robert Levinson
    Computer and Information Sciences
    Applied Sciences Building
    University of California at Santa Cruz
    Santa Cruz, CA 95064
    (408)459-2087
    ARPANET:levinson@cis.ucsc.edu
       UUCP:ucbvax!ucsc!saturn!levinson