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

Internal Authors/Editors

Publication Details

Abstract

Recent research has revealed new applications of network control science

within bio-medicine, pharmacology, and medical therapeutics. These new

insights and new applications generated in turn a rediscovery of some

old, unresolved algorithmic questions, this time with a much stronger

motivation for their tackling. One of these questions regards the

so-called Structural Target Control optimization problem, known in

previous literature also as Structural Output Controllability problem.

Given a directed network (graph) 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., it can be driven from any

given initial configuration to any desired final one, through a finite

sequence of input values. In recent work, this problem has been shown to

be NP-hard, and several heuristic algorithms were introduced and

analyzed, both on randomly generated networks, and on bio-medical 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(logn)" role="presentation">O(logn).