본 논문은 공격자와 방어자 간의 1라운드 적대적 게임으로 모델링된 고전적인 Most Vital Links 문제의 Stackelberg 변형을 연구합니다. 공격자는 소스 s와 싱크 t 사이의 흐름을 최대한 방해하기 위해 흐름 네트워크에서 최대 k개의 엣지를 전략적으로 제거하고, 그 후 방어자는 남은 흐름을 최적으로 재라우팅합니다. 이러한 공격자-방어자 상호작용을 포착하기 위해, 본 논문은 컷 비용을 가장 비싼 k개의 엣지를 제외하고 평가하는 새로운 수학적 모델인 할인 컷을 도입합니다. 이 모델은 Most Vital Links 문제를 일반화하고 새로운 알고리즘적 및 복잡성 이론적 속성을 밝힙니다. 다양한 형태의 할인 컷 문제를 분석하기 위한 통일된 알고리즘 프레임워크를 개발했으며, 일반 그래프에서 대부분의 변형이 NP-완전임에도 불구하고, 입력이 경계 속 그래프로 제한될 때, 즉 교통 및 인프라 네트워크와 같은 많은 실제 네트워크를 포함하는 관련 클래스에서 모든 할인 컷 문제에 대한 다항 시간 해결 가능성을 입증합니다.
