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⊆ V(G) with demands dem: D→ 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: 1.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,2.a fixed-parameter tractable O⋆(kO ( k )) time algorithm for the general case, and a kernel of size polynomial in k for the special case of Many Visits TSP,3.a | V(G) |O ( t w ) time algorithm and a matching | V(G) |o ( t w ) 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].