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

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

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

(23)

• Univariate ideal membership parameterized by rank, degree, and number of generators
• A note on algebraic techniques for subgraph detection
• Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
• A regeneration scheme for generating extensions
• Extending and Implementing RASP
• scientific article; zbMATH DE number 1002576 (Why is no real title available?)
• The External Interface for Extending WASP
• Counting problems in parameterized complexity
• Approximate Counting of k -Paths: Simpler, Deterministic, and in Polynomial Space
• Patching colors with tensors
• Univariate ideal membership parameterized by rank, degree, and number of generators
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Parameterised counting in logspace
• Parameterized Counting and Cayley Graph Expanders
• The complexity of pattern counting in directed graphs, parameterised by the outdegree
• Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
• Decremental sensitivity oracles for covering and packing minors
• Determinantal sieving
• 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
• Deterministically counting k-paths and trees parameterized by treewidth in single-exponential time
• Fast exact algorithms using Hadamard product of polynomials

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)