Complexity Results for Equistable Graphs and Related Classes
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; chara...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Science + Business Media B.V.
2013
|
| Online Access: | http://hdl.handle.net/1721.1/77910 https://orcid.org/0000-0002-7488-094X |
| _version_ | 1826196158365564928 |
|---|---|
| author | Milanic, Martin Orlin, James B. Rudolf, Gabor |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Milanic, Martin Orlin, James B. Rudolf, Gabor |
| author_sort | Milanic, Martin |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:22:27Z |
| format | Article |
| id | mit-1721.1/77910 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:22:27Z |
| publishDate | 2013 |
| publisher | Springer Science + Business Media B.V. |
| record_format | dspace |
| spelling | mit-1721.1/779102022-09-26T17:28:08Z Complexity Results for Equistable Graphs and Related Classes Milanic, Martin Orlin, James B. Rudolf, Gabor Sloan School of Management Orlin, James B. Orlin, James B. 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. Germany. Federal Ministry of Education and Research Alexander von Humboldt-Stiftung (Sofja Kovalevskaja Award 2004) 2013-03-15T17:22:22Z 2013-03-15T17:22:22Z 2011-01 2009-01 Article http://purl.org/eprint/type/JournalArticle 0254-5330 1572-9338 http://hdl.handle.net/1721.1/77910 Milanič, Martin, James Orlin, and Gábor Rudolf. “Complexity Results for Equistable Graphs and Related Classes.” Annals of Operations Research 188.1 (2010): 359–370. CrossRef. Web. https://orcid.org/0000-0002-7488-094X en_US http://dx.doi.org/10.1007/s10479-010-0720-3 Annals of Operations Research Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Springer Science + Business Media B.V. Prof. Orlin via Alex Caracuzzo |
| spellingShingle | Milanic, Martin Orlin, James B. Rudolf, Gabor Complexity Results for Equistable Graphs and Related Classes |
| title | Complexity Results for Equistable Graphs and Related Classes |
| title_full | Complexity Results for Equistable Graphs and Related Classes |
| title_fullStr | Complexity Results for Equistable Graphs and Related Classes |
| title_full_unstemmed | Complexity Results for Equistable Graphs and Related Classes |
| title_short | Complexity Results for Equistable Graphs and Related Classes |
| title_sort | complexity results for equistable graphs and related classes |
| url | http://hdl.handle.net/1721.1/77910 https://orcid.org/0000-0002-7488-094X |
| work_keys_str_mv | AT milanicmartin complexityresultsforequistablegraphsandrelatedclasses AT orlinjamesb complexityresultsforequistablegraphsandrelatedclasses AT rudolfgabor complexityresultsforequistablegraphsandrelatedclasses |