Solutions for subset sum problems with special digraph constraints

DOI10.1007/S00186-020-00718-6zbMATH Open1454.90075arXiv2004.04712OpenAlexW3038179692MaRDI QIDQ2216192FDOQ2216192

Authors: Frank Gurski, Dominique Komander, Carolin Rehs 

Publication date: 15 December 2020

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

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.

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

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

zbMATH Keywords

subset sum problemdirected co-graphsseries-parallel digraphsdigraph constraint

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

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

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)