{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T16:31:47Z","timestamp":1754152307257,"version":"3.41.2"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071417"],"award-info":[{"award-number":["12071417"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,8]]},"abstract":"<jats:p> 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. <\/jats:p>","DOI":"10.1142\/s0129054123460012","type":"journal-article","created":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T05:52:37Z","timestamp":1679550757000},"page":"767-780","source":"Crossref","is-referenced-by-count":0,"title":["The B-Prize-Collecting Multicut Problem in Paths, Spider Graphs and Rings"],"prefix":"10.1142","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1650-2625","authenticated-orcid":false,"given":"Xiaofei","family":"Liu","sequence":"first","affiliation":[{"name":"School of Information Science and Engineering, Yunnan University, Kunming, P. R. China"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mathematics and Statistics, Yunnan University, Kunming, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2023,3,22]]},"reference":[{"doi-asserted-by":"publisher","key":"S0129054123460012BIB001","DOI":"10.1016\/j.ejor.2008.05.006"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB002","DOI":"10.1137\/120868360"},{"volume-title":"Computers and Intractability: A Guide to the Theory of -Completeness","year":"1979","author":"Garey M. R.","key":"S0129054123460012BIB004"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB005","DOI":"10.1137\/S0097539793243016"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB006","DOI":"10.1007\/BF02523685"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB007","DOI":"10.1016\/j.jda.2005.07.005"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB008","DOI":"10.1016\/j.tcs.2020.07.014"},{"volume-title":"Integer Programming and Network Flows","year":"1969","author":"Hu T. C.","key":"S0129054123460012BIB009"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB010","DOI":"10.1016\/j.jcss.2007.06.019"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB011","DOI":"10.1007\/s00453-012-9701-z"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB012","DOI":"10.1007\/s00453-009-9317-0"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB013","DOI":"10.1016\/j.tcs.2006.09.018"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB014","DOI":"10.1007\/978-3-031-20350-3_21"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB015","DOI":"10.1051\/ro\/2015010"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB016","DOI":"10.1007\/s10878-020-00568-2"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB017","DOI":"10.1145\/321921.321934"},{"doi-asserted-by":"publisher","key":"S0129054123460012BIB018","DOI":"10.1016\/j.dam.2012.01.016"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123460012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T03:43:33Z","timestamp":1753155813000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123460012"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,22]]},"references-count":17,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10.1142\/S0129054123460012"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123460012","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,3,22]]}}}