ABSTRACT
It is known that the maximum independent set problem (MISP) is polynomially solvable for perfect, t-perfect, h-perfect, and W-perfect graphs. This chapter discusses the polynomial solvability of MISP for a family of generalized wheel graphs Wp2k+1, which are joints of an odd cycle C2k+1 and a clique Kp. We justify that, for any Wp2k+1, the Shor’s bound ψ*1(G) is exact, wherefrom it follows that MISP is polynomially solvable on graphs of this type. The bound ψ*1(G) utilizes an equivalent MISP-reformulation as a polynomial optimization problem with two groups of functionally redundant constraints and its dual. It is shown that the polytopes of perfect, t-perfect, h-perfect, and W-perfect graphs are obtainable from the Wp2k+1-graph’s polytope by relaxing a part of its constraints whence the polynomial MISP-solvability on these classes of graphs is also followed.
