Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/288447 
Year of Publication: 
2020
Citation: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 92 [Issue:] 2 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 401-433
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
The subset sum problem is one of the simplest and most fundamental NP-hard problems in combinatorial optimization. We consider two extensions of this problem: The subset sum problem with digraph constraint (SSG) and subset sum problem with weak digraph constraint (SSGW). In both problems there is given a digraph with sizes assigned to the vertices. Within SSG we want to find a subset of vertices whose total size does not exceed a given capacity and which contains a vertex if at least one of its predecessors is part of the solution. Within SSGW we want to find a subset of vertices whose total size does not exceed a given capacity and which contains a vertex if all its predecessors are part of the solution. SSG and SSGW have been introduced recently by Gourvès et al. who studied their complexity for directed acyclic graphs and oriented trees. We show that both problems are NP-hard even on oriented co-graphs and minimal series-parallel digraphs. Further, we provide pseudo-polynomial solutions for SSG and SSGW with digraph constraints given by directed co-graphs and series-parallel digraphs.
Subjects: 
Subset sum problem
Digraph constraint
Directed co-graphs
Series-parallel digraphs
JEL: 
C85
C39
C69
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.