On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem

Abstract

We study a variant of Min Cost Flow in which the flow needs to be connected. Specifically, in the Connected Flow problem one is given a directed graph $G$, along with a set of demand vertices $D\subseteq V(G)$ with demands $\mathsf{dem}:D\to \mathbb{N}$, and costs and capacities for each edge. The goal is to find a minimum cost flow that satisfies the demands, respects the capacities and induces a (strongly) connected subgraph. This generalizes previously studied problems like the (Many Visits) TSP. We study the parameterized complexity of Connected Flow parameterized by $|D|$, the treewidth $tw$ and by vertex cover size $k$ of $G$ and provide: (i) $\mathsf{NP}$-completeness already for the case $|D|=2$ with only unit demands and capacities and no edge costs, and fixed-parameter tractability if there are no capacities, (ii) a fixed-parameter tractable ${\mathcal{O}}^{\star }(k^{\mathcal{O}(k)})$ time algorithm for the general case, and a kernel of size polynomial in $k$ for the special case of Many Visits TSP, (iii) a $|V(G){|}^{\mathcal{O}(tw)}$ time algorithm and a matching $|V(G){|}^{o(tw)}$ time conditional lower bound conditioned on the Exponential Time Hypothesis. To achieve some of our results, we significantly extend an approach by Kowalik et al.~[ESA'20].

To be included in the proceedings of the 'International Workshop on Graph-Theoretic Concepts in Computer Science' (WG2021)