Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K is contained in V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first study the complexity status of the problem with respect to the number of terminals: the problem is solvable in polynomial time for any digraph with two terminals, while it is NP-hard for three terminals. We then give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|).
展开▼
机译：假设有向图D =（V，A）中的每个弧都有两个非负整数的开销，称为脊柱开销和叶子开销。毛毛虫是一棵有向树，由一条（脊弧的）有向路径和叶顶点组成，每条顶点都通过一个正好进入的弧（叶弧）入射到有向路径。对于给定的端子组K包含在V中，我们研究在D中找到履带的问题，使得它在K中包含所有端子，并且其总成本最小化，其中履带中每个弧的成本取决于是否用作书脊弧或叶弧。在本文中，我们首先研究了与终端数有关的问题的复杂性状态：对于具有两个终端的任何有向图，该问题可以在多项式时间内解决，而对于三个终端，则该问题是NP难的。然后，我们给出一种线性时间算法来解决有界树宽的有向图的问题，其中，有向图D的树宽被定义为D的底层图的树宽。即使| K |，我们的算法也以线性时间运行= O（| V |）。
展开▼
