Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Fixed Parameter Algorithms and...

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

Eugen Czeizler, Alexandru Popa, Victor Popescu, Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem. In: Jesper Jansson, Carlos Martin-Vide, Miguel Vega-Rodriguez (Eds.), Algorithms for Computational Biology, Lecture Notes in Computer Science 10849, 103 – 114, Springer International Publishing, 2018.

http://dx.doi.org/10.1007/978-3-319-91938-6_9

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(log n)

BibTeX entry:

@INPROCEEDINGS{inpCzPoPo18a,
  title = {Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem},
  booktitle = {Algorithms for Computational Biology},
  author = {Czeizler, Eugen and Popa, Alexandru and Popescu, Victor},
  volume = {10849},
  series = {Lecture Notes in Computer Science},
  editor = {Jansson, Jesper and Martin-Vide, Carlos and Vega-Rodriguez, Miguel},
  publisher = {Springer International Publishing},
  pages = {103 – 114},
  year = {2018},
  keywords = {Systems biology, Protein interaction networks, Structural network control, Approximation algorithms, Fixed parameter algorithms },
}

Belongs to TUCS Research Unit(s): Computational Biomodeling Laboratory (Combio Lab)

Edit publication