This paper investigates the Critical Node Detection Problem (CNDP) on path graphs where connection costs between node pairs are binary (0 or 1). Two variants of the problem are explored based on whether node weights are uniform or arbitrary. For both cases, the objective is to identify a subset of nodes whose removal minimizes the number of important connections surviving. Efficient dynamic programming algorithms are proposed to solve these problems optimally. When node weights are uniform, the approach runs in O(n3K) time, where n is the number of nodes and K is the maximum number of deletions allowed. For arbitrary node weights with a total removal budget W, the solution is derived in O(n5) time.
| Published in | American Journal of Applied Mathematics (Volume 13, Issue 5) |
| DOI | 10.11648/j.ajam.20251305.13 |
| Page(s) | 339-343 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2025. Published by Science Publishing Group |
Critical Node Detection, Dynamic Programming, Polynomial Time Algorithm
| [1] | Addis, B., Aringhieri, R., Grosso, A., Hosteins, P.: Hybrid constructive heuristics for the critical node problem, Annals of Operations Research, 238(1-2), 637-649 (2016). |
| [2] | Addis, B., Di Summa, M., Grosso, A.: Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth, Discrete Applied Mathematics, 161(16), 2349-2360 (2013). |
| [3] | R. Ali and Y. Chen, “Power grid robustness via critical node identification in line-structured systems,” Electric Power Systems Research, vol. 187, p. 106455, 2020. |
| [4] | Arulselvan A., Commander C. W., Elefteriadou L., Pardalos P. M.: Detecting critical nodes in sparse graphs, Computers & Operations Research, 36, 2193-2200 (2009). |
| [5] | D. Banerjee and S. Rao, “Molecular pathway disruption analysis using path graph models,” Bioinformatics, vol. 34, no. 5, pp. 876-883, 2018. |
| [6] | Costa, Luciano da Fontoura and Rodrigues, Francisco A and Travieso, Gonzalo and Boas, Pedro RV: Characterization of complex networks: A survey of measurements, Advances in physics, 56 (1), 167-252 (2007). |
| [7] | Di Summa, M., Grosso, A., Locatelli, M.: Complexity of the critical node problem over trees, Computers & Operations Research, 38(12), 1766-1774 (2011). |
| [8] | Di Summa, M., and Faruk, SMO.: Critical node/edge detection problems on trees, 4OR, 21: 439-455 (2022). |
| [9] | Faruk, S. M. O., and Jabin, K. N. (2022). Critical Node Detection Problem over a Path, Applied Mathematics, 12(2), 25-31. |
| [10] | M. Fernandes and R. Bianchini, “Polynomial-time solutions for CNDP in special graph classes,” Theoretical Computer Science, vol. 823, pp. 59-73, 2020. |
| [11] | N. Gupta and S. Jain, “Risk-aware supply chain modeling and analysis using CNDP,” Journal of Operations Management, vol. 68, no. 1, pp. 40-55, 2022. |
| [12] | H. Kim and W. Tan, “Reliability optimization in sequential distributed computing systems,” ACM Transactions on Computer Systems, vol. 37, no. 3, pp. 1-26, 2019. |
| [13] | Oosten, M., Rutten, J. H. G. C., Spieksma, F. C. R.: Disconnecting graphs by removing vertices: a polyhedral approach, Statistica Neerlandica 61(1), 35-60 (2007). |
| [14] | M. O’ Reilly and A. Singh, “Adaptive curriculum design using critical path analysis,” Computers & Education, vol. 164, p. 104117, 2021. |
| [15] | Shen, S., Smith, J.: Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs, Networks, 60(2), 103-119 (2012). |
| [16] | J. Smith and X. Liu, “Critical node detection in linear communication networks,” IEEE Transactions on Network and Service Management, vol. 16, no. 2, pp. 230-242, 2019. |
| [17] | L. Zhang and P. Kumar, “Vulnerability analysis of urban transit networks using path-based criticality,” Transportation Research Part C, vol. 128, p. 103202, 2021. |
APA Style
Faruk, S. M. O., Jabin, K. N. (2025). Efficient Algorithms for Critical Node Detection on Path Graphs with Binary Connection Metrics. American Journal of Applied Mathematics, 13(5), 339-343. https://doi.org/10.11648/j.ajam.20251305.13
ACS Style
Faruk, S. M. O.; Jabin, K. N. Efficient Algorithms for Critical Node Detection on Path Graphs with Binary Connection Metrics. Am. J. Appl. Math. 2025, 13(5), 339-343. doi: 10.11648/j.ajam.20251305.13
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.ajam.20251305.13,
author = {Syed Md Omar Faruk and Kamrun Nahar Jabin},
title = {Efficient Algorithms for Critical Node Detection on Path Graphs with Binary Connection Metrics
},
journal = {American Journal of Applied Mathematics},
volume = {13},
number = {5},
pages = {339-343},
doi = {10.11648/j.ajam.20251305.13},
url = {https://doi.org/10.11648/j.ajam.20251305.13},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20251305.13},
abstract = {This paper investigates the Critical Node Detection Problem (CNDP) on path graphs where connection costs between node pairs are binary (0 or 1). Two variants of the problem are explored based on whether node weights are uniform or arbitrary. For both cases, the objective is to identify a subset of nodes whose removal minimizes the number of important connections surviving. Efficient dynamic programming algorithms are proposed to solve these problems optimally. When node weights are uniform, the approach runs in O(n3K) time, where n is the number of nodes and K is the maximum number of deletions allowed. For arbitrary node weights with a total removal budget W, the solution is derived in O(n5) time.},
year = {2025}
}
TY - JOUR T1 - Efficient Algorithms for Critical Node Detection on Path Graphs with Binary Connection Metrics AU - Syed Md Omar Faruk AU - Kamrun Nahar Jabin Y1 - 2025/09/25 PY - 2025 N1 - https://doi.org/10.11648/j.ajam.20251305.13 DO - 10.11648/j.ajam.20251305.13 T2 - American Journal of Applied Mathematics JF - American Journal of Applied Mathematics JO - American Journal of Applied Mathematics SP - 339 EP - 343 PB - Science Publishing Group SN - 2330-006X UR - https://doi.org/10.11648/j.ajam.20251305.13 AB - This paper investigates the Critical Node Detection Problem (CNDP) on path graphs where connection costs between node pairs are binary (0 or 1). Two variants of the problem are explored based on whether node weights are uniform or arbitrary. For both cases, the objective is to identify a subset of nodes whose removal minimizes the number of important connections surviving. Efficient dynamic programming algorithms are proposed to solve these problems optimally. When node weights are uniform, the approach runs in O(n3K) time, where n is the number of nodes and K is the maximum number of deletions allowed. For arbitrary node weights with a total removal budget W, the solution is derived in O(n5) time. VL - 13 IS - 5 ER -
Department of Mathematics, Shahjalal University of Science and Technology, Sylhet, Bangladesh
Department of Mathematics, Shahjalal University of Science and Technology, Sylhet, Bangladesh
Information