FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees

Tomás Martínez-Muñoz, Andreas Wiese

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


We study the unsplittable flow on trees (UFT) problem in which we are given a tree with capacities on its edges and a set of tasks, where each task is described by a path and a demand. Our goal is to select a subset of the given tasks of maximum size such that the demands of the selected tasks respect the edge capacities. The problem models throughput maximization in tree networks. The best known approximation ratio for (unweighted) UFT is O(log n). We study the problem under the angle of FPT and FPT-approximation algorithms. We prove that
- UFT is FPT if the parameters are the cardinality k of the desired solution and the number of different task demands in the input,
- UFT is FPT under (1+δ)-resource augmentation of the edge capacities for parameters k and 1/δ, and
- UFT admits an FPT-5-approximation algorithm for parameter k. One key to our results is to compute structured hitting sets of the input edges which partition the given tree into O(k) clean components. This allows us to guess important properties of the optimal solution. Also, in some settings we can compute core sets of subsets of tasks out of which at least one task i is contained in the optimal solution. These sets have bounded size, and hence we can guess this task i easily.
A consequence of our results is that the integral multicommodity flow problem on trees is FPT if the parameter is the desired amount of sent flow. Also, even under (1+δ)-resource augmentation UFT is APX-hard, and hence our FPT-approximation algorithm for this setting breaks this boundary.
Original languageEnglish
Title of host publication29th Annual European Symposium on Algorithms (ESA 2021)
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages15
ISBN (Electronic)9783959772044
Publication statusPublished - 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969

Bibliographical note

Conference held: September 6-8, 2021, Lisbon, Portugal (Virtual Conference).


Dive into the research topics of 'FPT and FPT-Approximation Algorithms for Unsplittable Flow on Trees'. Together they form a unique fingerprint.

Cite this