2026-07-23T08:46:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6981 2024-03-06T10:39:14Z ddc:004 open_access

The Complexity of Knapsack in Graph Groups Lohrey, Markus Zetzsche, Georg knapsack subset sum graph groups decision problems in group theory Myasnikov et al. have introduced the knapsack problem for arbitrary finitely generated groups. In LohreyZ16 the authors proved that for each graph group, the knapsack problem can be solved in NP. Here, we determine the exact complexity of the problem for every graph group. While the problem is TC^0-complete for complete graphs, it is LogCFL-complete for each (non-complete) transitive forest. For every remaining graph, the problem is NP-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Lohrey and Georg Zetzsche 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.52 urn:nbn:de:0030-drops-69810 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.52 eng https://creativecommons.org/licenses/by/3.0/legalcode