지정된 수의 정점을 사용하여 최소 절단을 위한 효율적인 알고리즘

Question

꼭짓점이 있는 그래프를 생각해 보세요. $V$ 그리고 가장자리 $E$.최소 컷 문제의 표준 버전은 다음의 파티션을 찾는 것입니다. $V$ (비어 있지 않은) 하위 집합으로 $C$ 그리고 그 보완 $\bar{C}$ 사이에 가는 모서리의 수를 최소화하기 위해 $C$ 그리고 $\bar{C}$.이 문제를 다항식 시간에 해결하는 알고리즘이 알려져 있습니다.내 질문은 다음과 같은 제약 조건을 추가로 지정하면 어떻게 되는지입니다. $ | C | = n $ 일부 $n < |V|$?즉, 우리는 다음의 집합을 찾고 싶습니다. $n$ 정점의 나머지 정점에 연결되는 최소 수의 가장자리로 정점을 만듭니다.이 경우에도 효율적인 알고리즘이 있습니까?나는 이 문제가 다항식 시간에 공식적으로 해결 가능한지(내 추측으로는 그럴 것임)에 대한 질문과 실제로 어떤 알고리즘이 가장 좋은지에 대한 질문 모두에 관심이 있습니다.

Answer 1

을 위한 $n= \frac {|V|} 2$, 이는 최소 이등분이라고 하며 NP-하드입니다.존재한다 $O(\log^{3/2}n)$-근사: "최소 이등분의 다대수 근사".

관심이 있으시면 보다 일반적인 문제는 동일한 크기의 여러 구성 요소로 분할되는 것이며 이를 균형 그래프 분할이라고 합니다.2개 이상의 부품에 대해 P=NP가 아니면 유한 근사가 존재하지 않습니다. "균형 그래프 분할"(Andreev, Rakke), 답이 0인지 효율적으로 확인할 수 없기 때문입니다.

부품이 반드시 정확하게 균형을 이루고 있지 않은 경우(약간의 불균형은 허용됨) $O(\로그n)$- 근사 알고리즘이 존재합니다: "트리와 애플리케이션의 균형 잡힌 파티션".

---

일부 알고리즘(또한 확인 https://en.wikipedia.org/wiki/Graph_partition 및 다음 논문의 "참조" 섹션):

• 다양한 맛의 지역 검색:일부 분할로 시작한 다음 부품 간 정점을 교환하여 절단을 최소화하려고 합니다.예:각 정점에 대해 "이득"을 계산하고(다른 부분으로 이동하면 개선됨) 정점을 최대 이득으로 교환합니다.장점은 다른 알고리즘 다음에 적용할 수 있다는 것입니다.

• 스펙트럼 분할(예: 스펙트럼 그래프 이론 및 그래프 분할):라플라시안 행렬의 두 번째 고유벡터를 사용하여 분할을 근사화합니다(예:가장 작은 것을 움직여서 $|V|/2$ 첫 번째 부분과 일치합니다).놀랍게도 잘 작동합니다.그러나 불균형한 이등분을 원하는 경우(예: $1:2$ 대신에 $1:1$).

• 선형 임베딩: "선형 임베딩을 통한 분산 균형 파티셔닝".모든 정점 쌍에 대한 합을 최소화하면서 정점을 1차원 배열에 포함합니다.그들 사이의 거리에 가장자리의 무게를 곱한 것입니다.그런 다음 이 배열을 필요한 크기의 연속적인 청크로 분할합니다.내 경험으로는 그렇게 잘 작동하지 않았습니다.

• (광고) 우리 논문: "투영 된 그라디언트 하강을 통한 다차원 균형 그래프 파티셔닝" ", 여기서 우리는 최소 이등분을 찾기 위해 경사하강법을 사용했습니다.각 정점에 대해 정점이 첫 번째 부분에 속할 확률을 대략적으로 나타내는 변수를 도입하고 컷을 최소화하면 2차 함수의 제한된 최적화로 줄어듭니다.실제로는 미세 조정된 로컬 검색으로 인해 성능이 약간 떨어지지만 여러 균형 제약 조건이 있는 경우에는 정말 잘 작동합니다.

스펙트럼 방법을 제외하면 이들 방법 모두 그래프를 임의의 비율로 분할하는 데 쉽게 적용할 수 있습니다.

표준 솔버도 있습니다: 카힙, 혼혈아.제 경험상 KaHIP은 꽤 괜찮았습니다.그래도 임의의 크기로 분할하는 것을 지원하는지 잘 모르겠습니다.