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

A4 Konferenspublikationer

Interna författare/redaktörer

Publikationens författare: Eugen Czeizler, Alexandru Popa, Victor Popescu
Redaktörer: Jansson Jesper, Martin-Vide Carlos, Vega-Rodriguez Miguel
Publiceringsår: 2018
Tidskrift: Lecture Notes in Computer Science
Förläggare: Springer
Moderpublikationens namn: Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings
Seriens namn: Lecture Notes in Bioinformatics (LNBI)
Volym: 10849
Artikelns första sida, sidnummer: 103
Artikelns sista sida, sidnummer: 114
ISBN: 978-3-319-91937-9
eISBN: 978-3-319-91938-6
ISSN: 0302-9743


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(log⁡n)" role="presentation">O(logn).


Cancer, computational complexity, Efficient algorithms, Graph-search algorithms


Senast uppdaterad 2020-18-02 vid 06:16