Complexity results for equistable graphs and related classes

Complexity results for equistable graphs and related classes

0.00 Avg rating0 Votes
Article ID: iaor20117923
Volume: 188
Issue: 1
Start Page Number: 359
End Page Number: 370
Publication Date: Aug 2011
Journal: Annals of Operations Research
Authors: , ,
Abstract:

The class of equistable graphs is defined by the existence of a cost structure on the vertices such that the maximal stable sets are characterized by their costs. This graph class, not contained in any nontrivial hereditary class, has so far been studied mostly from a structural point of view; characterizations and polynomial time recognition algorithms have been obtained for special cases. We focus on complexity issues for equistable graphs and related classes. We describe a simple pseudo‐polynomial‐time dynamic programming algorithm to solve the maximum weight stable set problem along with the weighted independent domination problem in some classes of graphs, including equistable graphs. Our results are obtained within the wider context of Boolean optimization; corresponding hardness results are also provided. More specifically, we show that the above problems are APX‐hard for equistable graphs and that it is co‐NP‐complete to determine whether a given cost function on the vertices of a graph defines an equistable cost structure of that graph.

Reviews

Required fields are marked *. Your email address will not be published.