100개의 점을가진 연결된 그래프G가 있습니다.
그중 5개의 특별한 점 ABCDE가 있습니다.
G의 특별한점들을 모두 연결하는 G의 연결된 서브그래프를 찾는 가장 효율적인 (선의 개수가 최소가 되게 연결하는) 방법을 찾는 문제입니다.
제가 생각한 방법은 이렇습니다.
특별한점과 이웃한 점들에 가중치를둡니다.
가령,
A만 이웃한 점은 가중치 1, C와D에 이웃한 점은 가중치 2
이런식입니다.
그다음, 특별한 점중 임의로 하나를 잡습니다. 이를 시작점이라고 하겠습니다. 이후 규칙에 따라 움직입니다.
1. 시작점에 이웃한 점들중 가중치가 가장 큰 점으로 이동합니다. 이동한 점에서 가중치가 가장 큰 이웃점으로의 연결을 반복합니다.
2-1. 만약 이웃한 점 중 특별한 점이 있다면,가중치를 무시하고 해당 특별한 점으로 이동합니다.
2-2. 만일 이웃점 중 특별한 점이 2개 이상이면 일단 모두 연결합니다.연결된 점들의 이웃점중, 가중치가 가장 큰 점 하나를 찾아서 이동합니다.
3. 특별한 점에 도착하면, 해당 점과 이웃한 점들의 가중치를 1만큼 줄입니다.
4-1. 가중치가 같고,0이 아닌 이웃점들이 있다면, 아무곳이나갑니다.
4-2. 주위의 모든 점이 가중치가 0이라면, 왔던길을 한칸 돌아갑니다.
5. 다섯개의 특별한 점이 모두 연결되었다면 멈춥니다.
대충 이런식으로 진행하면 아래 그림과 같은 그래프는 가능하더군요.
하지만 몇가지 문제가 생겼습니다.
1. 설명이 너무 복잡합니다.
2. 위 그림은 예제로써 적은 수의 점을 사용한것입니다. 만일 100개의 점이 있고, 그중 5개만 특별한 점이라면 4-2번을 무한번 반복함이 명백합니다.
첫번째 문제점은 제 어휘력 탓이므로 그냥 넘길 수 있지만,
두번째 문제점은 너무나 치명적인 약점입니다.
두번째 문제점은, 아무리 생각해봐도 고칠 수가 없습니다.
이 아이디어는 그낭 없던걸로 하고, 다시 새로 생각해보는 게 정답일까요?
n개의 정점으로 구성된 그래프에서 어떤 정점들의 subset S가 주어졌을때, S를 포함하는 edge 개수가 최소가 되는 연결된 부분그래프를 찾는 문제는 유명한 Steiner tree problem인데, 일반적으로는 각 edge에 nonnegative weight까지 줌. 이 일반적인 문제는 NP-hard로 잘 알려져있기 때문에 이것을 다항시간 안에 쉽게 푸는 방법은 없음.
모든 edge의 weight을 1로 둔 unweighted case 또한 쉽게 NP-hard임을 알 수 있는데, 왜냐하면 weight이 양의 정수라고 항상 가정할 수 있고, at most polynomial이라는것도 항상 가정할 수 있고, weight이 k이면 각 edge를 path of length k로 subdivide하면 unweighted case의 instance로 바꿀 수 있기 때문임.
다만 여기에 또다른 parameter k를 추가로 두어서, 예를 들어서 S의 크기를 k 이하로 제한한다면, 어떤 함수 f(k)와 상수 c가 존재하여 Steiner tree problem은 f(k)n^c의 시간에 해결될 수 있음. 이런 류의 문제를 Fixed parameter tractable(FPT)에 속한다고 하는데, 즉 k가 상수라면 Steiner tree problem은 다항시간 안에 해결이 가능함.
https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230010302