6533b856fe1ef96bd12b2f4d

RESEARCH PRODUCT

Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem

Alexej DisterhoftMarkus KruppMarkus BlumenstockAndreas HildebrandtErnst Althaus

subject

Dynamic programmingDiscrete mathematicsCombinatoricsLinear programmingInduced subgraphHeuristicsInteger programmingAlgorithmTree (graph theory)Tree decompositionMathematicsofComputing_DISCRETEMATHEMATICSMathematicsInteger (computer science)

description

Finding differentially regulated subgraphs in a biochemical network is an important problem in bioinformatics. We present a new model for finding such subgraphs which takes the polarity of the edges (activating or inhibiting) into account, leading to the problem of finding a connected subgraph induced by \(k\) vertices with maximum weight. We present several algorithms for this problem, including dynamic programming on tree decompositions and integer linear programming. We compare the strength of our integer linear program to previous formulations of the \(k\)-cardinality tree problem. Finally, we compare the performance of the algorithms and the quality of the results to a previous approach for finding differentially regulated subgraphs.

yearjournalcountryeditionlanguage
2014-01-01
https://doi.org/10.1007/978-3-319-12691-3_21