In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph \(G = (V, E)\) , a subset \(U \subseteq E\) of vulnerable edges, two vertices \(s, t \in V\) , and integers k and \(\ell \) . The task is to decide whether there exists a subgraph H of G with total cost at most  \(\ell \) such that, after the removal of any k vulnerable edges, H still contains an s-t-path. We study whether Fault-Tolerant Path is fixed-parameter tractable (FPT) and whether it admits a polynomial kernel under various parameterizations. Our choices of parameters include the number of vulnerable edges in the input graph, the number of safe (i.e., invulnerable) edges in the input graph, the budget \(\ell \) , the minimum number of safe edges in any optimal solution, the minimum number of vulnerable edges in any optimal solution, the required redundancy k, and natural above- and below-guarantee parameterizations. We provide an almost complete description of the complexity landscape of FTP for these parameters.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

When Does FTP Become FPT?

  • Matthias Bentert,
  • Fedor V. Fomin,
  • Petr A. Golovach,
  • Laure Morelle

摘要

In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph \(G = (V, E)\) , a subset \(U \subseteq E\) of vulnerable edges, two vertices \(s, t \in V\) , and integers k and \(\ell \) . The task is to decide whether there exists a subgraph H of G with total cost at most  \(\ell \) such that, after the removal of any k vulnerable edges, H still contains an s-t-path. We study whether Fault-Tolerant Path is fixed-parameter tractable (FPT) and whether it admits a polynomial kernel under various parameterizations. Our choices of parameters include the number of vulnerable edges in the input graph, the number of safe (i.e., invulnerable) edges in the input graph, the budget \(\ell \) , the minimum number of safe edges in any optimal solution, the minimum number of vulnerable edges in any optimal solution, the required redundancy k, and natural above- and below-guarantee parameterizations. We provide an almost complete description of the complexity landscape of FTP for these parameters.