지시 된 그래프의 N 개의 주어진 경로에서 K 분리 된 경로를 찾는 것을 증명하십시오.

Question

문제점 : 지시 된 그래프 G (v, e)와 정수 K에 n 개의 경로가 주어지지 않고 공통 노드를 통과하지 못하도록 K 경로를 찾습니다.

주어진 문제가 NP 완료에있는 것임을 증명합니다.

나는 문제가 np에 있다는 것을 증명할 수있었습니다.힌트는이 문제에 대한 독립적 인 세트 문제의 다항식 시간 감소를 해결해야한다는 것입니다.

Answer 1

$ \ mathsf {np} $ 에서 문제의 회원은 사소한 것입니다. $ \ mathsf {np} $ - Hard 그래프 $ g= (v, e) $ $ | v |= n $ 및 정수 $ k $ .

그래프 $ h= (v ', e') $ 여기서 $ v '= v \ cup \ {x_ u, v} \, : \, (u, v) \ \ \ \ span> 및 $ e '= v'\ times v '$ < / span>.

각 $ u \ in v $ u \ in v $ $ v_1, v_2, \ dots, v_h $ $ u $ > $ g $ 및 경로 $ P_U=langle u, x_ {u, v_1}, x_ {u, v_2}, \ dots, x_ {u, v_h} \ rangle $ $ h $ . $ \ mathcal {p}={p_u \, : \, u \ in v \} $

.

대부분의 $ k $ 에서 $ g $ , $ | \ mathcal {p} '와 함께 하위 세트 $ \ mathcal> p}'$ \ mathcal> $ \ mathcal> {$ \ span>의 경로가 쌍으로 vertex-disjoint가되도록

더 정확하게, $ s $ 은 $ g $ 의 독립적 인 세트입니다. class="Math-Container"> $ \ {P_U \, : \, u \ in s \} $ 은 $ h의 쌍방향 정점 분리 경로 모음입니다. $ 및 $ \ mathcal {p} '$ 이 $ h $ , $ \ {u \, : \, p_u \ in \ mathcal {p} '\} $ 은 독립적 인 세트입니다 < SPAN 클래스="수학 용기"> $ G $ .