TY - JOUR

T1 - On the minimum caterpillar problem in digraphs

AU - Okada, Taku

AU - Suzuki, Akira

AU - Ito, Takehiro

AU - Zhou, Xiao

PY - 2014

Y1 - 2014

N2 - 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 - 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 show that the problem is NP-hard for any fixed constant number of terminals with |K| ≥ 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with |K| ≥ 3. Finally, we 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|), and the hidden constant factor of the running time is just a single exponential of the treewidth.

AB - 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 - 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 show that the problem is NP-hard for any fixed constant number of terminals with |K| ≥ 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with |K| ≥ 3. Finally, we 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|), and the hidden constant factor of the running time is just a single exponential of the treewidth.

KW - Bounded treewidth graph

KW - Caterpillar

KW - Dynamic programming

KW - Graph algorithm

KW - Inapproximability

UR - http://www.scopus.com/inward/record.url?scp=84897677629&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84897677629&partnerID=8YFLogxK

U2 - 10.1587/transfun.E97.A.848

DO - 10.1587/transfun.E97.A.848

M3 - Article

AN - SCOPUS:84897677629

SN - 0916-8508

VL - E96-A

SP - 848

EP - 857

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 3

ER -