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

Scientific Annals of Computer Science

article

E. Czeizler¹  A. Popa²  V. Popescu¹ 

[1] Abo Akademi University;University of Bucharest

关键词: Structural control;    Network control;    Optimization algorithm;    Fixed parameter algorithm;    NP-hardness;    Linear networks;   

DOI  :  10.7561/SACS.2022.1.109

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

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.

【 授权许可】

CC BY-ND