티스토리 뷰

Statement. 하나의 Ground Set $E$ 상의 세 개의 매트로이드 $M_1$, $M_2$, $M_3$가 있다. 이 때, $M_1$, $M_2$, $M_3$ 모두에서 independent 한 $E$의 가장 큰 subset을 구하여라.

 

Proof of NP-Hardness

Hamiltonian path 문제로 부터의 reduction을 구성할 것이다.

$E$를 임의의 directed graph $G$의 edge set으로 놓자. $X \subseteq E$에 대해:

 - $X$가 $M_1$에서 independent 함을 $X$에 속하는 간선만을 볼 때, 각 정점의 in-degree가 $1$ 이하임으로 정의하자.

 - $X$가 $M_2$에서 independent 함을 $X$에 속하는 간선만을 볼 때, 각 정점의 out-degree가 $1$ 이상임으로 정의하자.

 - 마지막으로, $X$가 $M_3$에서 independent 함을 $X$에 속하는 간선들을 undirected로 볼 때 acyclic 함으로 정의하자.

그러면, $M_1, M_2, M_3$에서 independent 한 $E$의 가장 큰 subset을 구할 수 있다면, Hamiltonian path 문제를 해결할 수 있다. (해당 집합의 크기가 $|V(G)| - 1$인지만  확인해주면 된다.)

댓글
댓글쓰기 폼