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

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

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, 85(11), 3406-3429. 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-11
• 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
• Volume: 85
• Issue: 11
• Pages: 3406-3429
• DOI: https://doi.org/10.1007/s00453-023-01120-4
• Public URL: https://durham-repository.worktribe.com/output/1175939