WorksComputer Science
Path-constrained Packing on Trees
Abstract
An instance of Budgeted Path-constrained Packing on Trees (BPPT) consists of a graph together with a spanning tree , a weight for each tree edge and a budget for each non-tree edge . The goal is to find a maximum weight packing of fundamental cuts respecting the budgets. Equivalently, an instance of BPPT is an integer program of the form where is a transposed edge-path-tree matrix, and . We define the congestion of a BPPT instance as the maximum number of non-zeros in a column of . The unit congestion is defined similarly, except that rows with are ignored. We also consider the minimum budget . In this paper, we begin the study of BPPT through the lens of the three parameters , and , and relative to the standard LP relaxation . BPPT generalizes the independent set problem in graphs of maximum degree at most and is a special case of the -matching problem in hypergraphs of rank at most . We obtain approximation algorithms for BPPT with factors , and for . These bounds are relative to the standard LP relaxation and, as we show, integrality gap tight with respect to parameters and , and almost integrality gap tight relative to . We complement these results with a -approximation for fixed which is not relative to the standard LP relaxation and has running time parameterized by .