BipArtite 그래프를 Subgraphs로 분할하는 알고리즘

Question

BipArtite 그래프를 특정 제약 조건으로 하위 그래프로 분할하는 알고리즘을 찾고 있습니다. 기존 알고리즘이 내 문제를 해결하는지 확실하지 않습니다.

Nodes가 고객이 고객 ( $ C $ ) 및 서비스 ( $ s $ < / span>). 나는 이것을 여러 개의 작은 서브 그래프로 분할하여 각 하위 그래프의 서비스 양을 최대 숫자 $ n $ 으로 제한하고 싶습니다. 불행히도 그래프 연결이 너무 높기 때문에 연결이 끊어진 하위 그래프를 찾는 것은 충분하지 않으므로 서비스를 중복해야합니다.

공식적으로, 나는 다음과 같은 서브 그래프를 원한다 :

• 각 고객 $ c \ in c $ 은 정확히 하나의 하위 그래프
에 나타납니다.
• 모든 모서리는 정확히 하나의 하위 그래프 (고객이 고객이 나타나는 것)
에 나타납니다.
• 각 서비스 $ s $ s \ in s $ \ subgraphs (Split를 돕기 위해 서비스를 중복하는 서비스를 중복하는 것이 괜찮습니다)
• 각 하위 그래프는 대부분의 $ n $ 서비스 ( $ n $ )는 주어진 상수입니다. 하나의 고객에게 연결된 가장 많은 서비스 수보다 큰 수의 서비스보다 큰 경우)
• 하위 그래프는 가능한 한 많은 고객이되어야합니다 (이 제한없이 각 고객을 자신의 Subgraph에 서비스 사본과 함께 배치함으로써 사소한 작동 가능). 그것은 공식적으로 입증 된 것이 아니라 휴리스틱 일 수 있습니다.

누구나이 작업을 수행하기위한 알고리즘을 제안 할 수 있습니까? 노드의 수는 거대하지 않습니다 (대략 1000 명의 고객, 100 개의 서비스가 5 개 이하의 서비스와 연결)이므로 무차별 강제에 접근하거나 BIG-O 확장이 나쁜 사람들이 적합 할 수 있습니다.

Answer 1

그것은 np-hard일지도 모른다.

하나의 그럴듯한 접근 방식은 SAT Solver 또는 ILP Solver를 사용하는 것입니다.대부분의 $ m $ subgraphs에서 원한다고 결정한다고 가정 해보십시오.그런 다음 $ x_ {i, k}, y_ {j, k} $ 을 가질 수 있습니다. 고객 $ i$ 은 subgraph $ k $ 및 service $ j $ 은 subgraph $ k $ .요구 사항에 따라 제약 조건 (절)을 얻은 다음 SAT Solver 또는 ILP Solver에게 가능한 해결책을 찾을 수 있습니다.최악의 사례 실행 시간은 지수입니다.이것은 귀하의 상황에서 충분히 잘 작동하지 않을 수도 있습니다.