Samenvatting
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(k^O(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(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].
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(k^O(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(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].
| Originele taal-2 | Engels |
|---|---|
| Tijdschrift | CoRR |
| Volume | abs/2106.11689 |
| Status | Gepubliceerd - 2021 |