The Complexity of Knapsack in Graph Groups

DOI10.4230/LIPICS.STACS.2017.52MaRDI QIDQ4636653zbMATH OpenFDO

Authors Markus Lohrey, Georg Zetzsche

Publication date 19 April 2018

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

zbMATH Keywords

decision problems in group theorygraph groupsknapsacksubset sum

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: Myasnikov et al. have introduced the knapsack problem for arbitrary finitely generated groups. In previous work, the authors proved that for each graph group, the knapsack problem can be solved in $mathsfNP$. Here, we determine the exact complexity of the problem for every graph group. While the problem is $mathsf{TC}^0$-complete for complete graphs, it is $mathsfLogCFL$-complete for each (non-complete) transitive forest. For every remaining graph, the problem is $mathsfNP$-complete.

Recommendations

• Knapsack in graph groups
• Knapsack in graph groups, HNN-extensions and amalgamated products
• Knapsack problems in groups
• A note on the solution of group knapsack problems
• scientific article; zbMATH DE number 7139161
• A relation between the knapsack and group knapsack problems
• Knapsack problems in products of groups
• Knapsack in hyperbolic groups
• Knapsack in hyperbolic groups
• Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups

Cited in

(12)

• A relation between the knapsack and group knapsack problems
• Knapsack in graph groups
• Closure properties of knapsack semilinear groups
• Knapsack problems for wreath products
• Knapsack in graph groups, HNN-extensions and amalgamated products
• Knapsack in hyperbolic groups
• Knapsack in hyperbolic groups
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• Knapsack problems for NL
• Disjointness, inclusion, and regularity of -rational trace languages (extended abstract)
• On tropical knapsack-type problems
• The stochastic weighted complexity of a group covering of a digraph

This page was built for publication: The Complexity of Knapsack in Graph Groups

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