...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete optimization >Paths of bounded length and their cuts: Parameterized complexity and algorithms
【24h】

Paths of bounded length and their cuts: Parameterized complexity and algorithms

机译：有界长度的路径及其切割：参数化的复杂度和算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length l of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both k and l and hardness results when the parameter is only one of k and l. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.
机译：我们研究了两个问题系列的参数化复杂度：有界长度不相交路径问题和有界长度切割问题。根据门格尔定理，对于单个源，单个目标路径，这两个问题在无穷大情况下是等效的（并且计算上很容易）。但是，在有界情况下，它们在组合上是截然不同的，并且都是NP困难的，甚至是近似的。我们的结果表明，当我们针对这些问题的参数化复杂性研究这些问题时，会出现更为精致的景观。为此，我们考虑了两个问题（边/顶点不相交）的所有变体的几个参数化（关于最大路径长度l，最大路径数k或切口的大小以及输入图的树宽）。路径或切割，有向/无向）。当同时用k和l进行参数设置时，我们提供FPT算法（适用于所有变体），而当参数仅是k和l之一时，则提供硬度结果。我们的结果表明，有界长度的不相交路径变体在结构上比有界长度的剪切路径更难。同样，当通过输入图的树宽进行参数化时，边缘变体似乎比其顶点不相交的对象更难。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号