When does FTP become FPT??

DOI10.1016/J.TCS.2026.115970MaRDI QIDQ7266638zbMATH OpenFDO

Authors Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Laure Morelle

Publication date 15 June 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115970

zbMATH Keywords

graph flowskernelization lower boundsparameterized complexityredundancy in solutions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A deterministic almost-linear time algorithm for minimum-cost flow
• Approximation algorithms for flexible graph connectivity
• Approximation algorithms for network design in non-uniform fault models
• Color-coding
• Fault-tolerant edge-disjoint \(s\)-\(t\) paths -- beyond uniform faults
• Flexible graph connectivity
• Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
• Incompressibility through Colors and IDs
• On Cayley's formula for counting forests
• On the complexity of finding a sparse connected spanning subgraph in a non-uniform failure model
• Parameterized algorithms
• The parameterized complexity of the k-biclique problem

This page was built for publication: When does FTP become FPT??

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7266638)