Complexity of the multiobjective minimum weight minimum stretch spanner problem

Fritz Bökler () and Henning Jasper ()
Additional contact information
Fritz Bökler: Osnabrück University
Henning Jasper: Osnabrück University

Mathematical Methods of Operations Research, 2024, vol. 100, issue 1, No 4, 65-83

Abstract: Abstract In this paper, we take an in-depth look at the complexity of a hitherto unexplored multiobjective minimum weight minimum stretch spanner problem; or in short multiobjective spanner (MSp) problem. The MSp is a multiobjective generalization of the well-studied minimum t-spanner problem. This multiobjective approach allows to find solutions that offer a viable compromise between cost and utility—a property that is usually neglected in singleobjective optimization. Thus, the MSp can be a powerful modeling tool when it comes to, e.g., the planning of transportation or communication networks. This holds especially in disaster management, where both responsiveness and practicality are crucial. We show that for degree-3 bounded outerplanar instances the MSp is intractable and computing the non-dominated set is BUCO-hard. Additionally, we prove that if $${\textbf{P}} \ne \textbf{NP}$$ P ≠ NP , the set of extreme points cannot be computed in output-polynomial time, for instances with unit costs and arbitrary graphs. Furthermore, we consider the directed versions of the cases above.

Keywords: Multiobjective optimization; Graph spanners; Output-sensitive complexity; Extreme points; Parametric optimization (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00186-024-00850-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:100:y:2024:i:1:d:10.1007_s00186-024-00850-7

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-024-00850-7

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().