그래프 알고리즘을 찾고 : 그래프를 행복하게 만드는 방법?

Question

배경 : 아래에서 볼 수 있듯이

, 그림의 왼쪽에 무향 그래프가있다. 정점은 S1, S2 ... S6으로 표시되고 가장자리는 정점 사이의 선분으로 표시됩니다. 모든 가장자리에는 양수 또는 음수의 가중치 (가장자리 근처의 숫자)가 있습니다.

설명 : 그래프

는 단순한 사이클은 네거티브 에지 홀수 경우 충돌주기라고하며되는 조화 된 사이클 음수 에지 짝수 (또는 제로) 번호. 예를 들어 아래 그림의 왼쪽에있는 그래프에는 두 개의 충돌주기 (S1-S2-S3-S1 및 S2-S3-S4-S2)가 있고 다른주기는 일치합니다. 충돌하는 사이클이없는 경우 그래프는 행복이라고합니다.

목표 :

한편 비용 (제거 에지 가중치의 절대 값의 합)을 최저 보증 일부 모서리를 제거하여 그래프 행복하게. 예를 들어 아래 그림에서 가장자리 (빨간색 선 세그먼트)를 제거한 후에는 충돌하는 사이클이 없습니다. 그래서 그래프는 행복이되고, 비용이 문제가 NP-하드 최대 컷 감소하여 만 2

Answer 1

입니다. 최대 컷의 인스턴스가 주어지면 모든 엣지 가중치에 -1을 곱합니다. 이 문제의 제약은 모든 홀수 사이클을 제거하기 위해 에지가 제거되도록 지시한다. 즉, 최대 - 중량 이분 서브 그래프를 찾아야한다.

이 문제는 사실 2 라벨 고유 라벨 커버 문제와 동일합니다. 목표는 (i) 서로 다른 색상의 정점을 연결하는 양의 가장자리 (ii) 같은 색상의 정점을 연결하는 음의 가장자리에 대한 비용 합계를 최소화하도록 각 정점을 검정 또는 흰색으로 색칠하는 것입니다. 이러한 모든 모서리를 삭제하는 것은 원래의 문제에 대한 유효한 해결책입니다. 반대로, 삭제할 올바른 가장자리 집합이 주어지면 색칠을 결정할 수 있습니다. 나는 semidefinite 프로그래밍에 기반한 approximation 알고리즘을 기대한다 (그리고 relax은 branch와 bound를 위해 사용될 수있다).

그러나 조합 최적화에 익숙하지 않다면, 내가 제안 할 알고리즘은 정수 프로그래밍입니다. e을 지우면 x(e)을 1로 놓고, 그렇지 않으면 x(e)을 0으로합시다.

minimize sum_{edges e} cost(e) x(e) 
subject to 
for every simple cycle C with an odd number of negative edges, 
    sum_{edges e in C} x(e) >= 1 
for each edge e, x(e) in {0, 1} 

솔버가 대부분의 작업을 수행합니다. 문제는 내가 작성한 지수의 지수를 다루는 것입니다. 가장 간단한 것은 모든 간단한 사이클을 생성하고 솔버 전체 프로그램을 제공하는 것입니다. 또 다른 가능성은 제약 조건의 하위 집합을 사용하여 최적으로 풀고 솔루션이 실제로 유효한지 테스트하고 그렇지 않은 경우 하나 이상의 누락 된 제약 조건을 도입하는 것입니다. 테스트를 수행하려면, 양의 가장자리로 결합 된 정점이 동일한 색상을, 음의 가장자리로 결합 된 정점이 다른 색상을 갖도록 삭제되지 않은 하위 그래프를 두 가지 색상으로 표시합니다. 색깔 탐욕; 우리가 붙어 있다면 이상한 순환이 있습니다.

더 세련되면서 column generation이라는 기술을 통해 작성된 프로그램을 해결할 수 있습니다.

Answer 2

"Signed Graph Balancing"이라는 이름으로이 문제에 대해 solver을 작성했습니다. 이 알고리즘은 고정 소수점 알고리즘을 기반으로합니다.이 방법은 "Separator-based data reduction for signed graph balancing"이라는 종이에 설명되어 있습니다.