Fare Zone Assignment with Hard Cut Budgets under Bounded Congestion

At the Oberwolfach workshop on Combinatorial Optimization in November 2024, Peis, with Pabst, Kauther and Fiorini, posed the following problem (Oberwolfach Report 50/2024, p. 2992). Commodities on a tree have paths, weights and budgets. A set of tree edges, the zone borders, is to be chosen; every commodity pays its weight once for each chosen edge on its path, the path of every commodity may contain at most its budget of chosen edges, and the total payment is to be maximized. The source states that the problem is polynomial on paths and strongly NP-hard on stars, that it has a 2-approximation when all budgets are even, and asks for its approximability when the congestion, the largest number of commodity paths through one edge, is at most \(k\). We answer this question up to polylogarithmic factors in \(k\), partly by citing known results. For \(k\le2\) the problem is a maximum-weight simple \(b\)-matching problem and is solvable in polynomial time on every host graph. For \(k\ge3\) it is strongly NP-hard and APX-hard already on stars with unit weights and budgets, by a reduction from independent set in cubic graphs. For every \(k\) it is a \(k\)-column-sparse packing integer program; hence known algorithms give the ratios \(8k\) and \(2k+o(k)\) in expectation, \(ek+o(k)\) deterministically, and \((k+1)/2+\varepsilon\) when all budgets are \(1\). Known hardness results for independent set in graphs of maximum degree \(k\) transfer to stars: for all sufficiently large \(k\) there is no \(k/(C\log^4k)\)-approximation unless \(\mathrm{P}=\mathrm{NP}\) (by a theorem of Chan), and none within \(ck/\log^2k\) under the Unique Games Conjecture and \(\mathrm{NP}\not\subseteq\mathrm{BPP}\) (Austrin, Khot and Safra); for \(k=3\) we only have APX-hardness. For unbounded congestion there is no \(|E|^{1-\varepsilon}\)-approximation on stars unless \(\mathrm{NP}=\mathrm{ZPP}\), while an \(|E|\)-approximation is trivial. The other two facts stated in the source, polynomiality on paths and the \(2\)-approximation, are proved by total unimodularity, and all hardness found here comes from commodities with budget \(1\). The cited approximation and hardness theorems are not ours. The closest work, by Hoefer, Kauther, Pabst, Peis and Tran, studies a different model in which a commodity over its budget drops out, and proves APX-hardness on stars with congestion \(3\) for that model. The exact dependence on \(k\) remains open. This is an unrefereed note.