Solutions for subset sum problems with special digraph constraints

DOI10.1007/S00186-020-00718-6MaRDI QIDQ2216192zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Dominique Komander, Carolin Rehs

Publication date 15 December 2020

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2004.04712

zbMATH Keywords

digraph constraintdirected co-graphsseries-parallel digraphssubset sum problem

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Dynamic programming (90C39)

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 Gourves 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.

Recommendations

• Subset sum problems with special digraph constraints
• Subset sum problems with digraph constraints
• On variations of the subset sum problem
• A Fast Approximation Algorithm For The Subset-Sum Problem
• An exact algorithm for the subset sum problem

Cites work

• A compact labelling scheme for series-parallel graphs
• A complete axiomatisation for the inclusion of series-parallel partial orders
• Arc-disjoint paths in decomposable digraphs
• Classes of directed graphs
• Complement reducible graphs
• Computing digraph width measures on directed co-graphs (extended abstract)
• Computing directed Steiner path covers for directed co-graphs (extended abstract)
• Directed NLC-width
• Directed path-width and directed tree-width of directed co-graphs
• Directed tree-width
• Fully dynamic recognition algorithm and certificate for directed cographs
• Handbook of Graph Grammars and Computing by Graph Transformation
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 6271443 (Why is no real title available?)
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• On Knapsacks, Partitions, and a New Dynamic Programming Technique for Trees
• Oriented coloring on recursively defined digraphs
• Partial homology relations -- satisfiability in terms of di-cographs
• Powers of tensors and fast matrix multiplication
• Quadratic assignment problems on series-parallel digraphs
• Sequencing with Series-Parallel Precedence Constraints
• Subset sum problems with digraph constraints
• The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
• The Recognition of Series Parallel Digraphs
• The Transitive Reduction of a Directed Graph
• Upper bounds to the clique width of graphs

Cited in

(4)

• Subset sum problems with digraph constraints
• Subset sum problems with special digraph constraints
• The knapsack problem with special neighbor constraints
• The knapsack problem with special neighbor constraints on directed co-graphs

This page was built for publication: Solutions for subset sum problems with special digraph constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216192)