Scholarlink

<p>Minimum flow decomposition (MFD) — the problem of finding a minimum set of weighted source-to-sink paths that perfectly decomposes a flow — is a classical problem in Computer Science, and variants of it are powerful models in a different fields such as Bioinformatics and Transportation. Even on acyclic graphs, the problem is NP-hard, and most practical solutions have been via heuristics or approximations. While there is an extensive body of research on acyclic graphs, currently there is no <i>exact</i> solution on graphs with cycles. In this paper we present the first ILP formulation for three natural variants of the MFD problem in graphs with cycles, asking for a decomposition consisting only of weighted source-to-sink paths or cycles, trails, and walks, respectively. On three datasets of increasing levels of complexity from both Bioinformatics and Transportation, our approaches solve any instance in under 12 minutes. Our implementations are freely available at <a href="https://github.com/algbio/MFD-ILP">https://github.com/algbio/MFD-ILP</a>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Minimum flow decomposition in graphs with cycles using integer linear programming

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年11月24日

查看全文
  • Fernando H. C. Dias,
  • Lucia Williams,
  • Brendan Mumey,
  • Alexandru I. Tomescu

摘要

Minimum flow decomposition (MFD) — the problem of finding a minimum set of weighted source-to-sink paths that perfectly decomposes a flow — is a classical problem in Computer Science, and variants of it are powerful models in a different fields such as Bioinformatics and Transportation. Even on acyclic graphs, the problem is NP-hard, and most practical solutions have been via heuristics or approximations. While there is an extensive body of research on acyclic graphs, currently there is no exact solution on graphs with cycles. In this paper we present the first ILP formulation for three natural variants of the MFD problem in graphs with cycles, asking for a decomposition consisting only of weighted source-to-sink paths or cycles, trails, and walks, respectively. On three datasets of increasing levels of complexity from both Bioinformatics and Transportation, our approaches solve any instance in under 12 minutes. Our implementations are freely available at https://github.com/algbio/MFD-ILP.