최장 경로 문제

그래프 이론과 이론 컴퓨터 과학에서, 가장 긴 경로 문제는 주어진 그래프에서 최대 길이의 단순한 경로를 찾는 문제이다.경로는 반복되는 정점이 없는 경우 단순하다고 합니다. 경로의 길이는 에지 수로 측정하거나 (가중치 그래프에서) 에지 가중치의 합으로 측정할 수 있습니다.음수 가중치 사이클이 없는 그래프에서 다항식 시간 내에 해결할 수 있는 최단 경로 문제와 대조적으로, 최장 경로 문제는 NP-hard이며, 적어도 일정 길이의 경로가 존재하는지 여부를 묻는 문제의 결정 버전은 NP-complete입니다.이는 P = NP가 아니면 임의 그래프에 대해 결정 문제를 다항 시간 내에 해결할 수 없다는 것을 의미한다. 더 강한 경도 결과도 알려져 있어 근사하기가 어렵다는 것을 보여준다.그러나, 이것은 유향 비순환 그래프에 대한 선형 시간 솔루션을 가지고 있으며, 이것은 스케줄링 문제에서 중요한 경로를 찾는 데 중요한 응용 프로그램을 가지고 있다.

NP-경도

가중되지 않은 최장 경로 문제의 NP-경도 문제는 해밀턴 경로 문제의 감소를 사용하여 나타낼 수 있습니다. 그래프 G는 가장 긴 경로가 길이 n - 1인 경우에만 해밀턴 경로를 가집니다. 여기서 n은 G의 정점 수입니다. 해밀턴 경로 문제는 NP-완전이기 때문에, 이 감소는 해밀턴 경로 문제의 결정 버전을 보여줍니다.최장 경로 문제도 NP-완전입니다.이 결정 문제에서 입력은 그래프 G와 숫자 k입니다.G에 k 이상의 에지의 경로가 포함되어 있으면 원하는 출력이 "yes"이고, ^[1]그 이외의 경우에는 "yes

만약 가장 긴 경로 문제를 다항식 시간에 해결할 수 있다면, 가장 긴 경로를 찾아 그 길이를 숫자 k와 비교함으로써 이 결정 문제를 해결하는 데 사용될 수 있다.따라서 가장 긴 경로 문제는 NP-hard입니다."특정 그래프에 최소 k개의 모서리가 있는 단순한 경로가 있는가?"라는 질문은 NP-완전이다.^[2]

음수가 아닌 모서리 가중치를 갖는 가중 완전 그래프에서는 가장 긴 경로에 항상 모든 ^[3]정점이 포함되므로 가중된 가장 긴 경로 문제는 여행 세일즈맨 경로 문제와 동일합니다.

비순환 그래프

가중 그래프 G에서 주어진 두 정점 s와 t 사이의 가장 긴 경로는 모든 무게를 부정으로 바꿈으로써 G에서 도출된 그래프 -G의 가장 짧은 경로와 같다.따라서 -G에서 최단 경로를 찾을 수 있는 경우 ^[4]G에서도 최단 경로를 찾을 수 있습니다.

대부분의 그래프에서 이 변환은 -G에서 음의 길이의 주기를 생성하므로 유용하지 않습니다.그러나 G가 지향성 비순환 ^[4]그래프라면 음의 사이클을 생성할 수 없으며, -G의 최단 경로에 대한 선형 시간 알고리즘을 적용하여 선형 시간 내에 G의 가장 긴 경로를 찾을 수 있습니다.DAG의 경우 소스 정점에서 다른 모든 정점으로 가는 가장 긴 경로는 -G에서 최단 경로 알고리즘을 실행하여 얻을 수 있습니다.

마찬가지로, 주어진 DAG의 각 정점 v에 대해, v로 끝나는 가장 긴 경로의 길이는 다음 단계에 의해 구할 수 있다.

1. 지정된 DAG의 토폴로지 순서를 찾습니다.
2. DAG의 각 정점 v에 대해 토폴로지 순서로 들어오는 인접 라우터를 보고 해당 인접 라우터에 대해 기록된 최대 길이에 1을 더하여 v로 끝나는 가장 긴 경로의 길이를 계산합니다.v에 들어오는 인접 라우터가 없는 경우 v로 끝나는 가장 긴 경로의 길이를 0으로 설정합니다.어느 경우든 알고리즘의 후속 단계에서 액세스할 수 있도록 이 번호를 기록합니다.

이것이 완료되면 기록된 값이 가장 큰 정점 v에서 시작하여 기록된 값이 가장 큰 착신 인접 라우터로 반복적으로 후퇴하고 이와 같이 발견된 정점의 시퀀스를 반전시킴으로써 DAG 전체에서 가장 긴 경로를 얻을 수 있습니다.

이는 -G에서 최단 경로 알고리즘을 실행하는 것과 동일합니다.

크리티컬 패스

활동 세트를 스케줄링하기 위한 핵심 경로 방법은 정점이 프로젝트의 이정표를 나타내고 가장자리가 하나의 이정표 이후와 다른 이정표 이전에 수행되어야 하는 활동을 나타내는 방향 비순환 그래프의 구성을 포함한다. 각 가장자리는 해당 활동 w에 대한 시간의 추정치로 가중치를 부여한다.완성해야 할 것 같습니다.이러한 그래프에서 첫 번째 마일스톤에서 마지막 마일스톤까지의 가장 긴 경로는 프로젝트를 ^[4]완료하기 위한 총 시간을 나타내는 중요 경로입니다.

유향 비순환 그래프의 가장 긴 경로는 레이어 그래프 도면에서도 적용할 수 있다.유향 비순환 그래프 G의 각 정점 v를 v로 끝나는 가장 긴 경로의 길이인 레이어에 할당하면 가능한 ^[5]최소 레이어 수로 G에 레이어 할당이 이루어진다.

근사치

Björklund, Husfeldt & Khanna(2004)는 무가중 무방향 그래프에서 가장 긴 경로 문제는 "근사 ^[6]경도를 이해하는 것이 어려운 것으로 악명 높다"고 쓰고 있다.가장 좋은 다항식 시간 근사 알고리즘 이 사건을 알려진;0{\displaystyle \epsilon>0}, 그것은 2배 이내에서 가장 긴 길과 가까워지려고 가능하지 않는다는 약한 근사 비율, n/지수 함수 모든ϵ를 들어⁡(Ω(통나무⁡ n)){\displaystyle n(\Omega({\sqrt{\log n}}))}.[7]을 수행한다. (통나무) ${\displaystyle {n^{}}^{}}$ 1${\displaystyle {{}^{}}^{}}$- ${\$ ( \ $displaystyle$ 2 ^{ ( \ $log n$ )^$1$- \ $epsilon }$ 。다만$$, NP가 준다항식 결정론적 시간 내에 포함되지 않는 한, 이 ^[8]문제에 대해 알려진 근사 알고리즘과 큰 차이가 있다.

가중치가 없지만 지시된 그래프의 경우, 강한 비직접성 결과가 알려져 있다.지 않는 한 P는 NP마다 ϵ>;0이 문제에 n1− ϵ{\displaystyle n^{1-\epsilon}에}할 수 없으며 더 강하complexity-theoretic 가정 그것에 n/로그 2+ϵ⁡ n{\displaystylen/\log ^{2+\epsilon}n}에 가깝 수 없{\displaystyle \epsilon>0}. .[6]컬러 코딩 기술을 사용하여 로그 길이의 경로를 찾을 수 있지만, 이는 O${\displaystyle (n}$/ log${\displaystyle n}$n $)\displaystyle$ O$(n/\log$ n$)$^[9]의 근사 비율만 $제공$합니다.

파라미터화된복잡도

가장 긴 경로 문제는 경로의 길이로 매개 변수를 지정하면 고정 매개 변수를 추적할 수 있습니다.예를 들어, 다음 단계를 수행하는 알고리즘에 의해 입력 그래프의 크기(단, 경로 길이에서는 지수)에서 시간 선형으로 해결할 수 있습니다.

1. 그래프의 깊이 우선 검색을 수행합니다.d$\displaystyle$d를$$ 깊이 우선 검색 트리의 깊이로 $합니다{\displaystyle }$.
2. 깊이 우선 검색 트리의 루트 투 리프 경로 시퀀스를 검색에 의해 횡단된 순서대로 사용하여 경로$폭{\displaystyle }$ d\$displaystyle$ d$\}$를 사용하여 그래프의 경로 분해를 구성합니다.
3. 이 경로 분해에 동적 프로그래밍을 적용하여 $시간{\displaystyle }$ O${\displaystyle (}$ ${\displaystyle d}$! ${\displaystyle {\mathrm{}}^{}}$ $)(\displaystyle$ O$(d!2^{d}n$ 중 가장 긴 경로를 찾습니다. $여기$서$$n {\$displaystyle$ n$}$은 그래프 내의 정점 수입니다.

출력 패스의 길이가 d$(\displaystyle$ d$)$와 적어도 같기 때문에 실행 시간은 ${\displaystyle {\mathrm{}}^{}(!}$ ${\displaystyle {}^{}}$ ${\displaystyle )}$n )(\$displaystyle O(\ell!2$^{\$ell}$n$\})$로 $제한$됩니다.$여기$서 $"\displaystyle$ \$ell"$은 가장 긴 ^[10]경로의 길이입니다.색상 코딩을 사용하면 경로 길이에 대한 의존도를 단일 ^{[9][11][12][13]}지수 단위로 줄일 수 있습니다.유사한 동적 프로그래밍 기술은 가장 긴 경로 문제도 그래프의 트리 폭에 의해 매개 변수화되었을 때 고정 매개 변수 추적이 가능하다는 것을 보여준다.

유계 클리크 폭의 그래프의 경우, 최장 패스는 다항식 시간 동적 프로그래밍 알고리즘에 의해서도 해결할 수 있다.그러나 다항식의 지수는 그래프의 집단 폭에 의존하므로 이 알고리즘은 고정 매개 변수를 추적할 수 없습니다.clique-width로 파라미터화된 최장 경로 문제는 파라미터화된 복잡도 $클래스{\displaystyle }$W [ $]\displaystyle$ W[$1$]$$에는 적용되지 않습니다.이는 고정 파라미터 ^[14]추적 가능한 알고리즘이 존재할 가능성이 낮음을 나타냅니다.

그래프의 특수 클래스

트리에서 가장 긴 경로를 찾기 위한 선형 시간 알고리즘은 1960년대에 Dijkstra에 의해 제안되었고,^[15] 이 알고리즘의 공식적인 증거는 2002년에 발표되었다.또한, 가장 긴 경로는 가중 트리, 블록 그래프, 선인장,^[16] 초당 순열 ^[17]그래프 및 프톨레마이오스 ^[18]그래프에서 다항식 시간으로 계산될 수 있다.

구간 그래프의 클래스에는 동적 프로그래밍 ^[19]접근법을 사용하는 O${\displaystyle }$( ${\displaystyle {n\mathrm{}}^{}}$4$$) \ $displaystyle$O ( $n$^ { $4$) } - time$$ $알고리즘$이 알려져 있습니다.이 동적 프로그래밍 접근방식은 동일한 실행 $시간{\displaystyle }$ O${\displaystyle ({n\mathrm{}}^{}}$4$)\style$ O$(n$^{4$)\$display O(n$^{$4$)\}$를 갖는 더 큰 등급의 원형 호^[20] 그래프와 공존성 그래프(즉, 치환 그래프를 ^[21]포함)에 대한 다항식 시간 알고리즘을 얻기 위해 이용되었다.후자의 알고리즘은 비교가능성 그래프의 사전 깊이 우선 검색(LDFS) 정점^[22] 순서의 특수 속성을 기반으로 합니다.공비교 그래프의 경우 입력 공비교 ^[23]그래프의 보완에 의해 정의된 부분 순서 집합의 하세 다이어그램에 기초한 실행 $시간{\displaystyle }$ O${\displaystyle ({n\mathrm{}}^{}}$ 7$)(\style$ O$(n^{7)})$가 더 높은 대체 다항 시간 알고리즘도 알려져 있다.

또한, 가장 긴 경로 문제는 거리 종속 그래프와 같이 유계 트리 폭 또는 유계 클리크 폭의 모든 그래프 클래스에서 다항식 시간 내에 해결할 수 있다.마지막으로 분할 그래프, 원 그래프 및 평면 그래프와 같이 해밀턴 경로 문제가 NP-hard인 모든 그래프 클래스에서 NP-hard이다.

유도 비순환 그래프의 단순한 모델은 인용 네트워크를 나타내기 위해 Derek J. de Solla Price에 의해 개발된 Price 모델입니다.이는 일부 특성에 대한 분석 결과를 찾을 수 있을 정도로 단순합니다.예를 들어 네트워크에 추가된n번째 노드부터 네트워크 내의 첫 번째 노드까지의 가장 긴 경로의 ${\displaystyle \mathrm{길이}}$는 ln${\displaystyle (}$n )\$displaystyle \ln($n$)\}$ 입니다^[24].

「 」를 참조해 주세요.

• 가장 긴 경로와 그래프 색칠 사이의 이중성 관계인 갈라이-하세-로이-비타버 정리
• 가장 긴 무교차 기사 길
• Hypercube 그래프에서 가장 긴 유도 경로인 Snake-in-the-box
• 가장 긴 경로 길이를 분석적으로 찾을 수 있는 단순한 인용 네트워크 모델인 Price의 모델

레퍼런스

외부 링크

• 댄 배럿의 'Find the Longest Path' 노래