{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:05:26Z","timestamp":1767139526360,"version":"build-2238731810"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T00:00:00Z","timestamp":1593734400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T00:00:00Z","timestamp":1593734400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GU 970\/7-1"],"award-info":[{"award-number":["GU 970\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>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\u00e8s 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.<\/jats:p>","DOI":"10.1007\/s00186-020-00718-6","type":"journal-article","created":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T12:04:55Z","timestamp":1593777895000},"page":"401-433","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Solutions for subset sum problems with special digraph constraints"],"prefix":"10.1007","volume":"92","author":[{"given":"Frank","family":"Gurski","sequence":"first","affiliation":[]},{"given":"Dominique","family":"Komander","sequence":"additional","affiliation":[]},{"given":"Carolin","family":"Rehs","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,3]]},"reference":[{"issue":"2","key":"718_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho AV, Garey MR, Ullman JD (1972) The transitive reduction of a directed graph. SIAM J Comput 1(2):131\u2013137","journal-title":"SIAM J Comput"},{"key":"718_CR2","volume-title":"Classes of directed graphs","year":"2018","unstructured":"Bang-Jensen J, Gutin G (eds) (2018) Classes of directed graphs. Springer, Berlin"},{"key":"718_CR3","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1002\/jgt.21775","volume":"77","author":"J Bang-Jensen","year":"2014","unstructured":"Bang-Jensen J, Maddaloni A (2014) Arc-disjoint paths in decomposable digraphs. J Graph Theory 77:89\u2013110","journal-title":"J Graph Theory"},{"key":"718_CR4","first-page":"230","volume-title":"Rewriting techniques and applications, volume 1232 of LNCS","author":"D Bechet","year":"1997","unstructured":"Bechet D, de Groote P, Retor\u00e9 C (1997) A complete axiomatisation of the inclusion of series-parallel partial orders. Rewriting techniques and applications, volume 1232 of LNCS. Springer, Berlin, pp 230\u2013240"},{"key":"718_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil DG, Lerchs H, Stewart-Burlingham L (1981) Complement reducible graphs. Discrete Appl Math 3:163\u2013174","journal-title":"Discrete Appl Math"},{"key":"718_CR6","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle B, Olariu S (2000) Upper bounds to the clique width of graphs. Discrete Appl Math 101:77\u2013114","journal-title":"Discrete Appl Math"},{"issue":"12","key":"718_CR7","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1016\/j.dam.2006.03.005","volume":"154","author":"C Crespelle","year":"2006","unstructured":"Crespelle C, Paul C (2006) Fully dynamic recognition algorithm and certificate for directed cographs. Discrete Appl Math 154(12):1722\u20131741","journal-title":"Discrete Appl Math"},{"key":"718_CR8","first-page":"1","volume-title":"Handbook of grammars and computing by graph transformation","author":"J Engelfriet","year":"1997","unstructured":"Engelfriet J, Rozenberg G (1997) Node replacement graph grammars. Handbook of grammars and computing by graph transformation. World Scientific, Singapore, pp 1\u201394"},{"key":"718_CR9","volume-title":"Graph theory","author":"R Gould","year":"2012","unstructured":"Gould R (2012) Graph theory. Dover Publications Inc, New York"},{"issue":"3","key":"718_CR10","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1007\/s10878-018-0262-1","volume":"36","author":"L Gourv\u00e8s","year":"2018","unstructured":"Gourv\u00e8s L, Monnot J, Tlilane L (2018) Subset sum problems with digraph constraints. J Comb Optim 36(3):937\u2013964","journal-title":"J Comb Optim"},{"key":"718_CR11","doi-asserted-by":"publisher","first-page":"35","DOI":"10.19139\/soic.v5i1.260","volume":"5","author":"F Gurski","year":"2017","unstructured":"Gurski F (2017) Dynamic programming algorithms on directed cographs. Stat Optim Inf Comput 5:35\u201344","journal-title":"Stat Optim Inf Comput"},{"key":"718_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2015.11.003","volume":"616","author":"F Gurski","year":"2016","unstructured":"Gurski F, Wanke E, Yilmaz E (2016) Directed NLC-width. Theor Comput Sci 616:1\u201317","journal-title":"Theor Comput Sci"},{"key":"718_CR13","doi-asserted-by":"crossref","unstructured":"Gurski F, Komander D, Rehs C (2019a) Computing digraph width measures on directed co-graphs. In: Proceedings of international symposium on fundamentals of computation theory (FCT), vol 11651 of LNCS. Springer, Berlin, pp 292\u2013305","DOI":"10.1007\/978-3-030-25027-0_20"},{"issue":"4","key":"718_CR14","doi-asserted-by":"publisher","first-page":"87","DOI":"10.3390\/a12040087","volume":"12","author":"F Gurski","year":"2019","unstructured":"Gurski F, Komander D, Rehs C (2019) Oriented coloring on recursively defined digraphs. Algorithms 12(4):87","journal-title":"Algorithms"},{"key":"718_CR15","doi-asserted-by":"crossref","unstructured":"Gurski F, Hoffmann S, Komander D, Rehs C, Rethmann J, Wanke E (2020) Computing directed steiner path covers for directed co-graphs. In: Proceedings of the conference on current trends in theory and practice of computer science (SOFSEM), vol 12011 of LNCS. Springer, Berlin, pp 556\u2013565","DOI":"10.1007\/978-3-030-38919-2_45"},{"key":"718_CR16","doi-asserted-by":"crossref","unstructured":"Gurski F, Rehs C (2018) Directed path-width and directed tree-width of directed co-graphs. In: Proceedings of the international conference on computing and combinatorics (COCOON), vol 10976 LNCS. Springer, Berlin, pp 255\u2013267","DOI":"10.1007\/978-3-319-94776-1_22"},{"issue":"1","key":"718_CR17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s00285-016-1084-3","volume":"75","author":"M Hellmuth","year":"2017","unstructured":"Hellmuth M, Stadler PF, Wieseke N (2017) The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations. J Math Biol 75(1):199\u2013237","journal-title":"J Math Biol"},{"issue":"1","key":"718_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.8.1.1","volume":"8","author":"DS Johnson","year":"1983","unstructured":"Johnson DS, Niemi KA (1983) On knapsacks, partitions, and a new dynamic programming technique for trees. Math Oper Res 8(1):1\u201314","journal-title":"Math Oper Res"},{"key":"718_CR19","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"Johnson T, Robertson N, Seymour PD, Thomas R (2001) Directed tree-width. J Comb Theory Ser B 82:138\u2013155","journal-title":"J Comb Theory Ser B"},{"key":"718_CR20","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/B:JOCO.0000021934.29833.6b","volume":"8","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U (2004) A new fully polynomial time approximation scheme for the knapsack problem. J Comb Optim 8:5\u201311","journal-title":"J Comb Optim"},{"key":"718_CR21","volume-title":"Knapsack problems","author":"H Kellerer","year":"2010","unstructured":"Kellerer H, Pferschy U, Pisinger D (2010) Knapsack problems. Springer, Berlin"},{"key":"718_CR22","first-page":"3","volume":"81","author":"EL Lawler","year":"1976","unstructured":"Lawler EL (1976) Graphical algorithms and their complexity. Math Centre Tracts 81:3\u201332","journal-title":"Math Centre Tracts"},{"key":"718_CR23","doi-asserted-by":"crossref","unstructured":"Le Gall F (2014) Powers of tensors and fast matrix multiplication. In: Proceedings of the international symposium on symbolic and algebraic computation (ISSAC). ACM, pp 296\u2013303","DOI":"10.1145\/2608628.2608664"},{"key":"718_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1287\/moor.4.3.215","volume":"4","author":"CL Monma","year":"1977","unstructured":"Monma CL, Sidney JB (1977) A general algorithm for optimal job sequencing with series-parallel constraints. Math Oper Res 4:215\u2013224","journal-title":"Math Oper Res"},{"key":"718_CR25","doi-asserted-by":"crossref","unstructured":"Nojgaard N, El-Mabrouk N, Merkle D, Wieseke N, Hellmuth M (2018) Partial homology relations\u2014satisfiability in terms of di-cographs. In: Proceedings of international computing and combinatorics conference (COCOON), volume 10976 of LNCS, Springer, New York pp 403\u2013415","DOI":"10.1007\/978-3-319-94776-1_34"},{"issue":"3","key":"718_CR26","first-page":"A161","volume":"30","author":"F Rendl","year":"1986","unstructured":"Rendl F (1986) Quadratic assignment problems on series-parallel digraphs. Z Oper Res Ser A-B 30(3):A161\u2013A173","journal-title":"Z Oper Res Ser A-B"},{"key":"718_CR27","doi-asserted-by":"crossref","unstructured":"Steiner G (1985) A compact labeling scheme for series-parallel graphs. Discrete Appl Math 11(3):281\u2013297","DOI":"10.1016\/0166-218X(85)90079-4"},{"key":"718_CR28","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes J, Tarjan RE, Lawler EL (1982) The recognition of series-parallel digraphs. SIAM J Comput 11:298\u2013313","journal-title":"SIAM J Comput"}],"updated-by":[{"DOI":"10.1007\/s00186-021-00757-7","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T00:00:00Z","timestamp":1657152000000}}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-020-00718-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-020-00718-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-020-00718-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T13:12:22Z","timestamp":1657199542000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-020-00718-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,3]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["718"],"URL":"https:\/\/doi.org\/10.1007\/s00186-020-00718-6","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,3]]},"assertion":[{"value":"24 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 July 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00186-021-00757-7","URL":"https:\/\/doi.org\/10.1007\/s00186-021-00757-7","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}