Extensor-coding

DOI10.1145/3188745.3188902MaRDI QIDQ5230285zbMATH OpenOpenAlexFDO

Authors Cornelius Brand, Holger Dell, Thore Husfeldt

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-pathapproximate countingexterior algebra

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Approximation algorithms (68W25) Enumeration in graph theory (05C30) Paths and cycles (05C38) Exterior algebra, Grassmann algebras (15A75)

Abstract: We devise an algorithm that approximately computes the number of paths of length $k$ in a given directed graph with $n$ vertices up to a multiplicative error of $1pmvarepsilon$. Our algorithm runs in time $varepsilo{n}^{-2}{4}^k(n+m)operatornamepoly(k)$. The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic $2^{k}cdotoperatornamepoly(n)$ time algorithm to find a $k$-path in a given directed graph that is promised to have few of them. Our results and techniques generalize to the subgraph isomorphism problem when the subgraphs we are looking for have bounded pathwidth. Finally, we also obtain a randomized algorithm to detect $k$-multilinear terms in a multivariate polynomial given as a general algebraic circuit. To the best of our knowledge, this was previously only known for algebraic circuits not involving negative constants.

Recommendations

• Patching colors with tensors
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• scientific article; zbMATH DE number 3876620
• Faster Algebraic Algorithms for Path and Packing Problems
• Color-coding

Cited in

(21)

• Fast exact algorithms using Hadamard product of polynomials
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Patching colors with tensors
• A note on algebraic techniques for subgraph detection
• Parameterised counting in logspace
• Counting problems in parameterized complexity
• A regeneration scheme for generating extensions
• scientific article; zbMATH DE number 7561312 (Why is no real title available?)
• A simple inclusion-exclusion based algorithm for (k, n)-MLC and related problems
• Parameterized applications of symbolic differentiation of (totally) multilinear polynomials
• Detecting and counting small subgraphs, and evaluating a parameterized Tutte polynomial: lower bounds via toroidal grids and Cayley graph expanders
• Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
• Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
• Determinantal sieving
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Parameterized Counting and Cayley Graph Expanders
• The External Interface for Extending WASP
• Univariate ideal membership parameterized by rank, degree, and number of generators
• Decremental sensitivity oracles for covering and packing minors
• scientific article; zbMATH DE number 1002576 (Why is no real title available?)
• Extending and Implementing RASP

This page was built for publication: Extensor-coding

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