TY - JOUR

T1 - Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem

AU - Czeizler, Eugen

AU - Popa, Alexandru

AU - Popescu, Victor

N1 - Funding Information:
This work was supported by the Academy of Finland through grant 272451, by the Finnish Funding Agency for Innovation through grant 1758/31/2016, by the Romanian National Authority for Scientific Research and Innovation, through the POC grant P 37 257 and by a grant of the Romanian Ministry of Research, Innovation and Digitization, CNCS - UEFISCDI, project number PN-III-P1-1.1-TE-2021-0253, within PNCDI III.
Funding Information:
This work was supported by the Academy of Finland through grant 272451, by the Finnish Funding Agency for Innovation through grant 1758/31/2016, by the Romanian National Authority for Scientific Research and Innovation, through the POC grant P 37 257 and by a grant of the Romanian Ministry of Research, Innovation and Digitization, CNCS-UEFISCDI, project number PN-III-P1-1.1-TE-2021-0253, within PNCDI III.
Publisher Copyright:
© Scientific Annals of Computer Science 2022.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Fixed parameter algorithm

KW - Linear networks

KW - Network control

KW - NP-hardness

KW - Optimization algorithm

KW - Structural control

UR - http://www.scopus.com/inward/record.url?scp=85134027609&partnerID=8YFLogxK

U2 - 10.7561/SACS.2022.1.109

DO - 10.7561/SACS.2022.1.109

M3 - Article

AN - SCOPUS:85134027609

SN - 1843-8121

VL - 32

SP - 109

EP - 136

JO - Scientific Annals of Computer Science

JF - Scientific Annals of Computer Science

IS - 1

ER -