Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth

DOI10.1145/3186898zbMATH Open1457.05110arXiv1511.01379OpenAlexW4230551286WikidataQ129724156 ScholiaQ129724156MaRDI QIDQ4554362

Author name not available (Why is that?)

Publication date: 13 November 2018

Published in: (Search for Journal in Brave)

Abstract: We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial time, however the exponent of the polynomial is large. Therefore, our main goal is to construct algorithms with running time of the form $extrmpoly(k)cdotn$ or $extrmpoly(k)cdotnlogn$, where $k$ is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like $O(n^{1/c})$ for some small constant $c$. Our results include: -- an algorithm for computing the determinant and the rank of an $nimesn$ matrix using $O(k^{3}cdotn)$ time and arithmetic operations; -- an algorithm for solving a system of linear equations using $O(k^{3}cdotn)$ time and arithmetic operations; -- an $O(k^{3}cdotnlogn)$-time randomized algorithm for finding the cardinality of a maximum matching in a graph; -- an $O(k^{4}cdotnlo{g}^{2}n)$-time randomized algorithm for constructing a maximum matching in a graph; -- an $O(k^{2}cdotnlogn)$-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we give an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph $G$ and integer $k$, runs in time $O(k^{7}cdotnlogn)$ and either correctly reports that the treewidth of $G$ is larger than $k$, or constructs a tree decomposition of $G$ of width $O(k^2)$.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth

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