Space Efficient Algorithms for Parameterised Problems
摘要
We study “space efficient” FPT algorithms for graph problems with limited memory. Let n be the size of the input graph and k be the parameter. We present algorithms that run in time \(f(k)\cdot n^{\mathcal{O}(1)}\) and use \(g(k)\cdot (\log n)^{\mathcal{O}(1)}\) working space, where f and g are functions of k alone, for k-Path, MaxLeaf SubTree and Multicut in Trees. These algorithms are motivated by big-data settings where very large problem instances must be solved, and using \(n^{O(1)}\) memory is prohibitively expensive. They are also theoretically interesting, since most of the standard methods tools, such as deleting a large set of vertices or edges, are unavailable, and we must develop different ways to tackle them.