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)*poly(n) and use g(k)*polylog(n) 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 poly(n) 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 a develop different way to tackle them.

翻译：我们研究了图问题在有限内存下的“空间高效”FPT算法。设输入图的大小为n，参数为k。针对k-路径、最大叶子子树和树中的多割问题，我们提出了运行时间为f(k)*poly(n)且工作空间为g(k)*polylog(n)的算法，其中f和g仅为k的函数。这些算法的动机源于大数据场景，其中需要解决非常大的问题实例，而使用poly(n)内存成本过高。它们也具有理论上的趣味性，因为大多数标准方法工具（如删除大量顶点或边）无法使用，我们必须开发不同的处理方式。