The Complexity of L(p, q)-Edge-Labelling

Berthe, Gaétan; Martin, Barnaby; Paulusma, Daniël; Smith, Siani

doi:10.1007/s00453-023-01120-4

The Complexity of L(p, q)-Edge-Labelling

Berthe, Gaétan; Martin, Barnaby; Paulusma, Daniël; Smith, Siani

Authors

Gaétan Berthe

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

Siani Smith

Abstract

The L(p, q)-EDGE-LABELLING problem is the edge variant of the well-known L(p, q)-LABELLING problem. It is equivalent to the L(p, q)-LABELLING problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p, q)-EDGE-LABELLING was only partially classified in the literature. We complete this study for all p,q≥0 by showing that whenever (p,q)≠(0,0) , the L(p, q)-EDGE-LABELLING problem is NP-complete. We do this by proving that for all p,q≥0 except p=q=0 , there is an integer k so that L (p , q)-EDGE-k -LABELLING is NP-complete.

Citation

Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, https://doi.org/10.1007/s00453-023-01120-4

Journal Article Type	Article
Acceptance Date	Mar 21, 2023
Online Publication Date	Apr 13, 2023
Publication Date	2023
Deposit Date	Apr 17, 2023
Publicly Available Date	Apr 14, 2024
Journal	Algorithmica
Print ISSN	0178-4617
Electronic ISSN	1432-0541
Publisher	Springer
Peer Reviewed	Peer Reviewed
DOI	https://doi.org/10.1007/s00453-023-01120-4
Public URL	https://durham-repository.worktribe.com/output/1175939

Files

Accepted Journal Article (639 Kb)
PDF

Copyright Statement
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s00453-023-01120-4