경로, 스파이더 그래프 및 링에서의 B-프라이즈 수집 멀티컷 문제

그래프 Formula: see text, 소스-싱크 쌍의 집합 Formula: see text 및 이익 제한 Formula: see text가 주어졌을 때, 모든 엣지 Formula: see text는 비용 Formula: see text를 가지며, 모든 소스-싱크 쌍 Formula: see text는 이익 Formula: see text와 벌금 Formula: see text를 가집니다. Formula: see text-프라이즈 수집 멀티컷 문제(Formula: see text-PCMP)는 목표 비용을 최소화하는 멀티컷 Formula: see text을 찾는 것이며, 이 목표 비용은 Formula: see text의 엣지 총 비용과 Formula: see text 제거 후에도 여전히 연결된 쌍의 총 벌금으로 구성됩니다. 소스-싱크 쌍이 Formula: see text를 제거하였을 때의 총 이익은 적어도 Formula: see text이어야 합니다. 본 논문에서 우리는 먼저 경로에서 Formula: see text-PCMP를 고려하고, 그것이 Formula: see text일 때조차 Formula: see text-어려운 것임을 증명합니다. 그런 다음, 우리는 경로에서 Formula: see text-PCMP에 대한 실행 시간이 Formula: see text인 완전 다항식 근사 알고리즘(FPTAS)을 제시합니다. 이 알고리즘을 바탕으로, 스파이더 그래프에서 Formula: see text-PCMP에 대한 실행 시간이 Formula: see text인 FPTAS와 링에서 Formula: see text-PCMP에 대한 실행 시간이 Formula: see text인 FPTAS를 각각 제시합니다. 여기서 Formula: see text는 스파이더 그래프의 리프 수입니다.