Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem
A4 Conference proceedings
Internal Authors/Editors
Publication Details
List of Authors: Eugen Czeizler, Alexandru Popa, Victor Popescu
Editors: Jansson Jesper, Martin-Vide Carlos, Vega-Rodriguez Miguel
Publication year: 2018
Journal: Lecture Notes in Computer Science
Publisher: Springer
Book title: Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings
Title of series: Lecture Notes in Bioinformatics (LNBI)
Volume number: 10849
Start page: 103
End page: 114
ISBN: 978-3-319-91937-9
eISBN: 978-3-319-91938-6
ISSN: 0302-9743
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).
Keywords
Cancer, computational complexity, Efficient algorithms, Graph-search algorithms
Documents