구조적 제약 하의 전화 방송 문제
전화 방송 문제는 주어진 그래프의 특정 시작 정점에서 메시지를 모든 정점으로 전파하는 최소 라운드 수를 찾는 문제입니다. 각 라운드에서 정보를 아는 정점은 인접한 모르는 정점 하나에게 메시지를 전달할 수 있습니다. 본 연구는 이 문제의 구조적 매개변수 복잡도를 탐구합니다. 기존 연구를 확장하여, 본 연구는 전화 방송 문제가 유한한 트리 깊이를 갖는 그래프와 경로 숲에서 하나의 정점만 제거하면 되는 선인장 그래프에서도 NP-완전임을 보이며 NP-난이도 결과를 강화합니다. 이러한 난이도에 대응하여, 정점 무결성(vertex integ…