On the parameterized complexity of dynamic problems
In a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained from what “remained” from the original solution at a minimal cost. In the pa...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , , , |
| التنسيق: | article |
| منشور في: |
2015
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/4761 http://dx.doi.org/10.1016/j.tcs.2015.06.053 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0304397515005630 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513464563662848 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Egan, Judith Fellows, Michael R. Rosamond, Frances A. Shaw, Peter |
| author2_role | author author author author |
| author_facet | Abu-Khzam, Faisal N. Egan, Judith Fellows, Michael R. Rosamond, Frances A. Shaw, Peter |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Egan, Judith Fellows, Michael R. Rosamond, Frances A. Shaw, Peter |
| dc.date.none.fl_str_mv | 2015 2016-11-08T14:17:47Z 2016-11-08T14:17:47Z 2016-11-08 |
| dc.identifier.none.fl_str_mv | 0304-3975 http://hdl.handle.net/10725/4761 http://dx.doi.org/10.1016/j.tcs.2015.06.053 Abu-Khzam, F. N., Egan, J., Fellows, M. R., Rosamond, F. A., & Shaw, P. (2015). On the parameterized complexity of dynamic problems. Theoretical Computer Science, 607, 426-434. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0304397515005630 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Theoretical Computer Science |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | On the parameterized complexity of dynamic problems |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | In a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained from what “remained” from the original solution at a minimal cost. In the parameterized version of such a problem, the changes made to an instance are bounded by an edit-parameter, while the cost of reconstructing a solution is bounded by some increment-parameter. Capitalizing on the recent initial work of Downey et al. on the Dynamic Dominating Set problem, we launch a study of the dynamic versions of a number of problems including Vertex Cover, Maximum Clique, Connected Vertex Cover and Connected Dominating Set. In particular, we show that Dynamic Vertex Cover is W[1]-hard, and the connected versions of both Dynamic Vertex Cover and Dynamic Dominating Set become fixed-parameter tractable with respect to the edit-parameter while they remain W[2]-hard with respect to the increment-parameter. Moreover, we show that Dynamic Independent Dominating Set is W[2]-hard with respect to the edit-parameter. We introduce the reoptimization parameter, which bounds the difference between the cardinalities of initial and target solutions. We prove that, while Dynamic Maximum Clique is fixed-parameter tractable with respect to the edit-parameter, it becomes W[1]-hard if the increment-parameter is replaced with the reoptimization parameter. Finally, we establish that Dynamic Dominating Set becomes W[2]-hard when the target solution is required not to be larger than the initial one, even if the edit parameter is exactly one. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_73eb7d524d65bef9f9d2953748657f08 |
| identifier_str_mv | 0304-3975 Abu-Khzam, F. N., Egan, J., Fellows, M. R., Rosamond, F. A., & Shaw, P. (2015). On the parameterized complexity of dynamic problems. Theoretical Computer Science, 607, 426-434. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/4761 |
| publishDate | 2015 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On the parameterized complexity of dynamic problemsAbu-Khzam, Faisal N.Egan, JudithFellows, Michael R.Rosamond, Frances A.Shaw, PeterIn a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained from what “remained” from the original solution at a minimal cost. In the parameterized version of such a problem, the changes made to an instance are bounded by an edit-parameter, while the cost of reconstructing a solution is bounded by some increment-parameter. Capitalizing on the recent initial work of Downey et al. on the Dynamic Dominating Set problem, we launch a study of the dynamic versions of a number of problems including Vertex Cover, Maximum Clique, Connected Vertex Cover and Connected Dominating Set. In particular, we show that Dynamic Vertex Cover is W[1]-hard, and the connected versions of both Dynamic Vertex Cover and Dynamic Dominating Set become fixed-parameter tractable with respect to the edit-parameter while they remain W[2]-hard with respect to the increment-parameter. Moreover, we show that Dynamic Independent Dominating Set is W[2]-hard with respect to the edit-parameter. We introduce the reoptimization parameter, which bounds the difference between the cardinalities of initial and target solutions. We prove that, while Dynamic Maximum Clique is fixed-parameter tractable with respect to the edit-parameter, it becomes W[1]-hard if the increment-parameter is replaced with the reoptimization parameter. Finally, we establish that Dynamic Dominating Set becomes W[2]-hard when the target solution is required not to be larger than the initial one, even if the edit parameter is exactly one.PublishedN/A2016-11-08T14:17:47Z2016-11-08T14:17:47Z20152016-11-08Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article0304-3975http://hdl.handle.net/10725/4761http://dx.doi.org/10.1016/j.tcs.2015.06.053Abu-Khzam, F. N., Egan, J., Fellows, M. R., Rosamond, F. A., & Shaw, P. (2015). On the parameterized complexity of dynamic problems. Theoretical Computer Science, 607, 426-434.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttp://www.sciencedirect.com/science/article/pii/S0304397515005630enTheoretical Computer Scienceinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/47612021-03-19T10:00:50Z |
| spellingShingle | On the parameterized complexity of dynamic problems Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | On the parameterized complexity of dynamic problems |
| title_full | On the parameterized complexity of dynamic problems |
| title_fullStr | On the parameterized complexity of dynamic problems |
| title_full_unstemmed | On the parameterized complexity of dynamic problems |
| title_short | On the parameterized complexity of dynamic problems |
| title_sort | On the parameterized complexity of dynamic problems |
| url | http://hdl.handle.net/10725/4761 http://dx.doi.org/10.1016/j.tcs.2015.06.053 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php http://www.sciencedirect.com/science/article/pii/S0304397515005630 |