A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

ABSTRACT

The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e. finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.

REFERENCES

• 1: V. E. Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics, v.135 n.1-3, p.3-16, 15 January 2004 [doi>10.1016/S0166-218X(02)00290-1]
• 2: C. Berge, Two theorems in graph theory, Proc. Nat. Acad. Sci. USA, 43 (1957) 842--844.
• 3: Andreas Brandstädt , Chính T. Hoàng , Van Bang Le, Stability number of bull- and chair-free graphs revisited, Discrete Applied Mathematics, v.131 n.1, p.39-50, 6 September 2003 [doi>10.1016/S0166-218X(02)00415-8]
• 4: A. Brandstädt, T. C. Hoáng and J.-M. Vanherpe, On minimal prime extensions of a four-vertex graph in a prime graph, Discrete Mathematics, 288 (2004) 9--17.
• 5: Andreas Brandstädt , Van Bang Le , H. N. de Ridder, Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes, Information Processing Letters, v.89 n.4, p.165-173, 28 February 2004 [doi>10.1016/j.ipl.2003.11.002]
• 6: Andreas Brandstädt , Hoàng-Oanh Le , Jean-Marie Vanherpe, Structure and stability number of chair-, co-P- and gem-free graphs revisited, Information Processing Letters, v.86 n.3, p.161-167, 16 May 2003 [doi>10.1016/S0020-0190(02)00487-8]
• 7: D. G. Corneil, H. Lerchs and L. Stewart-Burlingham, Complement reducible graphs, Discrete Applied Mathematics, 3 (1981) 163--174.
• 8: Caterina De Simone , Antonio Sassano, Stability number of bull- and chair-free graphs, Discrete Applied Mathematics, v.41 n.2, p.121-129, Jan. 26, 1993 [doi>10.1016/0166-218X(93)90032-J]
• 9: J. Edmonds, Path, trees, and flowers, Canadian J. Mathematics, 17 (1965) 449--467.
• 10: J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 69B (1965) 125--130.
• 11: M. Farber, M. Hujter and Zs. Tuza, An upper bound on the number of cliques in a graph, Networks, 23 (1993) 207--210.
• 12: F. Harary, Graph Theory, (Addison-Wesley, Reading, MA, 1969).
• 13: L. Lovász and M. D. Plummer, Matching Theory, Ann. Discrete Math, 29. North-Holland Publishing Co., Amsterdam; Akadmiai Kiad (Publishing House of the Hungarian Academy of Sciences), Budapest, 1986. xxvii+544 pp.
• 14: Ross M. McConnell , Jeremy P. Spinrad, Modular decomposition and transitive orientation, Discrete Mathematics, v.201 n.1-3, p.189-241, April 28, 1999 [doi>10.1016/S0012-365X(98)00319-7]
• 15: G. J. Minty, On maximal independent sets of vertices in claw-free graphs. J. Combinatorial Theory, Ser. B, 28 (1980) 284--304.
• 16: D. Nakamura and A. Tamura, A revision of Minty's algorithm for finding a maximum weight stable set of a claw-free graph, J. Oper. Res. Soc. Japan 44 (2001) 194--204.
• 17: S. Poljak, A note on stable sets and coloring of graphs, Comment. Math. Univ. Carolinae 15 (1974) 307--309.
• 18: N. Sbihi, Algorithme de recherche d'un independent de cardinalité maximum dans un graphe sans étoile, Discrete Mathematics, 29 (1980) 53--76.
• 19: A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Series: Algorithms and Combinatorics, Vol. 24, Springer, 2003, Chapter 69, pp. 1208--1217.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Pattern matching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
independent set, polynomial-time algorithm