Subset Sum Problems with Special Digraph Constraints

Frank Gurski (), Dominique Komander and Carolin Rehs
Additional contact information
Frank Gurski: Institute of Computer Science, Algorithmics for Hard Problems Group
Dominique Komander: Institute of Computer Science, Algorithmics for Hard Problems Group
Carolin Rehs: Institute of Computer Science, Algorithmics for Hard Problems Group

A chapter in Operations Research Proceedings 2019, 2020, pp 339-346 from Springer

Abstract: 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 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.

Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:oprchp:978-3-030-48439-2_41

Ordering information: This item can be ordered from
http://www.springer.com/9783030484392

DOI: 10.1007/978-3-030-48439-2_41

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().