Scholarlink

The Minimum Tree Cut/Paste Distance problem is a well-known NP-hard problem in computational biology. However, its fixed-parameter tractability with respect to the distance remains an open problem. Within the paper, we study a simplified variant of the problem, called the Spanning Forest Isomorphism on Tree problem (alternatively called the Tree Assembly problem). Its input contains a rooted target tree \(T^*\) and a rooted forest F, and the goal is to decide whether F is a spanning forest of \(T^*\) . The problem has been shown to be NP-hard and fixed-parameter tractable with respect to the number k of trees in F. Within our investigation, we present several FPT algorithms for the problem and its general variant, where n is the size of the input instance.

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

Parameterized Algorithms for the Spanning Forest Isomorphism (or Containment) on Tree Problems

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Jingyi Liu,
  • Xian Chen,
  • Yicheng Zheng,
  • Jianxin Wang,
  • Feng Shi

摘要

The Minimum Tree Cut/Paste Distance problem is a well-known NP-hard problem in computational biology. However, its fixed-parameter tractability with respect to the distance remains an open problem. Within the paper, we study a simplified variant of the problem, called the Spanning Forest Isomorphism on Tree problem (alternatively called the Tree Assembly problem). Its input contains a rooted target tree \(T^*\) and a rooted forest F, and the goal is to decide whether F is a spanning forest of \(T^*\) . The problem has been shown to be NP-hard and fixed-parameter tractable with respect to the number k of trees in F. Within our investigation, we present several FPT algorithms for the problem and its general variant, where n is the size of the input instance.