Fixed parameter algorithms and hardness of approximation results for the structural target controllability problem

Eugen Czeizler, Alexandru Popa, Victor Popescu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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).

Original languageEnglish
Title of host publicationAlgorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings
EditorsCarlos Martin-Vide, Jesper Jansson, Miguel A. Vega-Rodriguez
PublisherSpringer Verlag
Pages103-114
Number of pages12
ISBN (Print)9783319919379
DOIs
Publication statusPublished - Jan 1 2018
Event5th International Conference on Algorithms for Computational Biology, AlCoB 2018 - Hong Kong, China
Duration: Jun 25 2018Jun 26 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10849 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th International Conference on Algorithms for Computational Biology, AlCoB 2018
CountryChina
CityHong Kong
Period6/25/186/26/18

Fingerprint

Hardness of Approximation
Fixed-parameter Algorithms
Controllability
Hardness
Target
Heuristic algorithms
Medicine
Vertex of a graph
Pharmacology
Directed Network
Heuristic algorithm
Control Problem
NP-complete problem
Optimization Problem
Configuration
Subset
Output
Graph in graph theory

Keywords

  • Approximation algorithms
  • Fixed parameter algorithms
  • Protein interaction networks
  • Structural network control
  • Systems biology

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Czeizler, E., Popa, A., & Popescu, V. (2018). Fixed parameter algorithms and hardness of approximation results for the structural target controllability problem. In C. Martin-Vide, J. Jansson, & M. A. Vega-Rodriguez (Eds.), Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings (pp. 103-114). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10849 LNBI). Springer Verlag. https://doi.org/10.1007/978-3-319-91938-6_9

Fixed parameter algorithms and hardness of approximation results for the structural target controllability problem. / Czeizler, Eugen; Popa, Alexandru; Popescu, Victor.

Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings. ed. / Carlos Martin-Vide; Jesper Jansson; Miguel A. Vega-Rodriguez. Springer Verlag, 2018. p. 103-114 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10849 LNBI).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Czeizler, E, Popa, A & Popescu, V 2018, Fixed parameter algorithms and hardness of approximation results for the structural target controllability problem. in C Martin-Vide, J Jansson & MA Vega-Rodriguez (eds), Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10849 LNBI, Springer Verlag, pp. 103-114, 5th International Conference on Algorithms for Computational Biology, AlCoB 2018, Hong Kong, China, 6/25/18. https://doi.org/10.1007/978-3-319-91938-6_9
Czeizler E, Popa A, Popescu V. Fixed parameter algorithms and hardness of approximation results for the structural target controllability problem. In Martin-Vide C, Jansson J, Vega-Rodriguez MA, editors, Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings. Springer Verlag. 2018. p. 103-114. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-91938-6_9
Czeizler, Eugen ; Popa, Alexandru ; Popescu, Victor. / Fixed parameter algorithms and hardness of approximation results for the structural target controllability problem. Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings. editor / Carlos Martin-Vide ; Jesper Jansson ; Miguel A. Vega-Rodriguez. Springer Verlag, 2018. pp. 103-114 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{9e921ca8bcdf4edca766cd3fd5ae9a0f,
title = "Fixed parameter algorithms and hardness of approximation results for the structural target controllability problem",
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).",
keywords = "Approximation algorithms, Fixed parameter algorithms, Protein interaction networks, Structural network control, Systems biology",
author = "Eugen Czeizler and Alexandru Popa and Victor Popescu",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-319-91938-6_9",
language = "English",
isbn = "9783319919379",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "103--114",
editor = "Carlos Martin-Vide and Jesper Jansson and Vega-Rodriguez, {Miguel A.}",
booktitle = "Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings",
address = "Germany",

}

TY - GEN

T1 - Fixed parameter algorithms and hardness of approximation results for the structural target controllability problem

AU - Czeizler, Eugen

AU - Popa, Alexandru

AU - Popescu, Victor

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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).

AB - 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).

KW - Approximation algorithms

KW - Fixed parameter algorithms

KW - Protein interaction networks

KW - Structural network control

KW - Systems biology

UR - http://www.scopus.com/inward/record.url?scp=85049205513&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049205513&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-91938-6_9

DO - 10.1007/978-3-319-91938-6_9

M3 - Conference contribution

SN - 9783319919379

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 103

EP - 114

BT - Algorithms for Computational Biology - 5th International Conference, AlCoB 2018, Proceedings

A2 - Martin-Vide, Carlos

A2 - Jansson, Jesper

A2 - Vega-Rodriguez, Miguel A.

PB - Springer Verlag

ER -