Abstract
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 FPTapproximation 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 FPT5approximation 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 APXhard, and hence our FPTapproximation algorithm for this setting breaks this boundary.
BibTeX  Entry
@InProceedings{martinezmunoz_et_al:LIPIcs.ESA.2021.67,
author = {Mart{\'\i}nezMu\~{n}oz, Tom\'{a}s and Wiese, Andreas},
title = {{FPT and FPTApproximation Algorithms for Unsplittable Flow on Trees}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {67:167:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14648},
URN = {urn:nbn:de:0030drops146486},
doi = {10.4230/LIPIcs.ESA.2021.67},
annote = {Keywords: FPT algorithms, FPTapproximation algorithms, packing problems, unsplittable flow, trees}
}
Keywords: 

FPT algorithms, FPTapproximation algorithms, packing problems, unsplittable flow, trees 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 