주어진 시작 정점 에서 주어진 끝 정점 이르기까지 지향 그래프의 간단한 경로 수를 근사하기위한 좋은 다항식 시간 알고리즘이 있다고 들었습니다 . 이 주제에 대한 좋은 언급을 아는 사람이 있습니까?
에스티
배경 : 일반 그래프에서 정확한 경로 수를 세는 것은 #P 완료이지만 문제에 대한 다항식 시간 근사가 존재할 수 있습니다. 나는 특히 임의의 근사치에 관심이 있습니다.
미리 감사드립니다.
답변
이 문제는 st 경로의 최대 길이에서 줄임으로써 NP-hard이어야합니다.
축소는 단순히 모든 모서리를 평행 모서리로 대체 합니다. (다중 그래프로 불편한 경우 각 모서리를 길이 2의 경로로 바꾸십시오.) 그 결과 길이 경로의 는 . 따라서 가 적당히 크면 원래 그래프에서 가장 긴 경로에 해당하는 항이 다른 모든 것을 지배하게됩니다 ( ). 거기에서 가장 긴 st 경로의 길이를 쉽게 복구 할 수 있습니다.
케이씨ℓ
ℓ
케이ℓ씨ℓ
케이
씨ℓ미디엄ㅏ엑스=1