
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

On the Minimum Caterpillar Problem in Digraphs
Taku OKADA Akira SUZUKI Takehiro ITO Xiao ZHOU
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E97A
No.3
pp.848857 Publication Date: 2014/03/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E97.A.848
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Algorithms and Data Structures Keyword: bounded treewidth graph, caterpillar, dynamic programming, graph algorithm, inapproximability,
Full Text: PDF(1.1MB) >>Buy this Article
Summary:
Suppose that each arc in a digraph D = (V,A) has two costs of nonnegative 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 NPhard 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 lineartime 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.

