Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation

Hans L. Bodlaender

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

Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation

Hans L. Bodlaender^*

^*Corresponding author for this work

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

Abstract

In this paper, we show that Bandwidth is hard for the complexity class W[t] for all t∈ N, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path P_N and integer M, decide if there exists a mapping of the vertices of P_N to a path P_M, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the pre-image of a vertex from P_M equals an integer c. We show that Weighted Path Emulation, with c as parameter, is hard for W[t] for all t∈ N, and is strongly NP-complete. We also show that Directed Bandwidth is hard for W[t] for all t∈ N, for directed acyclic graphs whose underlying undirected graph is a caterpillar.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	47th International Workshop, WG 2021, Revised Selected Papers
Editors	Lukasz Kowalik, Michal Pilipczuk, Pawel Rzazewski
Publisher	Springer
Pages	15-27
Number of pages	13
ISBN (Print)	9783030868376
DOIs	https://doi.org/10.1007/978-3-030-86838-3_2
Publication status	Published - 2021
Event	47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 - Virtual, Online Duration: 23 Jun 2021 → 25 Jun 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12911 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021
City	Virtual, Online
Period	23/06/21 → 25/06/21

Bibliographical note

Funding Information:
I thank Michael Fellows and Michael Hallett for discussions and earlier joint work on the parameterized complexity of Bandwidth, as reported in [5]. Some techniques in this paper are based upon techniques, underlying the results reported in [5]. I thank Marieke van der Wegen for discussions.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Funding

I thank Michael Fellows and Michael Hallett for discussions and earlier joint work on the parameterized complexity of Bandwidth, as reported in [5]. Some techniques in this paper are based upon techniques, underlying the results reported in [5]. I thank Marieke van der Wegen for discussions.

Keywords

Bandwidth
Caterpillars
Parameterized complexity
W-hierarchy
Weighted path emulation

Access to Document

10.1007/978-3-030-86838-3_2

Bodlaender2021_Chapter_ParameterizedComplexityOfBandwFinal published version, 294 KBLicence: Taverne

Cite this

Bodlaender, H. L. (2021). Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation. In L. Kowalik, M. Pilipczuk, & P. Rzazewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Revised Selected Papers (pp. 15-27). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12911 LNCS). Springer. https://doi.org/10.1007/978-3-030-86838-3_2

Bodlaender, Hans L. / Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation. Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Revised Selected Papers. editor / Lukasz Kowalik ; Michal Pilipczuk ; Pawel Rzazewski. Springer, 2021. pp. 15-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2a1ce00b0ffb437b9a1f72013bd1ca5e,

title = "Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation",

abstract = "In this paper, we show that Bandwidth is hard for the complexity class W[t] for all t∈ N, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path PN and integer M, decide if there exists a mapping of the vertices of PN to a path PM, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the pre-image of a vertex from PM equals an integer c. We show that Weighted Path Emulation, with c as parameter, is hard for W[t] for all t∈ N, and is strongly NP-complete. We also show that Directed Bandwidth is hard for W[t] for all t∈ N, for directed acyclic graphs whose underlying undirected graph is a caterpillar.",

keywords = "Bandwidth, Caterpillars, Parameterized complexity, W-hierarchy, Weighted path emulation",

author = "Bodlaender, {Hans L.}",

note = "Funding Information: I thank Michael Fellows and Michael Hallett for discussions and earlier joint work on the parameterized complexity of Bandwidth, as reported in [5]. Some techniques in this paper are based upon techniques, underlying the results reported in [5]. I thank Marieke van der Wegen for discussions. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021 ; Conference date: 23-06-2021 Through 25-06-2021",

year = "2021",

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

language = "English",

isbn = "9783030868376",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "15--27",

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

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

}

Bodlaender, HL 2021, Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation. in L Kowalik, M Pilipczuk & P Rzazewski (eds), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12911 LNCS, Springer, pp. 15-27, 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021, Virtual, Online, 23/06/21. https://doi.org/10.1007/978-3-030-86838-3_2

Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation. / Bodlaender, Hans L.
Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Revised Selected Papers. ed. / Lukasz Kowalik; Michal Pilipczuk; Pawel Rzazewski. Springer, 2021. p. 15-27 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12911 LNCS).

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

TY - GEN

T1 - Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation

AU - Bodlaender, Hans L.

N1 - Funding Information: I thank Michael Fellows and Michael Hallett for discussions and earlier joint work on the parameterized complexity of Bandwidth, as reported in [5]. Some techniques in this paper are based upon techniques, underlying the results reported in [5]. I thank Marieke van der Wegen for discussions. Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - In this paper, we show that Bandwidth is hard for the complexity class W[t] for all t∈ N, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path PN and integer M, decide if there exists a mapping of the vertices of PN to a path PM, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the pre-image of a vertex from PM equals an integer c. We show that Weighted Path Emulation, with c as parameter, is hard for W[t] for all t∈ N, and is strongly NP-complete. We also show that Directed Bandwidth is hard for W[t] for all t∈ N, for directed acyclic graphs whose underlying undirected graph is a caterpillar.

AB - In this paper, we show that Bandwidth is hard for the complexity class W[t] for all t∈ N, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path PN and integer M, decide if there exists a mapping of the vertices of PN to a path PM, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the pre-image of a vertex from PM equals an integer c. We show that Weighted Path Emulation, with c as parameter, is hard for W[t] for all t∈ N, and is strongly NP-complete. We also show that Directed Bandwidth is hard for W[t] for all t∈ N, for directed acyclic graphs whose underlying undirected graph is a caterpillar.

KW - Bandwidth

KW - Caterpillars

KW - Parameterized complexity

KW - W-hierarchy

KW - Weighted path emulation

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

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

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

M3 - Conference contribution

AN - SCOPUS:85115858447

SN - 9783030868376

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 15

EP - 27

BT - Graph-Theoretic Concepts in Computer Science

A2 - Kowalik, Lukasz

A2 - Pilipczuk, Michal

A2 - Rzazewski, Pawel

PB - Springer

T2 - 47th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2021

Y2 - 23 June 2021 through 25 June 2021

ER -

Bodlaender HL. Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation. In Kowalik L, Pilipczuk M, Rzazewski P, editors, Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Revised Selected Papers. Springer. 2021. p. 15-27. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-86838-3_2

Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this