Limits and applications of group algebras for parameterized problems

Ioannis Koutis, Ryan Williams

Research output: Chapter in Book/Report/Conference proceedingConference contribution

80 Scopus citations

Abstract

The algebraic framework introduced in [Koutis, Proc. of the 35 th ICALP 2008] reduces several combinatorial problems in parameterized complexity to the problem of detecting multilinear degree-k monomials in polynomials presented as circuits. The best known (randomized) algorithm for this problem requires only O *(2 k ) time and oracle access to an arithmetic circuit, i.e. the ability to evaluate the circuit on elements from a suitable group algebra. This algorithm has been used to obtain the best known algorithms for several parameterized problems. In this paper we use communication complexity to show that the O *(2 k ) algorithm is essentially optimal within this evaluation oracle framework. On the positive side, we give new applications of the method: finding a copy of a given tree on k nodes, a spanning tree with at least k leaves, a minimum set of nodes that dominate at least t nodes, and an m-dimensional k-matching. In each case we achieve a faster algorithm than what was known. We also apply the algebraic method to problems in exact counting. Among other results, we show that a combination of dynamic programming and a variation of the algebraic method can break the trivial upper bounds for exact parameterized counting in fairly general settings.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings
Pages653-664
Number of pages12
EditionPART 1
DOIs
StatePublished - 2009
Externally publishedYes
Event36th International Colloquium on Automata, Languages and Programming, ICALP 2009 - Rhodes, Greece
Duration: Jul 5 2009Jul 12 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5555 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other36th International Colloquium on Automata, Languages and Programming, ICALP 2009
Country/TerritoryGreece
CityRhodes
Period7/5/097/12/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Limits and applications of group algebras for parameterized problems'. Together they form a unique fingerprint.

Cite this