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

Eugen Czeizler; Alexandru Popa; Victor-Bogdan Popescu

doi:/10.1007/978-3-319-91938-6_9

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

Eugen Czeizler, Alexandru Popa, Victor-Bogdan Popescu

Research output: Chapter in Book/Conference proceeding › Published conference proceeding › Scientific › peer-review

30 Downloads (Pure)

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

Original language	Undefined/Unknown
Title of host publication	Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings
Editors	Jansson Jesper, Martin-Vide Carlos, Vega-Rodriguez Miguel
Publisher	Springer
Pages	103–114
ISBN (Electronic)	978-3-319-91938-6
ISBN (Print)	978-3-319-91937-9
DOIs	https://doi.org//10.1007/978-3-319-91938-6_9
Publication status	Published - 2018
MoE publication type	A4 Article in a conference publication
Event	International Conference on Algorithms for Computational Biology (AlCoB) - 5th International Conference on Algorithms for Computational Biology, AlCoB Duration: 25 Jun 2018 → 26 Jun 2018

Conference

Conference	International Conference on Algorithms for Computational Biology (AlCoB)
Period	25/06/18 → 26/06/18

Keywords

Cancer
Efficient algorithms
Graph-search algorithms
computational complexity

Access to Document

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

main.pdf

http://urn.fi/URN:NBN:fi-fe2020102788471

NetPharma: Network pharmacology: drug re-purposing and discovery of multi-drug therapies by analytical approaches (Business Finland)
Czeizler, E. (Principal Investigator)
01/06/16 → 31/12/18
Project: Research

Cite this

Czeizler, E., Popa, A., & Popescu, V.-B. (2018). Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem. In J. Jesper, M.-V. Carlos, & V.-R. Miguel (Eds.), Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings (pp. 103–114). Springer. https://doi.org//10.1007/978-3-319-91938-6_9

Czeizler, Eugen ; Popa, Alexandru ; Popescu, Victor-Bogdan. / Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem. Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings. editor / Jansson Jesper ; Martin-Vide Carlos ; Vega-Rodriguez Miguel. Springer, 2018. pp. 103–114

@inproceedings{39b13299d02f40fab8732b4d5422b95f,

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){"} role={"}presentation{"}>O(logn).",

keywords = "Cancer, Efficient algorithms, Graph-search algorithms, computational complexity, Cancer, Efficient algorithms, Graph-search algorithms, computational complexity, Cancer, Efficient algorithms, Graph-search algorithms, computational complexity",

author = "Eugen Czeizler and Alexandru Popa and Victor-Bogdan Popescu",

note = "Also part of the Lecture Notes in Computer Science book series (LNCS, volume 10849); International Conference on Algorithms for Computational Biology (AlCoB) ; Conference date: 25-06-2018 Through 26-06-2018",

year = "2018",

doi = "/10.1007/978-3-319-91938-6_9",

language = "Odefinierat/ok{\"a}nt",

isbn = "978-3-319-91937-9",

pages = "103–114",

editor = "Jansson Jesper and Martin-Vide Carlos and Vega-Rodriguez Miguel",

booktitle = "Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings",

publisher = "Springer",

}

Czeizler, E, Popa, A & Popescu, V-B 2018, Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem. in J Jesper, M-V Carlos & V-R Miguel (eds), Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings. Springer, pp. 103–114, International Conference on Algorithms for Computational Biology (AlCoB), 25/06/18. 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-Bogdan.
Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings. ed. / Jansson Jesper; Martin-Vide Carlos; Vega-Rodriguez Miguel. Springer, 2018. p. 103–114.

Research output: Chapter in Book/Conference proceeding › Published conference proceeding › Scientific › peer-review

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-Bogdan

N1 - Also part of the Lecture Notes in Computer Science book series (LNCS, volume 10849)

PY - 2018

Y1 - 2018

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

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

KW - Cancer

KW - Efficient algorithms

KW - Graph-search algorithms

KW - computational complexity

KW - Cancer

KW - Efficient algorithms

KW - Graph-search algorithms

KW - computational complexity

KW - Cancer

KW - Efficient algorithms

KW - Graph-search algorithms

KW - computational complexity

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

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

M3 - Publicerad konferensartikel

SN - 978-3-319-91937-9

SP - 103

EP - 114

BT - Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings

A2 - Jesper, Jansson

A2 - Carlos, Martin-Vide

A2 - Miguel, Vega-Rodriguez

PB - Springer

T2 - International Conference on Algorithms for Computational Biology (AlCoB)

Y2 - 25 June 2018 through 26 June 2018

ER -

Czeizler E, Popa A, Popescu VB. Fixed Parameter Algorithms and Hardness of Approximation Results for the Structural Target Controllability Problem. In Jesper J, Carlos MV, Miguel VR, editors, Algorithms for Computational Biology : 5th International Conference, AlCoB 2018, Hong Kong, China, June 25–26, 2018, Proceedings. Springer. 2018. p. 103–114 doi: /10.1007/978-3-319-91938-6_9

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

Abstract

Conference

Keywords

Access to Document

Projects

NetPharma: Network pharmacology: drug re-purposing and discovery of multi-drug therapies by analytical approaches (Business Finland)

Cite this