Abstract
Dynamic systems are becoming steadily more important with the profusion of mobile and distributed computing devices. Coincidentally incremental computation is a natural approach to deal with ongoing changes. We explore incremental computation in the parameterized complexity setting and show that incrementalization leads to non-trivial complexity classifications. Interestingly, some incremental versions of hard problems become tractable, while others remain hard. Moreover tractability or intractability is not a simple function of the problem’s static complexity, every level of the W-hierarchy exhibits complete problems with both tractable and intractable incrementalizations. For problems that are already tractable in their static form, we also show that incrementalization can lead to interesting algorithms, improving upon the trivial approach of using the static algorithm at each step.
Similar content being viewed by others
References
Batagelj, V., Zaversnik, M.: AnO(m)algorithm for cores decomposition of networks. arXiv: cs/0310049 (2003)
Crowston, R., Gutin, G., Jones, M., Raman, V., Saurabh, S.: Parameterized Complexity of MaxSat Above Average. In: Theoretical Informatics - 10th Latin American Symposium LATIN’12. LNCS 7256, pp. 184–194 (2012)
Desikan, P., Pathak, N., Srivastava, J., Kumar, V.: Incremental page rank computation on evolving graphs. In: Special interest tracks and posters of the 14th international conference on World Wide Web, WWW’05, pp. 1094–1095. ACM (2005)
Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer (1999)
Fernau, H., Schmid, M.L., Villanger, Y.: On the parameterised complexity of string morphism problems. Theory of Computing Systems 59(1), 24–51 (2016)
Flum, J., Grohe, M.: Parameterized complexity theory. Springer (2006)
Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory of Computing Systems 41(3), 501–520 (2007)
Held, M., Huber, S.: Topology-oriented incremental computation of voronoi diagrams of circular arcs and straight-line segments. Comput. Aided Des. 41(5), 327–338 (2009)
Jakub Ł., Sankowski, P.: Optimal decremental connectivity in planar graphs. Theory of Computing Systems 59(1), 1–17 (2016)
Marx, D.: The Parameterized complexity approximation algorithms. Comput. J. 51(1), 60–78 (2008)
Mathieson, L.: The parameterized complexity of editing graphs for bounded degeneracy. Theor. Comput. Sci. 411(34-36), 3181–3187 (2010)
Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity models for incremental computation. Theor. Comput. Sci. 130(1), 203–236 (1994)
Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the Parameterized Complexity of Reconfiguration Problems. In: Proceedings of the 8th International Symposium on Parameterized and Exact Computation, IPEC’13, pp. 281–294. Springer (2013)
Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying Modular Decomposition to Parameterized Cluster Editing Problems. Theory of Computing Systems 44(1), 91–104 (2009)
Ramalingam, G., Reps, T.: A categorized bibliography on incremental computation. In: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages POPL’93, pp. 502–510. ACM (1993)
Ramalingam, G., Reps, T.: On the computational complexity of dynamic graph problems. Theoretical Computer Science 158(1–2), 233–277 (1996)
Sundaresh, R.S., Hudak, P.: Incremental computation via partial evaluation. In: Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages POPL’91, pp. 1–13. ACM (1991)
Weber, V., Schwentick, T.: Dynamic complexity theory revisited. Theory of Computing Systems 40(4), 355–377 (2007)
Acknowledgments
This research was supported by Australian Research Council Grants DP110104560 and DP140100118.
Author information
Authors and Affiliations
Corresponding author
Additional information
This article is part of the Topical Collection on 50th Anniversary
Rights and permissions
About this article
Cite this article
Mans, B., Mathieson, L. Incremental Problems in the Parameterized Complexity Setting. Theory Comput Syst 60, 3–19 (2017). https://doi.org/10.1007/s00224-016-9729-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-016-9729-6