Waring Rank, Parameterized and Exact Algorithms
Author:
- 1 November 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 806-823
Abstract
We show that the Waring rank (symmetric tensor rank) of a certain family of polynomials has intimate connections to the areas of parameterized and exact algorithms, generalizing some well-known methods and providing a concrete approach to obtain faster approximate counting and deterministic decision algorithms. To illustrate the amenability and utility of this approach, we give an algorithm for approximately counting subgraphs of bounded treewidth, improving on earlier work of Alon, Dao, Hajirasouliha, Hormozdiari, and Sahinalp. Along the way we give an exact answer to an open problem of Koutis and Williams and sharpen a lower bound on the size of perfectly balanced hash families given by Alon and Gutner.Keywords
All Related Versions
This publication has 38 references indexed in Scilit:
- Finding and Counting Vertex-Colored SubtreesAlgorithmica, 2011
- On the rank of a symmetric formJournal of Algebra, 2011
- Faster algorithms for finding and counting subgraphsJournal of Computer and System Sciences, 2011
- Finding paths of length k in timeInformation Processing Letters, 2009
- Biomolecular network motif counting and discovery by color codingBioinformatics, 2008
- Algorithm Engineering for Color-Coding with Applications to Signaling Pathway DetectionAlgorithmica, 2007
- Color-codingJournal of the ACM, 1995
- Inclusion and exclusion algorithm for the Hamiltonian path problemInformation Processing Letters, 1993
- Dynamic programming meets the principle of inclusion and exclusionOperations Research Letters, 1982
- A note on the graph isomorphism counting problemInformation Processing Letters, 1979