Parameterized complexity of the \(\mathcal{T}_{h+1} \)-free edge deletion problem. (English) Zbl 07856021
Fernau, Henning (ed.) et al., Fundamentals of computation theory. 24th international symposium, FCT 2023, Trier, Germany, September 18–21, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14292, 221-233 (2023).
Summary: Given an undirected graph \(G=(V,E)\) and two integers \(k\) and \(h\), we study \(\mathcal{T}_{h+1} \)-Free Edge Deletion, where the goal is to remove at most \(k\) edges such that the resulting graph does not contain any tree on \(h+1\) vertices as a (not necessarily induced) subgraph, that is, we delete at most \(k\) edges in order to obtain a graph in which every component contains at most \(h\) vertices. This is desirable from the point of view of restricting the spread of a disease in transmission networks. Enright and Meeks (Algorithmica, 2018) gave an algorithm to solve \(\mathcal{T}_{h+1} \)-Free Edge Deletion whose running time on an \(n\)-vertex graph \(G\) of treewidth \(\mathsf{tw}(G)\) is bounded by \(O((\mathsf{tw}(G)h)^{2\mathsf{tw}(G)}n)\). However, it remains open whether the problem might belong to FPT when parameterized only by the treewidth \(\mathsf{tw}(G)\); they conjectured that treewidth alone is not enough, and that the problem is W[1]-hard with respect to this parameterization. We resolve this conjecture by showing that \(\mathcal{T}_{h+1} \)-Free Edge Deletion is indeed W[1]-hard when parameterized by \(\mathsf{tw}(G)\) alone. We resolve two additional open questions posed by Enright and Meeks (Algorithmica, 2018) concerning the complexity of \(\mathcal{T}_{h+1} \)-Free Edge Deletion on planar graphs and \(\mathcal{T}_{h+1} \)-Free Arc Deletion. We prove that the \(\mathcal{T}_{h+1} \)-Free Edge Deletion problem is NP-complete even when restricted to planar graphs. We also show that the \(\mathcal{T}_{h+1} \)-Free Arc Deletion problem is W[2]-hard when parameterized by the solution size on directed acyclic graphs.
For the entire collection see [Zbl 1537.68006].
For the entire collection see [Zbl 1537.68006].
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Cai, L., Fixed-parameter tractability of graph modification problems for hereditary properties, Inf. Process. Lett., 58, 4, 171-176, 1996 · Zbl 0875.68702 · doi:10.1016/0020-0190(96)00050-6 |
| [2] | Cygan, M., Parameterized Algorithms, 2015, Cham: Springer, Cham · Zbl 1334.90001 · doi:10.1007/978-3-319-21275-3 |
| [3] | Dahlhaus, E.; Johnson, DS; Papadimitriou, CH; Seymour, PD; Yannakakis, M., The complexity of multiterminal cuts, SIAM J. Comput., 23, 4, 864-894, 1994 · Zbl 0809.68075 · doi:10.1137/S0097539792225297 |
| [4] | Downey, RG; Fellows, MR, Parameterized Complexity, 2012, New York: Springer, New York · doi:10.1007/978-1-4612-0515-9 |
| [5] | Enright, J.; Meeks, K., Deleting edges to restrict the size of an epidemic: a new application for treewidth, Algorithmica, 80, 6, 1857-1889, 2018 · Zbl 1388.05174 · doi:10.1007/s00453-017-0311-7 |
| [6] | Fujito, T., A unified approximation algorithm for node-deletion problems, Discret. Appl. Math., 86, 2, 213-231, 1998 · Zbl 0906.68106 · doi:10.1016/S0166-218X(98)00035-3 |
| [7] | Gaikwad, A., Maity, S.: Further parameterized algorithms for the \(f\)-free edge deletion problem. Theor. Comput. Sci. (2022) |
| [8] | Ghosh, E., et al.: Faster parameterized algorithms for deletion to split graphs. Algorithmica 71(4), 989-1006 (2015) · Zbl 1325.68108 |
| [9] | Gibbens, JC, Descriptive epidemiology of the 2001 foot-and-mouth disease epidemic in great Britain: the first five months, Veterinary Rec., 149, 24, 729-743, 2001 · doi:10.1136/vr.149.24.729 |
| [10] | Guo, J.; Tokuyama, T., Problem kernels for NP-complete edge deletion problems: split and related graphs, Algorithms and Computation, 915-926, 2007, Heidelberg: Springer, Heidelberg · Zbl 1193.68194 · doi:10.1007/978-3-540-77120-3_79 |
| [11] | Kerr, B., Networks and the epidemiology of infectious disease, Interdisc. Perspect. Infect. Dis., 2011, 2011 |
| [12] | Knop, D., Masařík, T., Toufar, T.: Parameterized complexity of fair vertex evaluation problems. In: MFCS (2019) · Zbl 1541.68292 |
| [13] | Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, J. ACM, 41, 5, 960-981, 1994 · Zbl 0814.68064 · doi:10.1145/185675.306789 |
| [14] | Mansley, LM; Dunlop, PJ; Whiteside, SM; Smith, RGH, Early dissemination of foot-and-mouth disease virus through sheep marketing in February 2001, Veterinary Rec., 153, 2, 43-50, 2003 · doi:10.1136/vr.153.2.43 |
| [15] | Natanzon, A.; Shamir, R.; Sharan, R., Complexity classification of some edge modification problems, Discret. Appl. Math., 113, 1, 109-128, 2001 · Zbl 0982.68104 · doi:10.1016/S0166-218X(00)00391-7 |
| [16] | Robertson, N., Seymour, P.D.: Graph minors. iii. planar tree-width. J. Comb. Theory Ser. B 36(1), 49-64 (1984) · Zbl 0548.05025 |
| [17] | Szeider, S.: Not so easy problems for tree decomposable graphs. CoRR, abs/1107.1177 (2011). http://arxiv.org/abs/1107.1177, arXiv:1107.1177 |
| [18] | Watanabe, T.; Ae, T.; Nakamura, A., On the np-hardness of edge-deletion and -contraction problems, Discret. Appl. Math., 6, 1, 63-78, 1983 · Zbl 0511.68028 · doi:10.1016/0166-218X(83)90101-4 |
| [19] | Yannakakis, M.: Node-and edge-deletion np-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78, pp. 253-264. Association for Computing Machinery, New York, NY, USA (1978) · Zbl 1282.68131 |
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.
