Approximately counting locally-optimal structures
In general, constructing a locally-optimal structure is a little harder than constructing an arbitrary structure, but significantly easier than constructing a globally-optimal structure. A similar situation arises in listing. In counting, most problems are #P-complete, but in approximate counting we...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2016
|
| _version_ | 1797097810857820160 |
|---|---|
| author | Goldberg, L Gysel, R Lapinskas, J |
| author_facet | Goldberg, L Gysel, R Lapinskas, J |
| author_sort | Goldberg, L |
| collection | OXFORD |
| description | In general, constructing a locally-optimal structure is a little harder than constructing an arbitrary structure, but significantly easier than constructing a globally-optimal structure. A similar situation arises in listing. In counting, most problems are #P-complete, but in approximate counting we observe an interesting reversal of the pattern. Assuming that #BIS is not equivalent to #SAT under AP-reductions, we show that counting maximal independent sets in bipartite graphs is harder than counting maximum independent sets. Motivated by this, we show that various counting problems involving minimal separators are #SAT-hard to approximate. These problems have applications for constructing triangulations and phylogenetic trees. |
| first_indexed | 2024-03-07T05:00:36Z |
| format | Journal article |
| id | oxford-uuid:d823d477-337d-4988-9753-bce5043157b2 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:00:36Z |
| publishDate | 2016 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:d823d477-337d-4988-9753-bce5043157b22022-03-27T08:46:10ZApproximately counting locally-optimal structuresJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d823d477-337d-4988-9753-bce5043157b2Symplectic Elements at OxfordElsevier2016Goldberg, LGysel, RLapinskas, JIn general, constructing a locally-optimal structure is a little harder than constructing an arbitrary structure, but significantly easier than constructing a globally-optimal structure. A similar situation arises in listing. In counting, most problems are #P-complete, but in approximate counting we observe an interesting reversal of the pattern. Assuming that #BIS is not equivalent to #SAT under AP-reductions, we show that counting maximal independent sets in bipartite graphs is harder than counting maximum independent sets. Motivated by this, we show that various counting problems involving minimal separators are #SAT-hard to approximate. These problems have applications for constructing triangulations and phylogenetic trees. |
| spellingShingle | Goldberg, L Gysel, R Lapinskas, J Approximately counting locally-optimal structures |
| title | Approximately counting locally-optimal structures |
| title_full | Approximately counting locally-optimal structures |
| title_fullStr | Approximately counting locally-optimal structures |
| title_full_unstemmed | Approximately counting locally-optimal structures |
| title_short | Approximately counting locally-optimal structures |
| title_sort | approximately counting locally optimal structures |
| work_keys_str_mv | AT goldbergl approximatelycountinglocallyoptimalstructures AT gyselr approximatelycountinglocallyoptimalstructures AT lapinskasj approximatelycountinglocallyoptimalstructures |