Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials

DOI10.1016/J.JCSS.2018.01.004MaRDI QIDQ1747489zbMATH OpenOpenAlexFDO

Authors G. Gutin, Felix Reidl, Magnus Wahlström, Meirav Zehavi

Publication date 8 May 2018

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.03698, https://eprints.bbk.ac.uk/id/eprint/24757/6/24757.pdf

zbMATH Keywords

deterministicfixed-parameter tractableKirchoff matricesPfaffianspolynomial space

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: In recent years, several powerful techniques have been developed to design {em randomized} polynomial-space parameterized algorithms. In this paper, we introduce an enhancement of color coding to design deterministic polynomial-space parameterized algorithms. Our approach aims at reducing the number of random choices by exploiting the special structure of a solution. Using our approach, we derive the following deterministic algorithms (see Introduction for problem definitions). 1. Polynomial-space $O^{\ast }(3.86^k)$-time (exponential-space $O^{\ast }(3.41^k)$-time) algorithm for {sc $k$-Internal Out-Branching}, improving upon the previously fastest {em exponential-space} $O^{\ast }(5.14^k)$-time algorithm for this problem. 2. Polynomial-space $O^{\ast }((2e{)}^{k+o(k)})$-time (exponential-space $O^{\ast }(4.32^k)$-time) algorithm for {sc $k$-Colorful Out-Branching} on arc-colored digraphs and {sc $k$-Colorful Perfect Matching} on planar edge-colored graphs. To obtain our polynomial space algorithms, we show that $(n,k,alphak)$-splitters ($alphage1$) and in particular $(n,k)$-perfect hash families can be enumerated one by one with polynomial delay.

Recommendations

• Patching colors with tensors
• Mixing Color Coding-Related Techniques
• Narrow sieves for parameterized paths and packings
• Faster graph coloring in polynomial space
• Faster graph coloring in polynomial space

Cites work

• A linear vertex kernel for maximum internal spanning tree
• A Remark on Stirling's Formula
• Abusing the Tutte matrix: an algebraic instance compression for the K-set-cycle problem
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Color-coding
• Complexity results for rainbow matchings
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• Determinant sums for undirected Hamiltonicity
• Digraphs
• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Directed tree-width
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Fast algorithms for parameterized problems with relaxed disjointness constraints
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• scientific article; zbMATH DE number 3047763 (Why is no real title available?)
• LIMITS and applications of group algebras for parameterized problems
• Minimum leaf out-branching and related problems
• Mixing Color Coding-Related Techniques
• Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey
• Narrow sieves for parameterized paths and packings
• On a set of almost deterministic k-independent random variables
• On complexity of minimum leaf out-branching problem
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• Reducing to independent set structure -- the case of k-internal spanning tree
• Representative families: a unified tradeoff-based approach
• Sharp separation and applications to exact and parameterized algorithms
• Some Matching Problems for Bipartite Graphs
• Spotting trees with few leaves
• Trimmed Moebius inversion and graphs of bounded degree

Cited in

(4)

• Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms
• Patching colors with tensors
• Approximate Counting of k-Paths: Deterministic and in Polynomial Space
• Parameterized applications of symbolic differentiation of (totally) multilinear polynomials

This page was built for publication: Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials

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