독립 지배 집합(Independent Dominating Sets)을 위한 3-근사 알고리즘: Siriaisa 알고리즘

Frank Vega

Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA

vega.frank@gmail.com

초록 (Abstract)

최소 독립 지배 집합(Minimum Independent Dominating Set, MIDS) 문제, 즉 가장 작은 극대 독립 집합(maximal independent set)을 찾는 문제는 강력하게 근사가 불가능한(strongly inapproximable) 그래프 최적화 문제입니다. $P=NP$가 아닌 한, 어떤 다항 시간 알고리즘도 1보다 큰 고정된 상수 인자 내에서 이 문제를 근사할 수 없습니다. 본 논문에서는 현재의 Siriaisa v0.0.1 구현을 제시합니다. 이 알고리즘은 순차적 가젯(sequential gadget)을 통해 임의의 무방향 그래프를 최대 차수가 4 이하인 보조 그래프로 축소하고, 선형 계획법 완화(LP relaxation)를 해결하며, 우선순위 극대 독립 집합 스윕(priority maximal-independent-set sweep)을 통해 분수 해(fractional solution)를 반올림합니다. 그런 다음 알고리즘은 검증된 가장 작은 독립 지배 집합을 반환하기 전에 세 가지 확장된 후보(lifted candidates)를 테스트합니다. 알고리즘의 비-LP 부분은 최악의 경우 $O(n+m+N\log N+M)$ 시간 내에 실행됩니다. 이 알고리즘은 항상 유효한 독립 지배 집합을 반환합니다. 축소된 그래프에 대해 Boppana/Halldórsson 경계인 $(\Delta+1)/2 = 2.5 \le 3$에 의해 보장되는 성분별 차수 4 투영(componentwise degree-four projection) 및 폴백 인증서(fallback certificates)가 유지되는 한, 이 알고리즘은 증명 가능한 3-근사(3-approximation) 알고리즘입니다. 실험에서는 적대적 DIMACS 스위트(adversarial DIMACS suite)에 대해 Siriaisa v0.0.1을 사용하여 정확한 SciPy MILP 모델과 비교하였으며, 관찰된 최대 비율은 2.000이었습니다.

서론 (Introduction)

무방향 그래프 $G=(V,E)$의 _독립 지배 집합(independent dominating set)_은 독립적이면서 동시에 지배적인 집합 $D \subseteq V$를 의미합니다. 즉, $D$의 어떤 두 정점도 인접하지 않으며, $V \setminus D$의 모든 정점은 $D$ 내에 적어도 하나의 이웃을 가집니다. 동등하게 말하면, $D$는 극대 독립 집합(maximal independent set)입니다. 최소 독립 지배 집합 문제는 $i(G)$로 표기되는 최소 카디널리티(cardinality)를 가진 그러한 집합을 찾는 문제입니다.

MIDS는 일반적인 최소 지배 집합 (Minimum Dominating Set) 문제보다 근사하기 훨씬 더 어렵습니다. Irving은 $P=NP$가 아닌 한, 어떤 고정된 상수 $K>1$에 대해서도 다항 시간 (polynomial-time) 알고리즘이 $K$ 배율을 보장할 수 없음을 증명했습니다. 이후 Halldórsson은 동일한 최소 극대 독립 지배 집합 (minimum maximal independent set) 정식화에 대한 하한 (lower bound)을 더욱 강화했습니다. 결과적으로, 3과 같은 임의의 다항 시간 유니버설 상수 배율 (universal constant-factor) 보장은 $P=NP$를 의미하게 됩니다.

현재의 Siriaisa 알고리즘은 이러한 장벽을 염두에 두고 읽어야 합니다. 이 알고리즘은 모든 입력에 대해 유효한 독립 지배 집합을 제공하며, 차수 4로 축소된 그래프 (degree-four reduced graph)에 대한 Boppana/Halldórsson 하한을 기반으로 증명된 3-근사 인증서 (3-approximation certificate)를 제공합니다.

현재 알고리즘

구현은 siriaisa/algorithm.py에 있으며, LP 기반 근사 (LP-based approximation)는 siriaisa/approx.py에 있습니다.

높은 수준에서, find_independent_dominating_set(graph)는 다음 단계들을 수행합니다:

1. 전처리 (Preprocessing). 자기 루프 (self-loops)를 제거하고 고립된 정점 (isolated vertices)을 분리합니다. 고립된 정점은 모든 독립 지배 집합에 반드시 포함되어야 합니다.
2. 차수 4 축소 (Degree-Four Reduction). 각 연결 성분 (connected component)에 대해, 각 정점을 보조 정점들의 사이클 (cycle of auxiliary vertices)로 교체하는 순차적 가젯 (sequential gadget)을 적용하여, 보조 그래프 $H$의 최대 차수가 $\Delta(H) \le 4$가 되도록 보장합니다.
3. LP 유도 MIS (LP-Guided MIS). $H$ 상에서 MIDS의 LP 완화 (LP relaxation)를 풀고, 우선순위 순서에 따라 탐욕적 극대 독립 집합 (greedy Maximal Independent Set, MIS) 스윕 (sweep)을 실행합니다.
4. 리프팅 및 검증 (Lifting and Verification). 보조 솔루션을 두 가지 극성 (polarities)으로 원래의 성분에 다시 투영(project)하고, 직접적인 폴백 (fallback)을 테스트합니다. 검증된 후보 중 가장 작은 것을 반환합니다.

핵심적인 LP 유도 MIS 루틴은 다음과 같이 구현됩니다:

def mids_lp(G: nx.Graph) -> MIDSResult:
    """
    최소 독립 지배 집합 근사치를 계산합니다.
...

메인 컴포넌트 선택기 (main component selector)는 이 루틴을 호출하고 세 가지 후보를 처리합니다:

def _find_component_solution(component_graph):
    """하나의 연결 성분(connected component)에 대해 검증된 가장 작은 Siriaisa 후보를 반환합니다."""
    auxiliary = _degree_four_auxiliary_graph(component_graph)

차수 4 가젯 (The Degree-Four Gadget)

구현에서의 차수 4 변환(degree-four transformation)은 순차적으로 이루어집니다. 원래의 정점 $u$가 처리될 때, 작업 그래프(working graph) 내의 현재 이웃들이 나열됩니다. 정점 $u$는 제거됩니다. 각 이웃 $v_i$에 대해, 보조 정점 $(u, i)$가 생성되어 $v_i$와 연결됩니다. 또한 이 정점은 순환적으로 이전 이웃인 $v_{i-1}$과도 연결됩니다.

다음 Markdown으로 그려진 가젯은 차수가 4인 정점 $u$에 대한 국소적 교체(local replacement)를 보여줍니다:

Original Component:               Auxiliary Graph (Local View):

        v_0                               v_0
...

보조 그래프(auxiliary graph)에서 보조 정점 $a_i$는 원래의 이웃인 $v_i$ 및 $v_{i-1}$과 연결됩니다. 이러한 순환적 교차(cyclic interleaving)는 보조 그래프 내 모든 정점의 최대 차수(maximum degree)가 엄격하게 4 이하로 제한되도록 보장하며, 이는 런타임(runtime)에 검증됩니다.

근사 분석 (Approximation Analysis)

이 분석은 Boppana와 Halldórsson의 핵심 통찰에 기반합니다: 모든 극대 독립 집합(maximal independent set, MIS)은 유효한 MIDS(독립적이고 지배적인 집합)이며, 탐욕적(greedy) MIS 스윕(sweep)은 비가중치 그래프(unweighted graphs)에 대해 다음과 같은 결과를 도출합니다:

$$|MIDS| \le \frac{\Delta+1}{2} |OPT|$$

순차적 가젯이 보조 그래프 $H$의 최대 차수를 $\Delta(H) \le 4$로 명시적으로 줄여주기 때문에, $H$에 대한 탐욕적 MIS는 다음과 같은 근사 비율(approximation ratio)을 보장합니다:

$$\frac{4+1}{2} = 2.5$$

$2.5 \le 3$이므로, 이는 3-근사(3-approximation) 조건을 엄격히 충족합니다. 따라서 더 타이트하지만 취약한 경계(tighter, more fragile bound)를 요구하지 않고도, 견고하고 보수적인 3-근사 인증(3-approximation certificate)을 제시할 수 있습니다.

공식 인증 정리(formal certificate theorem)에 따르면, 모든 연결 성분(connected component)이 차수 4 투영 인증(degree-four projection certificate) 또는 폴백 인증(fallback certificate)을 만족할 경우, 반환된 집합 $D$는 다음을 만족합니다:

$|D| \le 3 \cdot i(G)$.

Irving의 비근사성 정리(inapproximability theorem)에 의해, 이 3-근사 인증(3-approximation certificate)에 대한 보편적인 다항 시간 증명은 $P=NP$임을 의미하게 됩니다.

실행 시간 분석 (Runtime Analysis)

표현된 그래프의 정점 수를 $n=|V|$, 간선 수를 $m=|E|$라 하고, 차수 4 축소(degree-four reduction) 이후 보조 그래프(auxiliary graph)의 정점 및 간선 수를 $N$과 $M$이라 합시다. Siriaisa의 최악 실행 시간은 다음과 같습니다:

$O(n+m+N\log N+M+T_{\mathrm{LP}}(N,M))$,

여기서 $T_{\mathrm{LP}}(N,M)$은 선형 계획법(LP) 솔버가 사용하는 시간입니다. 각 구성 요소는 다음과 같습니다:

• 전처리 및 고립 정점 처리 (Preprocessing and isolated-vertex handling): $O(n+m)$.
• 차수 4 변환 (Degree-four transformation): $O(n+m)$; 모든 원래의 인접 간선은 상수 개의 보조 인접 관계(auxiliary incidences)만을 기여합니다.
• LP 완화 풀이 (LP relaxation solve): $T_{\mathrm{LP}}(N,M)$.
• LP 값에 따른 정점 정렬 (Sorting vertices by LP value): $O(N\log N)$.
• 탐욕적 최대 독립 집합(MIS) 스윕 및 검증 (Greedy MIS sweep and verification): $O(N+M)$.

따라서 LP 완화(LP relaxation)가 다항 시간 LP 알고리즘에 의해 풀릴 때, Siriaisa는 다항 시간(polynomial time) 내에 동작합니다.

실험 (Experiments)

저장소의 experiments 디렉토리에는 작은 DIMACS 그래프들로 구성된 적대적 테스트 세트(adversarial suite)가 포함되어 있습니다. 각 인스턴스는 희소 저차수 그래프(sparse low-degree graphs), 밀집 그래프(dense graphs), 이분 극단 그래프(bipartite extremal graphs), 그리고 투영-극성 함정(projection-polarity traps)을 포함하여 Siriaisa에서 사용되는 메커니즘들을 대상으로 하는 구조적 테스트입니다. Siriaisa는 SciPy의 MILP 인터페이스를 통해 풀이된 정확한 이진 정수 계획법(binary integer program)과 비교됩니다.

적대적 DIMACS 결과 (Adversarial DIMACS results)

적대적 DIMACS 결과 (Adversarial DIMACS results)

| DIMACS 파일 | 그래프 클래스 | nnn | mmm | Δ\DeltaΔ | ∣DS∣|D_S|∣DS​∣ | i(G)i(G)i(G) | Ratio |
|---|---|---:|---:|---:|---:|---:|---:|
| adv_clique_k8.dimacs | Clique K8K_8K8​ | 8 | 28 | 7 | 1 | 1 | 1.000 |
| adv_complete_bipartite_k4_4.dimacs | Complete bipartite K4,4K_{4,4}K4,4​ | 8 | 16 | 4 | 4 | 4 | 1.000 |
| adv_crown_5.dimacs | Crown graph on 10 vertices | 10 | 20 | 4 | 2 | 2 | 1.000 |
| adv_cycle_c12.dimacs | Cycle C12C_{12}C12​ | 12 | 12 | 2 | 4 | 4 | 1.000 |
| adv_double_star_4_4.dimacs | Double star DS(4,4)DS(4,4)DS(4,4) | 10 | 9 | 5 | 5 | 5 | 1.000 |
| adv_grid_3x4.dimacs | Grid 3×43\times43×4 | 12 | 17 | 4 | 4 | 4 | 1.000 |
| adv_ladder_2x5.dimacs | Ladder 2×52\times52×5 | 10 | 13 | 3 | 3 | 3 | 1.000 |
| adv_lollipop_k5_p5.dimacs | Lollipop K5K_5K5​ -- P5P_5P5​ | 10 | 15 | 5 | 3 | 3 | 1.000 |
| adv_path_p12.dimacs | Path P12P_{12}P12​ | 12 | 11 | 2 | 4 | 4 | 1.000 |
| adv_projection_fallback_6.dimacs | Projection-polarity graph | 6 | 6 | 3 | 3 | 3 | 1.000 |
| adv_ratio2_trap_7.dimacs | Ratio-2 trap | 7 | 11 | 5 | 4 | 2 | 2.000 |
| adv_star_k1_11.dimacs | Star K1,11K_{1,11}K1,11​ | 12 | 11 | 11 | 1 | 1 | 1.000 |

The 가장 큰 관측 정확 비율은 adv_ratio2_trap_7.dimacs에서 2.000입니다. 이 인스턴스는 현재 구현에 의해 최적으로 해결되지 않았기 때문에, 최적 결과만 담긴 표보다 근사성 주장을 더 심각하게 테스트합니다. 나머지 적대적 클래스들은 이번 실행에서 최적으로 해결되었습니다.

진단: testMatrix16

파일 benchmarks/testMatrix16은 DIMACS 헤더 p edge 6 6과 간선 목록 (1,2),(1,3),(1,4),(2,4),(3,4),(3,6)(1,2),(1,3),(1,4),(2,4),(3,4),(3,6)(1,2),(1,3),(1,4),(2,4),(3,4),(3,6)입니다. 정점 5는 고립되어 있으므로 모든 독립 지배 집합에 포함됩니다. 비고립 성분은 {1,2,3,4,6}에 의해 유도됩니다.

비고립 성분(non-isolated component)에 대해 내부 3-후보 선택기(three-candidate selector)를 실행하면 다음과 같은 결과가 나옵니다:

이러한 동작은 왜 Siriaisa가 $S_1S_1S_2$와 $S_2S_2S_2$를 수락하기 전에 원래의 성분(original component)에서 이를 검증하는지를 보여줍니다. 수락된 전역 집합(global set) {2,5,6}은 최적(optimal)이므로, 정확한 비율은 1이며 이는 3보다 훨씬 낮습니다.

결론

우리는 가중치가 없는 최소 독립 지배 집합(Minimum Independent Dominating Set, MIDS)을 위한 Siriaisa 구현을 설명했습니다. 이 알고리즘은 고립 정점 전처리(isolated-vertex preprocessing), 순차적 차수-4 가젯(sequential degree-four gadget), 선형 계획법 완화(LP relaxation), LP 유도 최대 독립 집합 반올림(LP-guided maximal-independent-set rounding), 그리고 3-후보 검증 단계(three-candidate verification step)를 결합합니다. 반환되는 모든 집합은 직접적인 검증을 통해 독립적이고 지배적임이 확인됩니다. LP 완화가 다항 시간 LP 솔버(polynomial-time LP solver)에 의해 해결될 때, 최악의 실행 시간은 다항 시간(polynomial time)입니다.

근사(approximation) 주장은 이례적으로 강력한 결과를 내포하고 있습니다. 만약 성분 인증(component certificates)이 보편적으로 성립한다면, Siriaisa는 MIDS에 대한 다항 시간 3-근사(3-approximation) 알고리즘이 됩니다. $P=NP$가 아닌 한 MIDS는 고정된 상수 비율의 다항 시간 근사를 허용하지 않으므로, 그러한 보편적 증명은 $P=NP$를 확립하게 될 것입니다. 적대적 DIMACS 스위트(adversarial DIMACS suite)는 정확한 SciPy MILP 검증 결과와 일치하며 관찰된 최대 비율은 2.000인 반면, testMatrix16 진단은 왜 차수-4 가젯으로부터 리프팅된 해(lifted solution)를 수락하기 전에 후보 검증이 필요한지를 설명해 줍니다.