License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.52
URN: urn:nbn:de:0030-drops-69810
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6981/
Go to the corresponding LIPIcs Volume Portal

Lohrey, Markus ; Zetzsche, Georg

The Complexity of Knapsack in Graph Groups

pdf-format:
LIPIcs-STACS-2017-52.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{lohrey_et_al:LIPIcs:2017:6981,
  author =	{Markus Lohrey and Georg Zetzsche},
  title =	{{The Complexity of Knapsack in Graph Groups}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte ValleĢe},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6981},
  URN =		{urn:nbn:de:0030-drops-69810},
  doi =		{10.4230/LIPIcs.STACS.2017.52},
  annote =	{Keywords: knapsack, subset sum, graph groups, decision problems in group theory}
}

Keywords: knapsack, subset sum, graph groups, decision problems in group theory
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI