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

Isja Mannens; Jesper Nederlof; Céline Swennenhuis; Krisztina Szilágyi

doi:10.1007/978-3-030-86838-3_5

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

Isja Mannens, Jesper Nederlof, Céline Swennenhuis, Krisztina Szilágyi

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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^⋆(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 ⁽ ^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].

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	47th International Workshop, WG 2021 Warsaw, Poland, June 23–25, 2021 Revised Selected Papers
Editors	Lukasz Kowalik, Michal Pilipczuk, Pawel Rzazewski
Publisher	Springer
Pages	52-79
Number of pages	28
ISBN (Electronic)	978-3-030-86838-3
ISBN (Print)	978-3-030-86837-6
DOIs	https://doi.org/10.1007/978-3-030-86838-3_5
Publication status	Published - 23 Jun 2021

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Cham
Volume	12911
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Bibliographical note

Funding Information:
Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 853234) and by the Netherlands Organization for Scientific Research under project no. 613.009.031b.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-030-86838-3_5

978-3-030-86838-3_5Final published version, 487 KBLicence: Taverne

https://dblp.org/rec/conf/wg/MannensNSS21

Cite this

Mannens, I., Nederlof, J., Swennenhuis, C., & Szilágyi, K. (2021). On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem. In L. Kowalik, M. Pilipczuk, & P. Rzazewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021 Warsaw, Poland, June 23–25, 2021 Revised Selected Papers (pp. 52-79). (Lecture Notes in Computer Science; Vol. 12911). Springer. https://doi.org/10.1007/978-3-030-86838-3_5

Mannens, Isja ; Nederlof, Jesper ; Swennenhuis, Céline et al. / On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem. Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021 Warsaw, Poland, June 23–25, 2021 Revised Selected Papers. editor / Lukasz Kowalik ; Michal Pilipczuk ; Pawel Rzazewski. Springer, 2021. pp. 52-79 (Lecture Notes in Computer Science).

@inproceedings{ed23aa3a228b43fd9f2119093d45f14e,

title = "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{\textquoteright}20].",

author = "Isja Mannens and Jesper Nederlof and C{\'e}line Swennenhuis and Krisztina Szil{\'a}gyi",

note = "Funding Information: Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No. 853234) and by the Netherlands Organization for Scientific Research under project no. 613.009.031b. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.",

year = "2021",

month = jun,

day = "23",

doi = "10.1007/978-3-030-86838-3_5",

language = "English",

isbn = "978-3-030-86837-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "52--79",

editor = "Lukasz Kowalik and Michal Pilipczuk and Pawel Rzazewski",

booktitle = "Graph-Theoretic Concepts in Computer Science",

}

Mannens, I, Nederlof, J, Swennenhuis, C & Szilágyi, K 2021, On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem. in L Kowalik, M Pilipczuk & P Rzazewski (eds), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021 Warsaw, Poland, June 23–25, 2021 Revised Selected Papers. Lecture Notes in Computer Science, vol. 12911, Springer, pp. 52-79. https://doi.org/10.1007/978-3-030-86838-3_5

On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem. / Mannens, Isja; Nederlof, Jesper; Swennenhuis, Céline et al.
Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021 Warsaw, Poland, June 23–25, 2021 Revised Selected Papers. ed. / Lukasz Kowalik; Michal Pilipczuk; Pawel Rzazewski. Springer, 2021. p. 52-79 (Lecture Notes in Computer Science; Vol. 12911).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Mannens, Isja

AU - Nederlof, Jesper

AU - Swennenhuis, Céline

AU - Szilágyi, Krisztina

N1 - Funding Information: Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 853234) and by the Netherlands Organization for Scientific Research under project no. 613.009.031b. Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021/6/23

Y1 - 2021/6/23

N2 - 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].

AB - 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].

UR - http://www.scopus.com/inward/record.url?scp=85115882972&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-86838-3_5

DO - 10.1007/978-3-030-86838-3_5

M3 - Conference contribution

SN - 978-3-030-86837-6

T3 - Lecture Notes in Computer Science

SP - 52

EP - 79

BT - Graph-Theoretic Concepts in Computer Science

A2 - Kowalik, Lukasz

A2 - Pilipczuk, Michal

A2 - Rzazewski, Pawel

PB - Springer

ER -

Mannens I, Nederlof J, Swennenhuis C, Szilágyi K. On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem. In Kowalik L, Pilipczuk M, Rzazewski P, editors, Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021 Warsaw, Poland, June 23–25, 2021 Revised Selected Papers. Springer. 2021. p. 52-79. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-86838-3_5

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

Abstract

Publication series

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this