SACS | Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem

Published in Volume XXXII, Issue 1, 2022, pages 109-136, doi: 10.7561/SACS.2022.1.109

Authors: E. Czeizler, A. Popa, V. Popescu

Abstract

Recent research has revealed new and unexpected applications of network control science within biomedicine, pharmacology, and medical therapeutics. These new insights and new applications generated in turn a rediscovery of some old, unresolved algorithmic problems. One of these problems is the Structural Target Control optimization problem, known in previous literature also as Structural Output Controllability problem, which is defined as follows. Given a directed network and a target subset of nodes, the task is to select a small (or the smallest) set of nodes from which the target can be independently controlled, i.e., there exists a set of paths from the selected set of nodes (called driver nodes) to the target nodes such that no two paths intersect at the same distance from their targets. Recently, Structural Target Control optimization problem has been shown to be NP-hard, and several heuristic algorithms were introduced and analyzed, both on randomly generated networks, and on biomedical ones.

In this paper, we show that the Structural Target Controllability problem is fixed parameter tractable when parameterized by the number of target nodes. We also prove that the problem is hard to approximate at a factor better than O(log n). Taking into consideration the real case formulations of this problem we identify two more parameters which are naturally constrained by smaller bounds: the maximal length of a controlling path and the size of the set of nodes from which the control can start. With these new parameters we provide an approximation algorithm which is of exponential complexity in the size of the set of nodes from which the control can start and polynomial in all the other parameters.

Full Text (PDF)

References

[1] Erwin H. Bareiss. Sylvester’s identity and multistep integer-preserving Gaussian elimination. Mathematics of Computation, 22(103):565-578, 1968. doi:10.1090/S0025-5718-1968-0226829-0.

[2] Vincent A. Blomen, Peter Majek, Lucas T. Jae, Johannes W. Bigenzahn, Joppe Nieuwenhuis, Jacqueline Staring, Roberto Sacco, Ferdy R. van Diemen, Nadine Olk, Alexey Stukalov, Caleb Marceau, Hans Janssen, Jan E. Carette, Keiryn L. Bennett, Jacques Colinge, Giulio Superti-Furga, and Thijn R. Brummelkamp. Gene essentiality and synthetic lethality in haploid human cells. Science, 350(6264):1092-1096, 2015. doi:10.1126/science.aac7557.

[3] J. Adrian Bondy and Uppaluri S. R. Murty. Graph Theory. Graduate Texts in Mathematics. Springer, 2008. doi:10.1007/978-1-84628-970-5.

[4] Eugen Czeizler, Wu Kai Chiu, Cristian Gratie, Krishna Kanhaiya, and Ion Petre. Structural target controllability of linear networks. IEEE ACM Transactions on Computational Biology and Bioinformatics, 15(4):1217-1228, 2018. doi:10.1109/TCBB.2018.2797271.

[5] Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. doi:10.1007/978-1-4612-0515-9.

[6] Julio Saez-Rodriguez Denes Turei, Tamas Korcsmaros. Omnipath: guidelines and gateway for literature-curated signaling pathway resources. Nature Methods, 12(13):966-967, 2016. doi:10.1038/nmeth.4077.

[7] Bjorn Engquist. Encyclopedia of Applied and Computational Mathematics. Springer Publishing Company, Incorporated, 1st edition, 2016. doi:10.1007/978-3-540-70529-1.

[8] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634-652, 1998. doi:10.1145/285055.285059.

[9] Jorg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. doi:10.1007/3-540-29953-X.

[10] Jianxi Gao, Yang-Yu Liu, Raissa M. D’Souza, and Albert-Laszlo Barabasi. Target control of complex networks. Nature Communications, 5:5415, 2014. doi:10.1038/ncomms6415.

[11] Wei-Feng Guo et al. A novel algorithm for finding optimal driver nodes to target control complex networks and its applications for drug targets identification. BMC Genomics, 19(1):924, 2018. doi:10.1186/s12864-017-4332-z.

[12] Paul Hines, Seth Blumsack, Eduardo Cotilla Sanchez, and Clayton Barrows. The topological and electrical structure of power grids. In Proceedings of 43rd Hawaii International International Conference on Systems Science (HICSS-43 2010),, pages 1-10. IEEE Computer Society, 2010. doi:10.1109/HICSS.2010.398.

[13] Rudolf E. Kalman. Mathematical description of linear dynamical systems. Journal of the Society for Industrial and Applied Mathematics Series A Control, 1(2):152-192, jan 1963. doi:10.1137/0301010.

[14] Krishna Kanhaiya, Eugen Czeizler, Cristian Gratie, and Ion Petre. Controlling directed protein interaction networks in cancer. Scientific Reports, 7(1):10327, 2017. doi:10.1038/s41598-017-10491-y.

[15] A. Li, S. P. Cornelius, Y.-Y. Liu, L. Wang, and A.-L. Barabasi. The fundamental advantages of temporal networks. Science, 358(6366):1042-1046, 2017. doi:10.1126/science.aai7488.

[16] Ching-Tai Lin. Structural controllability. IEEE Transactions on Automatic Control, 19(3):201-208, 1974. doi:10.1109/TAC.1974.1100557.

[17] Yang-Yu Liu, Jean-Jacques Slotine, and Albert-Laszlo Barabasi. Controllability of complex networks. Nature, 473(7346):167-173, 2011. doi:10.1038/nature10011.

[18] Duncan MacRae. Direct factor analysis of sociometric data. Sociometry, 23(4):360-371, 1960. URL: http://www.jstor.org/stable/2785690.

[19] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: Simple building blocks of complex networks. Science, 298(5594):824-827, 2002. doi:10.1126/science.298.5594.824.

[20] Kazuo Murota. Systems analysis by graphs and matroids: structural solvability and controllability. Algorithms and combinatorics. Springer-Verlag, 1987. doi:10.1007/978-3-642-61586-3.

[21] Kazuo Murota and Svatopluk Poljak. Note on a Graph-theoretic Criterion for Structural Output Controllability. KAM series, discrete mathematics and combinatorics, operations research, mathematical linguistics. Department of Applied Mathematics, Charles University, 1989.

[22] Svatopluk Poljak. On the generic dimension of controllable subspaces. IEEE Transactions on Automatic Control, 35(3):367-369, 1990. doi:10.1109/9.50361.

[23] Victor Popescu. Fixed parameter algorithms for structural target controllability. https://github.com/vicbgdn/FixParamAlgNetControl, 2020.

[24] Robert W. Shields and J. Boyd Pearson. Structural controllability of multiinput linear systems. IEEE Transactions on Automatic Control, 21(2):203-212, apr 1976. doi:10.1109/TAC.1976.1101198.

[25] Takeaki Uno. Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In Hon Wai Leong, Hiroshi Imai, and Sanjay Jain, editors, Proceedings of 8th International Symposium on Algorithms and Computation, ISAAC ’97, volume 1350 of Lecture Notes in Computer Science, pages 92-101. Springer, 1997. doi:10.1007/3-540-63890-3\_11.

[26] Vijay V. Vazirani. Approximation algorithms. Springer, 2001. doi:10.1007/978-3-662-04565-7.

[27] Arunachalam Vinayagam, Travis E. Gibson, Ho-Joon Lee, Bahar Yilmazel, Charles Roesel, Yanhui Hu, Young Kwon, Amitabh Sharma, Yang-Yu Liu, Norbert Perrimon, and Albert-Laszlo Barabasi. Controllability analysis of the directed human protein interaction network identifies disease genes and drug targets. Proceedings of the National Academy of Sciences, 113(18):4976-4981, 2016. doi:10.1073/pnas.1603992113.

[28] Tim Wang, Kivanc Birsoy, Nicholas W. Hughes, Kevin M. Krupczak, Yorick Post amd Jenny J. Wei, Eric S. Lander, and David M. Sabatini. Identification and characterization of essential genes in the human genome. Science, 350(6264):1096-1101, 2015. doi:10.1126/science.aac7041.

[29] Jacques L. Willems. Structural controllability and observability. Systems and Control Letters, 8(1):5-12, 1986. doi:10.1016/0167-6911(86)90023-X.

[30] Leslie D. Zeleny. Adaptation of research findings in social leadership to college classroom procedures. Sociometry, 13(4):314-328, 1950. doi:10.2307/2785274.

[31] Tianzuo Zhan and Michael Boutros. Towards a compendium of essential genes – from model organisms to synthetic lethality in cancer cells. Critical Reviews in Biochemistry and Molecular Biology, 51(2):74-85, 2016. PMID: 26627871. doi:10.3109/10409238.2015.1117053.

Bibtex

@article{sacscuza:czeizler22fpaharstcp,
  title={Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem},
  author={E. Czeizler, A. Popa, V. Popescu},
  journal={Scientific Annals of Computer Science},
  volume={32},
  number={1},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2022},
  pages={109-136},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2022.1.109}
}