Key points are not available for this paper at this time.
Given a graph Formula: see text, a set of Formula: see text source-sink pairs Formula: see text Formula: see text and a profit bound Formula: see text, every edge Formula: see text has a cost Formula: see text, and every source-sink pair Formula: see text has a profit Formula: see text and a penalty Formula: see text. The Formula: see text-prize-collecting multicut problem (Formula: see text-PCMP) is to find a multicut Formula: see text such that the objective cost, which consists of the total cost of the edges in Formula: see text and the total penalty of the pairs still connected after removing Formula: see text, is minimized and the total profit of the disconnected pairs by removing Formula: see text is at least Formula: see text. In this paper, we firstly consider the Formula: see text-PCMP in paths, and prove that it is Formula: see text-hard even when Formula: see text for any Formula: see text. Then, we present a fully polynomial time approximation scheme (FPTAS) whose running time is Formula: see text for the Formula: see text-PCMP in paths. Based on this algorithm, we present an FPTAS whose running time is Formula: see text for the Formula: see text-PCMP in spider graphs, and an FPTAS whose running time is Formula: see text for the Formula: see text-PCMP in rings, respectively, where Formula: see text is the number of leaves of spider graph.
Liu et al. (Wed,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: