×

Dynamic parameterized problems. (English) Zbl 1393.68074

Summary: We study the parameterized complexity of various graph theoretic problems in the dynamic framework where the input graph is being updated by a sequence of edge additions and deletions. Vertex subset problems on graphs typically deal with finding a subset of vertices having certain properties. In real world applications, the graph under consideration often changes over time and due to this dynamics, the solution at hand might lose the desired properties. The goal in the area of dynamic graph algorithms is to efficiently maintain a solution under these changes. Recomputing a new solution on the new graph is an expensive task especially when the number of modifications made to the graph is significantly smaller than the size of the graph. In the context of parameterized algorithms, two natural parameters are the size \(k\) of the symmetric difference of the edge sets of the two graphs (on \(n\) vertices) and the size \(r\) of the symmetric difference of the two solutions. We study the Dynamic \(\Pi \)-Deletion problem which is the dynamic variant of the classical \(\Pi\)-Deletion problem and show NP-hardness, fixed-parameter tractability and kernelization results. For specific cases of Dynamic \(\Pi\)-Deletion such as Dynamic Vertex Cover and Dynamic Feedback Vertex Set, we describe improved algorithms and linear kernels. Specifically, we show that Dynamic Vertex Cover has a deterministic algorithm with \(1.0822^k n^{\mathcal {O}(1)}\) running time and Dynamic Feedback Vertex Set has a randomized algorithm with \(1.6667^k n^{\mathcal {O}(1)}\) running time. We also show that Dynamic Connected Feedback Vertex Set can be solved in \(2^{\mathcal {O}(k)} n^{\mathcal {O}(1)}\) time. For each of Dynamic Connected Vertex Cover, Dynamic Dominating Set and Dynamic Connected Dominating Set, we describe an algorithm with \(2^k n^{\mathcal {O}(1)}\) running time and show that this is the optimal running time (up to polynomial factors) assuming the Set Cover Conjecture.

MSC:

68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
68W40 Analysis of algorithms

Software:

tw-heuristic
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abu-Khzam, F.N., Cai, S., Egan, J., Shaw, P., Wang. K.: Turbo-charging cominating set with an FPT subroutine: Further Improvements and Experimental Analysis. In: Proceedings of the 14th International Conference on Theory and Applications of Models of Computation pp. 59-70. Springer (2017) · Zbl 1485.68242
[2] Abu-Khzam, FN; Egan, J; Fellows, MR; Rosamond, FA, Shaw. P.: on the parameterized complexity of dynamic problems, Theor. Comput. Sci., 607, 426-434, (2015) · Zbl 1333.68130 · doi:10.1016/j.tcs.2015.06.053
[3] Bodlaender, HL; Cygan, M; Kratsch, S; Nederlof, J, Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth, Inf. Comput., 243, 86-111, (2015) · Zbl 1327.68126 · doi:10.1016/j.ic.2014.12.008
[4] Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proceedings of the \(10th\) Annual ACM-SIAM Symposium on Discrete Algorithms SODA ’99, pp. 856-857. SIAM (1999) · Zbl 0938.68073
[5] Bonsma, P., Lokshtanov, D.: Feedback vertex set in mixed graphs. In: Proceedings of the 12th International Conference on Algorithms and Data Structures WADS ’11, pp. 122-133. Springer (2011) · Zbl 1342.05180
[6] Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the vertex feedback set problem with applications to constraint satisfaction and bayesian inference. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms SODA ’94, pp. 344-354. SIAM (1994) · Zbl 0867.05073
[7] Cai, L, Fixed-parameter tractability of graph modification problems for hereditary properties, Inf. Process. Lett., 58, 171-176, (1996) · Zbl 0875.68702 · doi:10.1016/0020-0190(96)00050-6
[8] Cygan, M; Dell, H; Lokshtanov, D; Marx, D; Nederlof, J; Okamoto, Y; Paturi, R; Saurabh, S; Wahlstrom, M, On problems as hard as CNF-SAT, ACM Trans. Algorithms, 12, 41, (2016) · Zbl 1442.68064 · doi:10.1145/2925416
[9] Cygan, M., Fomin, F.V., Łukasz, K., Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015) · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3
[10] Chen, J; Kanj, IA; Jia, W, Vertex cover: further observations and further improvements, J. Algorithms, 41, 280-301, (2001) · Zbl 1017.68087 · doi:10.1006/jagm.2001.1186
[11] Chen, J; Kanj, IA; Xia, G, Improved upper bounds for vertex cover, Theor. Comput. Sci., 411, 3736-3756, (2010) · Zbl 1205.05217 · doi:10.1016/j.tcs.2010.06.026
[12] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science FOCS ’11, pp. 150-159. IEEE (2011) · Zbl 1292.68122
[13] Downey, RG; Egan, J; Fellows, MR; Rosamond, FA, Shaw. P.: dynamic dominating set and turbo-charging greedy heuristics, Tsinghua. Sci. Technol., 19, 329-337, (2014) · doi:10.1109/TST.2014.6867515
[14] Downey, R.G., Fellows, R.G.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013) · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1
[15] Diestel, R.: Raph Theory. Springer, Berlin (2005)
[16] Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009) pp. 378-389. Springer (2009) · Zbl 1248.68243
[17] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006) · Zbl 1143.68016
[18] Fomin, F.V., Gaspers, S., Lokshtanov, D., Saurabh, S.: Exact algorithms via monotone local search. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing STOC ’16, pp. 764-775. ACM (2016) · Zbl 1375.68185
[19] Fomin, FV; Gaspers, S; Saurabh, S; Stepanov, AA, On two techniques of combining branching and treewidth, Algorithmica, 54, 181-207, (2009) · Zbl 1185.68475 · doi:10.1007/s00453-007-9133-3
[20] Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Proceedings of the 30th Workshop on Graph Theoretic Concepts in Computer Science (WG) pp. 245-256. Springer (2005) · Zbl 1112.68420
[21] Gaspers, S., Gudmundsson, J., Jones, M., Mestre, J., Rümmele, S.: Turbocharging treewidth heuristics. In: Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) volume 63 of Leibniz International Proceedings in Informatics (LIPIcs) pp. 13:1-13:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017) · Zbl 1398.68490
[22] Hartung, S; Niedermeier, R, Incremental List coloring of graphs, parameterized by conservation, Theor. Comput. Sci., 494, 86-98, (2013) · Zbl 1294.68085 · doi:10.1016/j.tcs.2012.12.049
[23] Kociumaka, T; Pilipczuk, M, Faster deterministic feedback vertex set, Inf. Process. Lett., 114, 556-560, (2014) · Zbl 1371.68116 · doi:10.1016/j.ipl.2014.05.001
[24] Khot, S; Raman, V, Parameterized complexity of finding subgraphs with hereditary properties, Theor. Comput. Sci., 289, 997-1008, (2002) · Zbl 1061.68061 · doi:10.1016/S0304-3975(01)00414-5
[25] Lewis, JM; Yannakakis, M, The node-deletion problem for hereditary properties is NP-complete, J. Comput. Syst. Sci., 20, 219-230, (1980) · Zbl 0436.68029 · doi:10.1016/0022-0000(80)90060-4
[26] Misra, N; Philip, G; Raman, V; Saurabh, S; Sikdar, S, FPT algorithms for connected feedback vertex set, J. Comb. Optim., 24, 131-146, (2012) · Zbl 1258.05060 · doi:10.1007/s10878-011-9394-2
[27] Thomassé, S, A \(4k^2\) kernel for feedback vertex set, ACM Trans. Algorithms, 6, 32, (2010) · Zbl 1300.05236 · doi:10.1145/1721837.1721848
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.