Introduction
An independent dominating set of an undirected graph G = ( V , E ) G=(V,E) G = ( V , E ) D ⊆ V D \subseteq V D ⊆ V V ∖ D V \setminus D V ∖ D D D D D D D i ( G ) i(G) i ( G ) n = ∣ V ∣ n=|V| n = ∣ V ∣ m = ∣ E ∣ m=|E| m = ∣ E ∣ N ( v ) N(v) N ( v ) N [ v ] = N ( v ) ∪ { v } N[v]=N(v)\cup\{v\} N [ v ] = N ( v ) ∪ { v } deg ( v ) = ∣ N ( v ) ∣ \deg(v)=|N(v)| deg ( v ) = ∣ N ( v ) ∣ Δ \Delta Δ τ ( G ) \tau(G) τ ( G ) α ( G ) \alpha(G) α ( G ) S S S ρ = ∣ S ∣ / i ( G ) \rho=|S|/i(G) ρ = ∣ S ∣/ i ( G )
MIDS is among the hardest graph problems to approximate. Irving proved that, unless P = NP, no polynomial-time algorithm approximates it within any constant factor [1 ] , and Halldórsson proved that it cannot be approximated within n 1 − ε n^{1-\varepsilon} n 1 − ε ε > 0 \varepsilon> 0 ε > 0 [2 ] ; Damian-Iordache and Pă̆mă̆răju proved that it is NP-complete on circle graphs and, unless P = NP, not approximable within n ε n^\varepsilon n ε ε < 1 \varepsilon< 1 ε < 1 n n n [3 ] . The problem remains NP-hard on bipartite graphs: Løwerov and Orlovich proved that it is NP-complete already on cubic planar bipartite graphs [4 ] ; Manlove proved it NP-hard on cubic planar graphs [5 ] , and Bazgan, Brankovic, Casel and Fernau derived from Manlove’s reduction that it is APX-hard on cubic planar graphs [6 ] . On graphs of maximum degree at most a constant B B B B B B [7 ] ; on cubic graphs, Alimonti and Calamoneri gave a polynomial-time algorithm with ratio 1.923, and the ratio 2 on graphs of maximum degree at most 3 [8 ] , while Alimonti and Kann proved APX-completeness on cubic graphs of vertex cover, independent set and dominating set [9 ] . It is also hard to approximate on graphs of bounded degree, including bipartite ones: Chlebík and Chlebíková proved that there are absolute constants δ > 0 \delta> 0 δ > 0 B 0 B_0 B 0 B ≥ B 0 B \ge B_0 B ≥ B 0 δ B \delta B δ B B B B 1 + 1 680 1 + \frac{1}{680} 1 + 680 1 Δ ≤ 3 \Delta\le3 Δ ≤ 3 1 + 1 293 1 + \frac{1}{293} 1 + 293 1 1 + 1 151 1 + \frac{1}{151} 1 + 151 1 Δ ≤ 4 \Delta\le4 Δ ≤ 4 Δ ≤ 5 \Delta\le5 Δ ≤ 5 [10 ] . These results hold without any conjecture.
Under the Unique Games Conjecture (UGC) [11 ] , Khot and Regev proved that Minimum Vertex Cover is hard to approximate within 2 − ε 2 - \varepsilon 2 − ε ε > 0 \varepsilon> 0 ε > 0 [12 ] . In October 2026 the OpenAI Math Team released a manuscript with Lean artifacts reporting a proof of UGC in the NP-hardness form that the theorem of Khot and Regev requires [13 ] ; at the time of writing it has not been peer reviewed. If it holds, the hardness result of Khot and Regev holds unless P = NP. Through a reduction of Chlebík and Chlebíková (§ 7 ), every vertex cover instance becomes an MIDS instance whose optimum is τ \tau τ
This paper describes version 0.0.8 of Siriaisa [14 ] , a Python implementation of an ensemble of eighteen strategies. The ensemble adapts the seventeen strategies of the vertex cover algorithm Salvador [15 , 16 ] and the phases of the independent set algorithm Esperanza [17 ] to independent domination. Where Salvador builds a bipartite structure and solves vertex cover on it exactly by Kőnig’s theorem, Siriaisa builds a forest and solves MIDS on it exactly by a linear-time tree dynamic program; MIDS is NP-hard on bipartite graphs [4 ] , so the bipartite structures of Salvador carry no exact solver for MIDS. One base strategy splits every vertex of degree larger than ⌊ n ⌋ \lfloor\sqrt{n}\rfloor ⌊ n ⌋ ⌊ n ⌋ \lfloor\sqrt{n}\rfloor ⌊ n ⌋
Contributions. The contributions of this paper are:
The algorithm (§ 3 ): twelve base strategies, five improvers and a final refinement, an exact conditioned forest solver, induced-forest layers, a degree-splitting strategy at ⌊ n ⌋ \lfloor\sqrt{n}\rfloor ⌊ n ⌋ Theorem 4.3 ).
Proved bounds (§ 6 ): the ratio is at most Δ \Delta Δ Theorem 6.4 ); the ratio is at most n \sqrt{n} n Theorem 6.5 ); and the degree-splitting strategy yields a dominating set of size at most ⌊ n ⌋ ( i ( G ) + s ( G ) ) \lfloor\sqrt{n}\rfloor(i(G) + s(G)) ⌊ n ⌋ ( i ( G ) + s ( G )) s ( G ) s(G) s ( G ) Theorem 6.8 ); the excess is largest on complete graphs, of order n 3 / 2 n^{3/2} n 3/2 n ≥ D 2 n \ge D^2 n ≥ D 2 D D D O ( n ) O(\sqrt{n}) O ( n ) 6.15 , Table 3 ).
Table 3. The splitting excess s ( G ) s(G) s ( G ) k = ⌊ n ⌋ k=\lfloor\sqrt{n}\rfloor k = ⌊ n ⌋
The parametric bound n 1 − ε ( i ( G ) + s ε ( G ) ) n^{1-\varepsilon}(i(G) + s_{\varepsilon}(G)) n 1 − ε ( i ( G ) + s ε ( G )) ⌊ n 1 − ε ⌋ \lfloor n^{1-\varepsilon}\rfloor ⌊ n 1 − ε ⌋ ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] n 3 / 4 n^{3/4} n 3/4 Δ ≤ ⌊ n 3 / 4 ⌋ \Delta\le\lfloor n^{3/4}\rfloor Δ ≤ ⌊ n 3/4 ⌋ s ε ( K n ) ≥ n s_{\varepsilon}(K_n) \ge n s ε ( K n ) ≥ n ε \varepsilon ε n n n Theorem 6.13 , Corollary 6.14).
The vertex cover reduction of Chlebík and Chlebíková with an explicit gadget and the identity i ( h ( H ) ) = τ ( H ) + 2 ∣ E ( H ) ∣ i(h(H)) = \tau(H) + 2|E(H)| i ( h ( H )) = τ ( H ) + 2∣ E ( H ) ∣ Proposition 7.1 ), the decoding of every independent dominating set into a vertex cover (Lemma 7.2 ), and the conditional consequences for vertex cover approximation, on general graphs under the hardness of Khot and Regev and on bounded-degree graphs under that of Austrin, Khot and Safra (Theorem 7.3 , Corollary 7.4).
Reproducible experiments (§ 9 ): 10 000 structured and random graphs with an exact integer-program optimum; 112 bipartite graphs; 55 instances of the two reductions of Chlebík and Chlebíková, ten of them built from Khot–Regev YES instances; and the 68 complements of the DIMACS clique benchmark graphs.
The application to the SAT solver satypy 0.0.4 (§ 8 ): the structure of the SAT-IDS graph, with i = p i=p i = p i ≥ β + p i \ge\beta+p i ≥ β + p Lemma 8.2 ), the least number of clause copies β \beta β β + p > 2 p 2 \beta+p>2p^{2} β + p > 2 p 2 Lemma 8.4 ) and with β + p > 2 n p \beta+p>2\sqrt{np} β + p > 2 n p Lemma 8.3 ), the correctness of every answer except UNSATISFIABLE on a satisfiable formula, which requires a ratio larger than 2 p 2p 2 p 2 p 2p 2 p Theorem 8.7 ), the failure of the bound of Theorem 6.8 to separate satisfiable from unsatisfiable formulas for every number of copies (Proposition 8.8 ), the exact branching on the clause named by the output (Proposition 8.13 ), the gap p p p p n 1 − 1 / t pn^{1-1/t} p n 1 − 1/ t β t = p t ( 3 q ) t − 1 + 1 \beta_t=p^{t}(3q)^{t-1}+1 β t = p t ( 3 q ) t − 1 + 1 Theorem 8.9 ), which gives a self-contained proof of Halldórsson’s theorem (Corollary 8.11 ) and the decision of every formula under Conjecture 6.20 (Corollary 8.12 ), the asymptotic s ( G ) ∼ 2 p L s(G)\sim2pL s ( G ) ∼ 2 p L β ∗ \beta^{*} β ∗ Proposition 8.5 ), and the identity μ ( φ ) = ⌊ i ( G ) / β ⌋ \mu(\varphi)=\lfloor i(G)/\beta\rfloor μ ( φ ) = ⌊ i ( G ) / β ⌋ μ ( φ ) \mu(\varphi) μ ( φ ) Theorem 8.6 ); and, on every graph, the inequality ⌊ n ⌋ ( i ( G ) + s ( G ) ) ≥ n − i ( G ) \lfloor\sqrt{n}\rfloor(i(G)+s(G))\ge n-i(G) ⌊ n ⌋ ( i ( G ) + s ( G )) ≥ n − i ( G )
§ 2 records the code metadata, § 3 describes the algorithm, § 4 proves correctness, § 5 the running time and § 6 the bounds. § 7 treats the reductions and the conditional consequences, § 8 the application to Boolean satisfiability, § 9 reports the experiments and § 10 concludes.
Research Data
The algorithm is implemented in the Python package siriaisa [14 ] . The version described in this paper is v0.0.8. Table 1 lists the code metadata.
Table 1. Code metadata of the siriaisa package. SciPy is used only by the experiment scripts, for the exact integer programs.
The Siriaisa Algorithm
The input graph is converted once into an index graph adj on the vertices 0 , … , n − 1 0,\ldots,n-1 0 , … , n − 1 § 3.1 ; the strategies are computed in their numbering order, the base strategies c 1 c_{1} c 1 c 13 c_{13} c 13 c 14 c_{14} c 14 c 18 c_{18} c 18 c 18 c_{18} c 18 Table 2 lists them, and Algorithm 1 gives the main loop.
Table 2. The eighteen strategies of Siriaisa 0.0.8. “Source” names the strategy of Salvador [15 ] or the phase of Esperanza [17 ] that it adapts.
Algorithm 1 FindIndependentDominatingSet(G G G
Require: Undirected graph G = ( V , E ) G = (V, E) G = ( V , E )
Ensure: An independent dominating set of G G G
remove self-loops; build the index graph adj; n ← ∣ V ∣ n \gets|V| n ← ∣ V ∣ m ← ∣ E ∣ m \gets|E| m ← ∣ E ∣
c 1 ← Complete ( SpanningTreePeeling ( adj ) ) c_1 \gets\operatorname{Complete}(\operatorname{SpanningTreePeeling}(\text{adj})) c 1 ← Complete ( SpanningTreePeeling ( adj )) c 2 ← Complete ( endpoints of min_maximal_matching ) c_2 \gets\operatorname{Complete}(\text{endpoints of min\_maximal\_matching}) c 2 ← Complete ( endpoints of min_maximal_matching ) c 3 ← Complete ( ∅ ) c_3 \gets\operatorname{Complete}(\varnothing) c 3 ← Complete ( ∅ )
c 4 , c 7 , c 8 ← c_4, c_7, c_8 \gets c 4 , c 7 , c 8 ←
c 5 ← MinToMin c_5 \gets\operatorname{MinToMin} c 5 ← MinToMin c 6 ← PrimalDual c_6 \gets\operatorname{PrimalDual} c 6 ← PrimalDual
( c 9 , L ) ← ForestLayers ( adj ) (c_9, \mathcal{L}) \gets\operatorname{ForestLayers}(\text{adj}) ( c 9 , L ) ← ForestLayers ( adj ) L \mathcal{L} L
c 10 ← ResolveLayer ( best of c 1 . . c 9 , L 0 ) c_{10} \gets\operatorname{ResolveLayer}(\text{best of }c_1..c_9, L_0) c 10 ← ResolveLayer ( best of c 1 .. c 9 , L 0 )
c 11 ← FeedbackForest ( adj , best of c 1 . . c 10 ) c_{11} \gets\operatorname{FeedbackForest}(\text{adj}, \text{best of }c_1..c_{10}) c 11 ← FeedbackForest ( adj , best of c 1 .. c 10 ) c 12 ← CaroWei c_{12} \gets\operatorname{CaroWei} c 12 ← CaroWei c 13 ← DegreeSplit ( adj ) c_{13} \gets\operatorname{DegreeSplit}(\text{adj}) c 13 ← DegreeSplit ( adj )
L B ← ∑ components C ⌈ n C Δ C + 1 ⌉ LB \gets\sum_{\text{components }C} \left\lceil\frac{n_C}{\Delta_C + 1}\right\rceil L B ← ∑ components C ⌈ Δ C + 1 n C ⌉ Lemma 6.3
c 14 ← Complete ( c 2 ∪ ⋯ ∪ c 8 , priority = votes ) c_{14} \gets\operatorname{Complete}(c_2 \cup\cdots\cup c_8, \text{ priority} = \text{votes}) c 14 ← Complete ( c 2 ∪ ⋯ ∪ c 8 , priority = votes )
c 15 ← ImproveIDS ( best of c 1 . . c 14 ) c_{15} \gets\operatorname{ImproveIDS}(\text{best of }c_1..c_{14}) c 15 ← ImproveIDS ( best of c 1 .. c 14 )
c 16 ← c_{16} \gets c 16 ← ImproveIDS \operatorname{ImproveIDS} ImproveIDS ForestLNS ( L ) \operatorname{ForestLNS}(\mathcal{L}) ForestLNS ( L ) c 1 . . c 15 c_1..c_{15} c 1 .. c 15
c 17 ← ConsensusForce ( c 1 , … , c 16 ) c_{17} \gets\operatorname{ConsensusForce}(c_1, \ldots, c_{16}) c 17 ← ConsensusForce ( c 1 , … , c 16 )
R j ← ImproveIDS ( ForestLNS ( c j , L ) ) R_j \gets\operatorname{ImproveIDS}(\operatorname{ForestLNS}(c_j, \mathcal{L})) R j ← ImproveIDS ( ForestLNS ( c j , L )) c j c_j c j j ≤ 17 j \le17 j ≤ 17
c 18 ← Complete ( ForestLNS ( ImproveIDS ( min j R j ) , L ) ) c_{18} \gets\operatorname{Complete}(\operatorname{ForestLNS}(\operatorname{ImproveIDS}(\min_j R_j), \mathcal{L})) c 18 ← Complete ( ForestLNS ( ImproveIDS ( min j R j ) , L ))
verify every c j c_j c j return c 18 c_{18} c 18
Every search of lines 10, 11, 13 and 14 stops as soon as its best set has at most L B LB L B
Repair and completion
Algorithm 2 turns any seed into an independent dominating set; it is the counterpart of the pruning of Salvador and of the routine MaximizeSolution of Salvador and Esperanza. All sorts are stable counting sorts on integer keys.
Algorithm 2 Complete(adj, P P P π \pi π
Require: Index graph, seed P ⊂ V P \subset V P ⊂ V π \pi π
Ensure: An independent dominating set S S S
S ← P S \leftarrow P S ← P conf ( v ) ← ∣ N ( v ) ∩ S ∣ \operatorname{conf}(v) \leftarrow|N(v) \cap S| conf ( v ) ← ∣ N ( v ) ∩ S ∣ v ∈ S v \in S v ∈ S
for v ∈ S v \in S v ∈ S conf ( v ) > 0 \operatorname{conf}(v) > 0 conf ( v ) > 0 π \pi π do
if v ∈ S v \in S v ∈ S conf ( v ) > 0 \operatorname{conf}(v) > 0 conf ( v ) > 0 then remove v v v S S S S S S
end if
end for
U ← U \leftarrow U ← S S S g ( v ) ← ∣ N [ v ] ∩ U ∣ g(v) \leftarrow|N[v] \cap U| g ( v ) ← ∣ N [ v ] ∩ U ∣ v ∈ U v \in U v ∈ U
while U ≠ ∅ U \ne\varnothing U = ∅ do ▷ bucket queue on g g g
take v ∈ U v \in U v ∈ U g ( v ) g(v) g ( v ) S ← S ∪ { v } S \leftarrow S \cup\{v\} S ← S ∪ { v } N [ v ] ∩ U N[v] \cap U N [ v ] ∩ U U U U g g g
end while
return S S S
The conditioned forest solver
Let F F F G G G G G G v v v F F F in ( v ) \operatorname{in}(v) in ( v ) v v v v v v F F F pre ( v ) \operatorname{pre}(v) pre ( v ) v v v F F F force ( v ) \operatorname{force}(v) force ( v ) v v v F F F P > ∣ F ∣ P > |F| P > ∣ F ∣
Φ ( X ) = ∣ X ∣ + P ⋅ ∣ { v ∈ V ( F ) : v ∉ X ∪ N ( X ) , ¬ pre ( v ) } ∣ + P ⋅ ∣ { v : force ( v ) , v ∉ X } ∣ \Phi(X) = |X| + P \cdot|\{v \in V(F): v \notin X \cup N(X),\ \neg\operatorname{pre}(v)\}| + P \cdot|\{v: \operatorname{force}(v),\ v \notin X\}| Φ ( X ) = ∣ X ∣ + P ⋅ ∣ { v ∈ V ( F ) : v ∈ / X ∪ N ( X ) , ¬ pre ( v )} ∣ + P ⋅ ∣ { v : force ( v ) , v ∈ / X } ∣ over the sets X ⊆ V ( F ) X \subseteq V(F) X ⊆ V ( F ) in ( v ) \operatorname{in}(v) in ( v ) v v v v ∈ X v \in X v ∈ X v ∉ X v \notin X v ∈ / X v ∉ X v \notin X v ∈ / X u ( c ) = 0 u(c) = 0 u ( c ) = 0 pre ( c ) \operatorname{pre}(c) pre ( c ) u ( c ) = P u(c) = P u ( c ) = P a ( c ) = min ( DOM ( c ) , FREE ( c ) + u ( c ) ) a(c) = \min(\operatorname{DOM}(c), \operatorname{FREE}(c) + u(c)) a ( c ) = min ( DOM ( c ) , FREE ( c ) + u ( c )) c c c v v v
IN ( v ) = { 1 + ∑ c min ( DOM ( c ) , FREE ( c ) ) if in ( v ) , ∞ otherwise , FREE ( v ) = ∑ c a ( c ) + P ⋅ [ force ( v ) ] , DOM ( v ) = ∑ c min ( IN ( c ) , a ( c ) ) + δ ( v ) + P ⋅ [ force ( v ) ] . \begin{aligned}
\operatorname{IN}(v) &=
\begin{cases}
1 + \sum_c \min(\operatorname{DOM}(c),\operatorname{FREE}(c)) & \text{if }\operatorname{in}(v),\\
\infty& \text{otherwise},
\end{cases}\\
\operatorname{FREE}(v) &= \sum_c a(c) + P \cdot[\operatorname{force}(v)],\\
\operatorname{DOM}(v) &= \sum_c \min(\operatorname{IN}(c),a(c)) + \delta(v) + P \cdot[\operatorname{force}(v)].
\end{aligned} IN ( v ) FREE ( v ) DOM ( v ) = { 1 + ∑ c min ( DOM ( c ) , FREE ( c )) ∞ if in ( v ) , otherwise , = c ∑ a ( c ) + P ⋅ [ force ( v )] , = c ∑ min ( IN ( c ) , a ( c )) + δ ( v ) + P ⋅ [ force ( v )] . where δ ( v ) = 0 \delta(v) = 0 δ ( v ) = 0 pre ( v ) \operatorname{pre}(v) pre ( v ) IN ( c ) ≤ a ( c ) \operatorname{IN}(c) \le a(c) IN ( c ) ≤ a ( c ) δ ( v ) = min c ( IN ( c ) − a ( c ) ) \delta(v) = \min_c(\operatorname{IN}(c) - a(c)) δ ( v ) = min c ( IN ( c ) − a ( c )) X X X DOM ( v ) = ∞ \operatorname{DOM}(v) = \infty DOM ( v ) = ∞ ¬ pre ( v ) \neg\operatorname{pre}(v) ¬ pre ( v ) r r r min ( IN ( r ) , DOM ( r ) , FREE ( r ) + u ( r ) ) \min(\operatorname{IN}(r),\operatorname{DOM}(r),\operatorname{FREE}(r) + u(r)) min ( IN ( r ) , DOM ( r ) , FREE ( r ) + u ( r )) X X X
Algorithm 3 ConditionedForestIDS(F F F in \operatorname{in} in pre \operatorname{pre} pre force \operatorname{force} force P P P
Require: An induced forest F F F P > ∣ V ( F ) ∣ P > |V(F)| P > ∣ V ( F ) ∣
Ensure: A minimiser X X X Φ \Phi Φ
for every tree of F F F do
root it; compute a BFS order and the children lists
for v v v do compute IN ( v ) \operatorname{IN}(v) IN ( v ) DOM ( v ) \operatorname{DOM}(v) DOM ( v ) FREE ( v ) \operatorname{FREE}(v) FREE ( v )
end for
choose the state of the root; assign the states top-down by the recorded choices; add the IN vertices to X X X
end for
return X X X
With neutral flags (in ≡ t r u e \operatorname{in} \equiv\mathrm{true} in ≡ true pre ≡ force ≡ f a l s e \operatorname{pre} \equiv\operatorname{force} \equiv\mathrm{false} pre ≡ force ≡ false F F F Lemma 4.2 ). ResolveLayer(S S S L L L L L L S S S L L L S S S S S S L L L L L L L L L L \mathcal{L} L 40 ( n + m ) 40(n + m) 40 ( n + m )
Base strategies
c 1 c_1 c 1 R R R G G G R R R deg R ( u ) + deg R ( v ) \operatorname{deg}_{R}(u) + \operatorname{deg}_{R}(v) deg R ( u ) + deg R ( v ) [18 ] ; the forest is solved exactly by Algorithm 3; a maximal G G G 40 ( n + m ) 40(n + m) 40 ( n + m )
c 2 c_2 c 2 c 8 c_8 c 8 c 2 c_2 c 2 [19 ] minimum maximal matching; every unmatched vertex has all its neighbours matched, so the endpoints and the isolated vertices dominate G G G c 3 c_3 c 3 c 4 c_4 c 4 c 5 c_5 c 5 c 6 c_6 c 6 v v v min ∑ u x u , ∑ u ∈ N [ v ] x u ≥ 1 \min\sum_{u} x_u,\ \sum_{u\in N[v]} x_u \ge1 min ∑ u x u , ∑ u ∈ N [ v ] x u ≥ 1 N [ v ] N[v] N [ v ] c 7 c_7 c 7 c 8 c_8 c 8 G G G G G G
c 9 c_9 c 9
Algorithm 4 ForestLayers(adj)
Require: Index graph; layering budget 8(n + m); at most 6 orders per component
Ensure: An independent dominating set and the layers 𝓛
1: for every connected component C do
2: R ← V(C) sorted by increasing degree; t ← 0
3: while R ≠ ∅ and the budget allows do
4: L_t ← ∅
5: for v ∈ R do add v to L_t if its neighbours in L_t lie in pairwise different trees of L_t (union-find)
6: end for
7: R ← R \ L_t; t ← t + 1
8: end while
9: for every order σ of the layers (all of them if t! ≤ 6, otherwise the natural and the reverse order and their rotations, at most 6) do
10: X ← ∅
11: for L in the order σ do X ← X ∪ ConditionedForestIDS(L \ (X ∪ N(X))) with neutral flags
12: end for
13: complete X greedily on the vertices still undominated; keep the smallest X
14: end for
15: end forc 10 c_{10} c 10 c 11 c_{11} c 11 c 10 c_{10} c 10 L \mathcal{L} L c 1 c_1 c 1 c 9 c_9 c 9 c 11 c_{11} c 11 core ) by the reductions of Salvador’s c 11 c_{11} c 11 v v v a , b a,b a , b a a a b b b b b b b b b G G G c 1 c_1 c 1 c 10 c_{10} c 10
c 12 c_{12} c 12 c 12 c_{12} c 12 [20 , 21 ] .
c 13 c_{13} c 13 degree splitting. Algorithm 5 replaces every vertex of degree larger than k = ⌊ n ⌋ k=\lfloor\sqrt{n}\rfloor k = ⌊ n ⌋ k k k
Algorithm 5 DegreeSplit(adj)
Require: Index graph on n vertices
Ensure: An independent dominating set of G
1: k ← max(1, ⌊√n⌋); H ← G; owner(v) ← v
2: for u ∈ V by decreasing degree (counting sort) do
3: if deg_H(u) > k then
4: let w₁, …, w_d be the neighbours of u in H; remove u from H
5: for j = 1, …, ⌈d/k⌉ do add a node u_j with owner(u_j) = u, joined to w_(j−1)k+1, …, w_min(jk,d)
6: end for
7: end if
8: end for
9: for each inner solver A ∈ {Complete(∅), MinToMin, ForestLayers} do
10: S_H ← A(H); cnt(v) ← |{x ∈ S_H : owner(x) = v}|; S₀ ← {v : cnt(v) > 0}
11: S_A ← Complete(adj, S₀, π = cnt) ▷ repair with pruning
12: end for
13: return the smallest S_AImprovers and the weighted swap search
c 14 c_{14} c 14 c 2 c_2 c 2 c 8 c_8 c 8 c 17 c_{17} c 17 k k k q k ∈ { 1 , 0.9 , 0.75 } q_k \in\{1, 0.9, 0.75\} q k ∈ { 1 , 0.9 , 0.75 }
Algorithm 6 is the local search used by c 15 c_{15} c 15 c 16 c_{16} c 16 c 18 c_{18} c 18 move at a vertex u ∉ S u \notin S u ∈ / S u u u k = ∣ N ( u ) ∩ S ∣ k=|N(u)\cap S| k = ∣ N ( u ) ∩ S ∣ u u u S S S S S S k ≥ 2 k\geq2 k ≥ 2 S S S k k k w ( v ) ≥ 1 w(v)\geq1 w ( v ) ≥ 1 w ( e ) ≥ 1 w(e)\geq1 w ( e ) ≥ 1
cost ( S ) = ∑ v : N [ v ] ∩ S = ∅ w ( v ) + ∑ e ⊆ S w ( e ) , \operatorname{cost}(S)=\sum_{v:N[v]\cap S=\varnothing}w(v)+\sum_{e\subseteq S}w(e), cost ( S ) = v : N [ v ] ∩ S = ∅ ∑ w ( v ) + e ⊆ S ∑ w ( e ) , so that every vertex, not only an undominated one, may enter S S S cost ( S ) = 0 \operatorname{cost}(S)=0 cost ( S ) = 0 S S S k k k k − 1 k-1 k − 1
Algorithm 6 ImproveIDS(adj, S 0 S_0 S 0 B B B σ \sigma σ
Require: An independent dominating set S 0 S_0 S 0 W = max ( B ( n + m ) , F ) W = \max(B(n + m), F) W = max ( B ( n + m ) , F ) σ \sigma σ L B LB L B
Ensure: An independent dominating set S ∗ S^* S ∗ ∣ S ∗ ∣ ≤ ∣ S 0 ∣ |S^*| \le|S_0| ∣ S ∗ ∣ ≤ ∣ S 0 ∣
S ← S \gets S ← S 0 S_0 S 0 k ≥ 2 k \ge2 k ≥ 2 S ∗ ← S S^* \gets S S ∗ ← S
for segment i = 1 , … , 4 i = 1, \ldots, 4 i = 1 , … , 4 θ i ∈ ( 10 , 100 , 30 , 300 ) \theta_i \in(10, 100, 30, 300) θ i ∈ ( 10 , 100 , 30 , 300 ) σ \sigma σ do
S ← S ∗ S \gets S^* S ← S ∗ ← 1 \gets1 ← 1
while work remains and ∣ S ∗ ∣ > L B |S^*| > LB ∣ S ∗ ∣ > L B do
remove the vertex of S S S
take a random undominated vertex v v v N [ v ] N[v] N [ v ]
add 1 to the weight of every undominated vertex and of every conflicting edge; halve all weights when their mean exceeds θ i \theta_i θ i
if cost ( S ) = 0 \operatorname{cost}(S) = 0 cost ( S ) = 0 then S ∗ ← S S^* \gets S S ∗ ← S S S S
end if
end while
end for
return S ∗ S^* S ∗
The score of a vertex is the decrease of the cost when it changes side; configuration checking forbids a removed vertex to re-enter before one of its neighbours has changed side. All scores, the domination counts and the sets of violations are updated incrementally in time proportional to the degrees of the two-hop neighbourhood of the changed vertex, and every operation is charged to a work counter. The default budgets are B = 10 B = 10 B = 10 c 15 c_{15} c 15 c 16 c_{16} c 16 c 18 c_{18} c 18 F = min ( 2 ⋅ 10 6 , 10 ( n + m ) 2 ) F = \min(2 \cdot10^6, 10(n + m)^2) F = min ( 2 ⋅ 1 0 6 , 10 ( n + m ) 2 ) F = min ( 24 ⋅ 10 6 , 100 ( n + m ) 2 ) F = \min(24 \cdot10^6, 100(n + m)^2) F = min ( 24 ⋅ 1 0 6 , 100 ( n + m ) 2 )
Correctness of the Algorithm
Lemma 4.1 (Repair and completion). For every seed P P P G G G O ( n + m + max π ) O(n + m + \max\pi) O ( n + m + max π )
Proof. After the repair loop no vertex of S S S S S S U U U S S S S S S U = ∅ U = \varnothing U = ∅ O ( n + Δ + max π ) O(n + \Delta+ \max\pi) O ( n + Δ + max π ) U U U O ( n + m ) O(n + m) O ( n + m )
Lemma 4.2 (Exact conditioned forest solver). Algorithm 3 returns a minimiser of Φ \Phi Φ O ( ∑ v ∈ V ( F ) deg G ( v ) ) O(\sum_{v \in V(F)} \deg_G(v)) O ( ∑ v ∈ V ( F ) deg G ( v )) P > ∣ V ( F ) ∣ P > |V(F)| P > ∣ V ( F ) ∣ F F F
Proof. For a rooted subtree T v T_v T v IN ( v ) \operatorname{IN}(v) IN ( v ) DOM ( v ) \operatorname{DOM}(v) DOM ( v ) FREE ( v ) \operatorname{FREE}(v) FREE ( v ) Φ \Phi Φ T v T_v T v X ∩ T v X \cap T_v X ∩ T v v v v v v v u ( c ) u(c) u ( c ) u ( c ) u(c) u ( c ) X X X F F F Φ ( X ) = ∣ X ∣ ≤ ∣ V ( F ) ∣ < P \Phi(X) = |X| \le|V(F)| < P Φ ( X ) = ∣ X ∣ ≤ ∣ V ( F ) ∣ < P F F F
Theorem 4.3 (Correctness). For every finite undirected graph G G G G G G c 1 , … , c 18 c_1,\ldots,c_{18} c 1 , … , c 18 G G G
Proof. Self-loops do not affect independence or domination of other vertices and are removed. c 1 c_1 c 1 c 4 c_4 c 4 c 7 c_7 c 7 c 8 c_8 c 8 c 13 c_{13} c 13 c 14 c_{14} c 14 Lemma 4.1 . c 5 c_5 c 5 c 6 c_6 c 6 c 12 c_{12} c 12 X X X G G G Lemma 4.2 ), so X X X c 10 c_{10} c 10 c 11 c_{11} c 11 c 17 c_{17} c 17 u u u S S S S S S
Runtime Analysis
Hash-table operations are counted as O ( 1 ) O(1) O ( 1 ) c 11 c_{11} c 11 c 13 c_{13} c 13
Lemma 5.1 (Copy graph). In Algorithm 5 let B = { v : deg G ( v ) > k } B = \{v : \deg_G(v) > k\} B = { v : deg G ( v ) > k } H H H k k k m m m H H H G G G G G G H H H ∣ V ( H ) ∣ = n − ∣ B ∣ + ∑ v ∈ B ⌈ deg G ( v ) / k ⌉ ≤ n + 2 m / k |V(H)| = n - |B| + \sum_{v\in B}\lceil\deg_G(v)/k\rceil\le n + 2m/k ∣ V ( H ) ∣ = n − ∣ B ∣ + ∑ v ∈ B ⌈ deg G ( v ) / k ⌉ ≤ n + 2 m / k O ( n + m ) O(n + m) O ( n + m )
Proof. Splitting u u u u w uw u w H H H u j w u_jw u j w u u u deg H ( u ) = deg G ( u ) \deg_H(u) = \deg_G(u) deg H ( u ) = deg G ( u ) u u u k k k k k k H H H m m m u u u u u u ⌈ d / k ⌉ ≤ d / k + 1 \lceil d/k\rceil\le d/k + 1 ⌈ d / k ⌉ ≤ d / k + 1 ∣ V ( H ) ∣ ≤ n + ∑ v ∈ B deg G ( v ) / k ≤ n + 2 m / k |V(H)| \le n + \sum_{v\in B}\deg_G(v)/k \le n + 2m/k ∣ V ( H ) ∣ ≤ n + ∑ v ∈ B deg G ( v ) / k ≤ n + 2 m / k
Theorem 5.2 (Running time). For the default parameters, Algorithm 1 runs in O ( ( n + m ) α A ( n ) ) O((n + m)\alpha_A(n)) O (( n + m ) α A ( n ))
Proof. The conversion, the components, the lower bound L B LB L B n + m n + m n + m c 2 c_2 c 2 c 3 c_3 c 3 c 8 c_8 c 8 c 12 c_{12} c 12 O ( n + m ) O(n + m) O ( n + m ) Lemmas 4.1 and 4.2 . c 1 c_1 c 1 c 9 c_9 c 9 O ( α A ( n ) ) O(\alpha_A(n)) O ( α A ( n )) [18 ] , within the work budgets 40 ( n + m ) 40(n + m) 40 ( n + m ) 8 ( n + m ) 8(n + m) 8 ( n + m ) c 9 c_9 c 9 O ( n + m ) O(n + m) O ( n + m ) c 10 c_{10} c 10 c 11 c_{11} c 11 O ( n + m ) O(n + m) O ( n + m ) O ( deg ) O(\deg) O ( deg ) c 13 c_{13} c 13 Lemma 5.1 , since the inner solvers and the three repairs are linear in ∣ V ( H ) ∣ + m = O ( n + m ) |V(H)| + m = O(n + m) ∣ V ( H ) ∣ + m = O ( n + m ) max ( B ( n + m ) , F ) \max(B(n + m),F) max ( B ( n + m ) , F ) B B B F F F O ( n + m ) O(n + m) O ( n + m ) c 17 c_{17} c 17 O ( ( n + m ) α A ( n ) ) O((n + m)\alpha_A(n)) O (( n + m ) α A ( n ))
Proved Bounds
Lemma 6.1 (Maximal-set bound). Every maximal independent set M M M G G G Δ ≥ 1 \Delta\ge1 Δ ≥ 1 n / ( Δ + 1 ) ≤ i ( G ) ≤ ∣ M ∣ ≤ Δ i ( G ) n/(\Delta+ 1) \le i(G) \le|M| \le\Delta i(G) n / ( Δ + 1 ) ≤ i ( G ) ≤ ∣ M ∣ ≤ Δ i ( G )
Proof. A minimum independent dominating set D D D V = ⋃ d ∈ D N [ d ] V = \bigcup_{d\in D}N[d] V = ⋃ d ∈ D N [ d ] n ≤ ( Δ + 1 ) ∣ D ∣ n \le(\Delta+ 1)|D| n ≤ ( Δ + 1 ) ∣ D ∣ M M M i ( G ) ≤ ∣ M ∣ i(G) \le|M| i ( G ) ≤ ∣ M ∣ d ∈ D d \in D d ∈ D ∣ M ∩ N [ d ] ∣ = 1 |M \cap N[d]| = 1 ∣ M ∩ N [ d ] ∣ = 1 d ∈ M d \in M d ∈ M M ∩ N [ d ] ⊆ N ( d ) M \cap N[d] \subseteq N(d) M ∩ N [ d ] ⊆ N ( d ) Δ \Delta Δ M ⊆ ⋃ d ∈ D N [ d ] M \subseteq\bigcup_{d\in D}N[d] M ⊆ ⋃ d ∈ D N [ d ] ∣ M ∣ ≤ Δ ∣ D ∣ |M| \le\Delta|D| ∣ M ∣ ≤ Δ∣ D ∣
Corollary 6.2 (Bounded degree). For every graph G G G S S S ∣ S ∣ ≤ max ( 1 , Δ ) i ( G ) |S| \le\max(1,\Delta)i(G) ∣ S ∣ ≤ max ( 1 , Δ ) i ( G ) Δ \Delta Δ
Proof. Isolated vertices belong to S S S S S S Theorem 4.3 ), so Lemma 6.1 applies componentwise and the bounds add up.
Lemma 6.3 (Certified lower bound). For every graph G G G C C C i ( G ) ≥ L B = ∑ C ⌈ n C / ( Δ C + 1 ) ⌉ i(G) \ge LB = \sum_C \lceil n_C/(\Delta_C+1)\rceil i ( G ) ≥ L B = ∑ C ⌈ n C / ( Δ C + 1 )⌉ L B LB L B
Proof. An independent dominating set of G G G Lemma 6.1 gives i ( C ) ≥ n C / ( Δ C + 1 ) i(C) \ge n_C/(\Delta_C+1) i ( C ) ≥ n C / ( Δ C + 1 )
Theorem 6.4 (Forests). If G G G
Proof. On a forest, the first round of c 1 c_1 c 1 4 ( n + 2 m ) 4(n+2m) 4 ( n + 2 m ) n + m n+m n + m 40 ( n + m ) 40(n+m) 40 ( n + m ) G G G G G G G G G c 1 c_1 c 1 Lemma 4.2 . Every candidate after c 1 c_1 c 1 c 18 c_{18} c 18 ∣ c 18 ∣ ≤ ∣ c 1 ∣ = i ( G ) |c_{18}| \le|c_1| = i(G) ∣ c 18 ∣ ≤ ∣ c 1 ∣ = i ( G )
The next theorem is the counterpart of the O ( n ) O(\sqrt{n}) O ( n ) [17 ] , which gives the ratio 2 n 2\sqrt{n} 2 n Δ ≤ n \Delta\le\sqrt{n} Δ ≤ n Δ \Delta Δ
Theorem 6.5 (Ratio n \sqrt{n} n Let S S S G G G n n n ∣ S ∣ / i ( G ) ≤ n |S|/i(G) \le\sqrt{n} ∣ S ∣/ i ( G ) ≤ n
(a) Δ ≤ n \Delta\le\sqrt{n} Δ ≤ n ∣ S ∣ / i ( G ) ≤ max ( 1 , Δ ) |S|/i(G) \le\max(1,\Delta) ∣ S ∣/ i ( G ) ≤ max ( 1 , Δ )
(b) i ( G ) ≥ n i(G) \ge\sqrt{n} i ( G ) ≥ n
(c) α ( G ) ≤ n i ( G ) \alpha(G) \le\sqrt{n}\,i(G) α ( G ) ≤ n i ( G )
Proof. (a) is Corollary 6.2. (b) ∣ S ∣ ≤ n |S| \le n ∣ S ∣ ≤ n ∣ S ∣ / i ( G ) ≤ n / n |S|/i(G) \le n/\sqrt{n} ∣ S ∣/ i ( G ) ≤ n / n S S S ∣ S ∣ ≤ α ( G ) ≤ n i ( G ) |S| \le\alpha(G) \le\sqrt{n}i(G) ∣ S ∣ ≤ α ( G ) ≤ n i ( G )
The degree-splitting strategy c 13 c_{13} c 13 n \sqrt{n} n k = max ( 1 , ⌊ n ⌋ ) k=\max(1,\lfloor\sqrt{n}\rfloor) k = max ( 1 , ⌊ n ⌋) B = { v : deg G ( v ) > k } B=\{v:\deg_G(v)>k\} B = { v : deg G ( v ) > k } splitting excess
s ( G ) = ∑ v ∈ B ( ⌈ deg G ( v ) k ⌉ − 1 ) ≤ ∑ v ∈ B deg G ( v ) k ≤ 2 m k . s(G)=\sum_{v\in B}\left(\left\lceil\frac{\deg_G(v)}{k}\right\rceil-1\right)\le\sum_{v\in B}\frac{\deg_G(v)}{k}\le\frac{2m}{k}. s ( G ) = v ∈ B ∑ ( ⌈ k deg G ( v ) ⌉ − 1 ) ≤ v ∈ B ∑ k deg G ( v ) ≤ k 2 m . Lemma 6.6 (Lifting). For the copy graph H H H i ( H ) ≤ i ( G ) + s ( G ) i(H)\le i(G)+s(G) i ( H ) ≤ i ( G ) + s ( G )
Proof. Let D D D G G G L L L H H H D D D ∣ L ∣ = ∑ u ∈ D ⌈ deg G ( u ) / k ⌉ |L|=\sum_{u\in D}\lceil\deg_G(u)/k\rceil ∣ L ∣ = ∑ u ∈ D ⌈ deg G ( u ) / k ⌉ u u u u u u L L L H H H H H H Lemma 5.1 ) and D D D z z z H H H w ∉ D w\notin D w ∈ / D w w w u ∈ D u\in D u ∈ D u w uw u w G G G H H H u u u L L L w w w w w w z z z z z z L L L w w w ⌈ deg G ( w ) / k ⌉ \lceil\deg_G(w)/k\rceil ⌈ deg G ( w ) / k ⌉ L L L H H H ⌈ deg G ( w ) / k ⌉ − 1 \lceil\deg_G(w)/k\rceil-1 ⌈ deg G ( w ) / k ⌉ − 1 w ∉ D w\notin D w ∈ / D i ( H ) ≤ ∣ D ∣ + ∑ u ∈ D ∩ B ( ⌈ deg G ( u ) / k ⌉ − 1 ) + ∑ w ∈ B ∖ D ( ⌈ deg G ( w ) / k ⌉ − 1 ) = i ( G ) + s ( G ) i(H)\le|D|+\sum_{u\in D\cap B}(\lceil\deg_G(u)/k\rceil-1)+\sum_{w\in B\setminus D}(\lceil\deg_G(w)/k\rceil-1)=i(G)+s(G) i ( H ) ≤ ∣ D ∣ + ∑ u ∈ D ∩ B (⌈ deg G ( u ) / k ⌉ − 1 ) + ∑ w ∈ B ∖ D (⌈ deg G ( w ) / k ⌉ − 1 ) = i ( G ) + s ( G )
Lemma 6.7 (Decoding). For every independent dominating set S H S_H S H H H H S 0 = { owner ( x ) : x ∈ S H } S_0=\{\operatorname{owner}(x):x\in S_H\} S 0 = { owner ( x ) : x ∈ S H } G G G ∣ S 0 ∣ ≤ ∣ S H ∣ |S_0|\le|S_H| ∣ S 0 ∣ ≤ ∣ S H ∣ S 0 S_0 S 0 G G G ( adj , S 0 , π ) = S 0 (\operatorname{adj},S_0,\pi)=S_0 ( adj , S 0 , π ) = S 0
Proof. ∣ S 0 ∣ ≤ ∣ S H ∣ |S_0|\le|S_H| ∣ S 0 ∣ ≤ ∣ S H ∣ w ∈ V w\in V w ∈ V w w w w w w H H H S H S_H S H w ∈ S 0 w\in S_0 w ∈ S 0 x ∈ S H x\in S_H x ∈ S H w w w G G G w w w S 0 S_0 S 0 U = ∅ U=\varnothing U = ∅ S 0 S_0 S 0 G G G
Theorem 6.8 (Degree splitting). Let k = max ( 1 , ⌊ n ⌋ ) k = \max(1, \lfloor\sqrt{n}\rfloor) k = max ( 1 , ⌊ n ⌋) S 0 S_0 S 0 G G G
∣ S 0 ∣ ≤ k ( i ( G ) + s ( G ) ) . |S_0| \le k\bigl(i(G) + s(G)\bigr). ∣ S 0 ∣ ≤ k ( i ( G ) + s ( G ) ) . If S 0 S_0 S 0 G G G S S S ∣ S ∣ ≤ k ( i ( G ) + s ( G ) ) |S| \le k\bigl(i(G) + s(G)\bigr) ∣ S ∣ ≤ k ( i ( G ) + s ( G ) ) ∣ S ∣ / i ( G ) ≤ ⌊ n ⌋ ( 1 + s ( G ) / i ( G ) ) |S|/i(G) \le\lfloor\sqrt{n}\rfloor\bigl(1 + s(G)/i(G)\bigr) ∣ S ∣/ i ( G ) ≤ ⌊ n ⌋ ( 1 + s ( G ) / i ( G ) ) ∣ S ∣ / i ( G ) ≤ 2 n |S|/i(G) \le2\sqrt{n} ∣ S ∣/ i ( G ) ≤ 2 n s ( G ) ≤ i ( G ) s(G) \le i(G) s ( G ) ≤ i ( G )
Proof. Every inner solver returns a maximal independent set S H S_H S H H H H Lemma 4.1 and Theorem 4.3 ). H H H k k k Lemma 5.1 , so Lemma 6.1 , applied componentwise in H H H max ( 1 , Δ ( H ) ) ≤ k \max(1,\Delta(H)) \le k max ( 1 , Δ ( H )) ≤ k ∣ S H ∣ ≤ k i ( H ) |S_H| \le k\,i(H) ∣ S H ∣ ≤ k i ( H ) Lemma 6.6 gives i ( H ) ≤ i ( G ) + s ( G ) i(H) \le i(G) + s(G) i ( H ) ≤ i ( G ) + s ( G ) Lemma 6.7 gives ∣ S 0 ∣ ≤ ∣ S H ∣ |S_0| \le|S_H| ∣ S 0 ∣ ≤ ∣ S H ∣ c 13 ≤ ∣ S 0 ∣ c_{13} \le|S_0| c 13 ≤ ∣ S 0 ∣ S 0 S_0 S 0 c 13 c_{13} c 13
On a graph with Δ ≤ k \Delta\le k Δ ≤ k s ( G ) = 0 s(G) = 0 s ( G ) = 0 H = G H = G H = G Theorem 6.8 reduces to Theorem 6.5 (a). On a star K 1 , n − 1 K_{1,n-1} K 1 , n − 1 s ( G ) = ⌈ ( n − 1 ) / k ⌉ − 1 s(G) = \lceil(n - 1)/k\rceil- 1 s ( G ) = ⌈( n − 1 ) / k ⌉ − 1 ⌈ ( n − 1 ) / k ⌉ \lceil(n - 1)/k\rceil ⌈( n − 1 ) / k ⌉ H H H { centre } \{\text{centre}\} { centre } Theorem 6.8 on S 0 S_0 S 0 S 0 S_0 S 0
Worst cases of the splitting excess. The excess s ( G ) s(G) s ( G )
Proposition 6.9 (Splitting excess). Let G G G n ≥ 3 n \ge3 n ≥ 3 m m m k = ⌊ n ⌋ k = \lfloor\sqrt{n}\rfloor k = ⌊ n ⌋ B = { v : deg ( v ) > k } B = \{v : \deg(v) > k\} B = { v : deg ( v ) > k }
(i) s ( G ) = 0 s(G) = 0 s ( G ) = 0 Δ ≤ k \Delta\le k Δ ≤ k H = G H = G H = G
(ii) s ( G ) ≤ ∑ v ∈ B deg ( v ) − 1 k ≤ min { 2 m − ∣ B ∣ k , ∣ B ∣ ( n − 2 ) k } ≤ ∣ B ∣ ( n + 1 ) ≤ n ( n + 1 ) s(G) \le\sum_{v\in B}\frac{\deg(v)-1}{k} \le\min\left\{\frac{2m-|B|}{k},\frac{|B|(n-2)}{k}\right\} \le|B|(\sqrt{n}+1) \le n(\sqrt{n}+1) s ( G ) ≤ ∑ v ∈ B k d e g ( v ) − 1 ≤ min { k 2 m − ∣ B ∣ , k ∣ B ∣ ( n − 2 ) } ≤ ∣ B ∣ ( n + 1 ) ≤ n ( n + 1 )
(iii) The complete graph maximises the excess: s ( G ) ≤ s ( K n ) = n ( ⌈ n − 1 k ⌉ − 1 ) s(G) \le s(K_n) = n\left(\left\lceil\frac{n-1}{k}\right\rceil- 1\right) s ( G ) ≤ s ( K n ) = n ( ⌈ k n − 1 ⌉ − 1 ) s ( K n ) ≥ n 3 / 2 − n − n s(K_n) \ge n^{3/2} - n - \sqrt{n} s ( K n ) ≥ n 3/2 − n − n
(iv) For the complete bipartite graph K a , b K_{a,b} K a , b a ≤ b a \le b a ≤ b a + b = n a+b=n a + b = n s ( K a , b ) = a ( ⌈ b k ⌉ − 1 ) + b ( ⌈ a k ⌉ − 1 ) s(K_{a,b}) = a\left(\left\lceil\frac{b}{k}\right\rceil- 1\right) + b\left(\left\lceil\frac{a}{k}\right\rceil- 1\right) s ( K a , b ) = a ( ⌈ k b ⌉ − 1 ) + b ( ⌈ k a ⌉ − 1 ) k k k s ( K n / 2 , n / 2 ) = n ( ⌈ n 2 k ⌉ − 1 ) s(K_{n/2,n/2}) = n\left(\left\lceil\frac{n}{2k}\right\rceil- 1\right) s ( K n /2 , n /2 ) = n ( ⌈ 2 k n ⌉ − 1 ) n n n s ( K 1 , n − 1 ) = ⌈ n − 1 k ⌉ − 1 s(K_{1,n-1}) = \left\lceil\frac{n-1}{k}\right\rceil- 1 s ( K 1 , n − 1 ) = ⌈ k n − 1 ⌉ − 1
Proof. (i) ⌈ d / k ⌉ − 1 = 0 \lceil d/k\rceil- 1 = 0 ⌈ d / k ⌉ − 1 = 0 d ≤ k d \le k d ≤ k Lemma 5.1 ), so when the first vertex has degree Δ ≤ k \Delta\le k Δ ≤ k d ≥ 1 d \ge1 d ≥ 1 ⌈ d / k ⌉ ≤ ( d − 1 ) / k + 1 \lceil d/k\rceil\le(d - 1)/k + 1 ⌈ d / k ⌉ ≤ ( d − 1 ) / k + 1 B B B ∑ v ∈ B deg ( v ) ≤ 2 m \sum_{v\in B}\deg(v) \le2m ∑ v ∈ B deg ( v ) ≤ 2 m deg ( v ) ≤ n − 1 \deg(v) \le n - 1 deg ( v ) ≤ n − 1 k > n − 1 > 0 k > \sqrt{n} - 1 > 0 k > n − 1 > 0 n − 2 < n − 1 = ( n − 1 ) ( n + 1 ) n - 2 < n - 1 = (\sqrt{n} - 1)(\sqrt{n} + 1) n − 2 < n − 1 = ( n − 1 ) ( n + 1 ) ( n − 2 ) / k < n + 1 (n - 2)/k < \sqrt{n} + 1 ( n − 2 ) / k < n + 1 s ( G ) s(G) s ( G ) d d d n − 1 n - 1 n − 1 ∣ B ∣ ≤ n |B| \le n ∣ B ∣ ≤ n K n K_n K n n − 1 > n ≥ k n - 1 > \sqrt{n} \ge k n − 1 > n ≥ k n ≥ 3 n \ge3 n ≥ 3 B B B ⌈ ( n − 1 ) / k ⌉ ≥ ( n − 1 ) / n = n − 1 / n \lceil(n - 1)/k\rceil\ge(n - 1)/\sqrt{n} = \sqrt{n} - 1/\sqrt{n} ⌈( n − 1 ) / k ⌉ ≥ ( n − 1 ) / n = n − 1/ n a a a b b b b b b a a a
:::
Proposition 6.10 (Lower bound of the splitting bound). For every graph G G G n n n k = max ( 1 , ⌊ n ⌋ ) k = \max(1,\lfloor\sqrt{n}\rfloor) k = max ( 1 , ⌊ n ⌋) k ( i ( G ) + s ( G ) ) ≥ n − i ( G ) k\bigl(i(G) + s(G)\bigr) \ge n - i(G) k ( i ( G ) + s ( G ) ) ≥ n − i ( G ) Theorem 6.8 is at least n − i ( G ) n - i(G) n − i ( G )
Proof. Let D D D n − i ( G ) n-i(G) n − i ( G ) ∑ d ∈ D deg ( d ) ≥ n − i ( G ) \sum_{d\in D}\deg(d) \ge n-i(G) ∑ d ∈ D deg ( d ) ≥ n − i ( G ) d ∈ D ∩ B d \in D\cap B d ∈ D ∩ B ⌈ deg ( d ) / k ⌉ − 1 ≥ deg ( d ) / k − 1 \lceil\deg(d)/k\rceil- 1 \ge\deg(d)/k - 1 ⌈ deg ( d ) / k ⌉ − 1 ≥ deg ( d ) / k − 1 s ( G ) s(G) s ( G ) d ∈ D ∖ B d \in D\setminus B d ∈ D ∖ B deg ( d ) ≤ k \deg(d) \le k deg ( d ) ≤ k deg ( d ) / k − 1 ≤ 0 \deg(d)/k - 1 \le0 deg ( d ) / k − 1 ≤ 0 s ( G ) s(G) s ( G ) s ( G ) ≥ ∑ d ∈ D ( deg ( d ) / k − 1 ) ≥ ( n − i ( G ) ) / k − i ( G ) s(G) \ge\sum_{d\in D}(\deg(d)/k - 1) \ge(n-i(G))/k - i(G) s ( G ) ≥ ∑ d ∈ D ( deg ( d ) / k − 1 ) ≥ ( n − i ( G )) / k − i ( G ) k k k k s ( G ) ≥ n − i ( G ) − k i ( G ) k\,s(G) \ge n-i(G)-k\,i(G) k s ( G ) ≥ n − i ( G ) − k i ( G )
:::
Proposition 6.11 (Rigid dense families). If every connected component of G G G K t , t K_{t,t} K t , t
Proof. Gains are local to the components, and whenever the greedy c 3 c_3 c 3 C C C ∣ N [ v ] ∩ U ∣ |N[v] \cap U| ∣ N [ v ] ∩ U ∣ c 3 c_3 c 3 c 3 c_3 c 3 Theorem 6.4 ). Complete multipartite C C C P 1 , … , P r P_1,\ldots,P_r P 1 , … , P r a vertex of P j P_j P j ∣ C ∣ − ∣ P j ∣ + 1 |C|-|P_j|+1 ∣ C ∣ − ∣ P j ∣ + 1 P P P P P P c 3 ∩ C = P c_3 \cap C=P c 3 ∩ C = P i ( C ) = min j ∣ P j ∣ i(C)=\min_j |P_j| i ( C ) = min j ∣ P j ∣ Crown with sides { a 1 , … , a t } \{a_1,\ldots,a_t\} { a 1 , … , a t } { b 1 , … , b t } \{b_1,\ldots,b_t\} { b 1 , … , b t } a i b j ∈ E a_i b_j \in E a i b j ∈ E i ≠ j i\ne j i = j all gains are t t t c 3 c_3 c 3 a 1 a_1 a 1 b j b_j b j j ≠ 1 j\ne1 j = 1 b 1 b_1 b 1 t t t a i a_i a i i ≥ 2 i\ge2 i ≥ 2 b 1 b_1 b 1 c 3 ∩ C = { a 1 , b 1 } c_3\cap C=\{a_1,b_1\} c 3 ∩ C = { a 1 , b 1 } C C C i ( C ) = 2 i(C)=2 i ( C ) = 2 Wheel (a hub joined to a cycle): the hub has the largest gain ∣ C ∣ |C| ∣ C ∣ C C C c 3 ∩ C c_3\cap C c 3 ∩ C i ( C ) = 1 i(C)=1 i ( C ) = 1 Double star (adjacent hubs x , y x,y x , y a ≥ b ≥ 1 a\ge b\ge1 a ≥ b ≥ 1 x x x a + 2 a+2 a + 2 y y y b b b y y y ∣ c 3 ∩ C ∣ = 1 + b |c_3\cap C|=1+b ∣ c 3 ∩ C ∣ = 1 + b x x x y y y y y y x x x a + b a+b a + b i ( C ) = 1 + min ( a , b ) = 1 + b i(C)=1+\min(a,b)=1+b i ( C ) = 1 + min ( a , b ) = 1 + b
By Propositions 6.9 and 6.11, the bound ⌊ n ⌋ ( i ( G ) + s ( G ) ) \lfloor\sqrt{n}\rfloor(i(G)+s(G)) ⌊ n ⌋ ( i ( G ) + s ( G )) Theorem 6.8 is weakest on complete graphs, where s ( G ) s(G) s ( G ) n 3 / 2 n^{3/2} n 3/2 i ( G ) = 1 i(G)=1 i ( G ) = 1 s ( G ) s(G) s ( G ) n 3 / 2 / 2 n^{3/2}/2 n 3/2 /2 i ( G ) i(G) i ( G ) c 3 c_3 c 3 n \sqrt{n} n
Corollary 6.12 (Few vertices of large degree). If ∣ B ∣ ≤ i ( G ) / ( n + 1 ) |B|\le i(G)/(\sqrt{n}+1) ∣ B ∣ ≤ i ( G ) / ( n + 1 ) ∣ B ∣ ( n + 1 ) ( Δ + 1 ) ≤ n |B|(\sqrt{n}+1)(\Delta+1)\le n ∣ B ∣ ( n + 1 ) ( Δ + 1 ) ≤ n s ( G ) ≤ i ( G ) s(G)\le i(G) s ( G ) ≤ i ( G ) S 0 S_0 S 0 Theorem 6.8 has at most 2 ⌊ n ⌋ i ( G ) 2\lfloor\sqrt{n}\rfloor i(G) 2 ⌊ n ⌋ i ( G ) S 0 S_0 S 0 2 n 2\sqrt{n} 2 n
Proof. By Proposition 6.9(ii), s ( G ) ≤ ∣ B ∣ ( n + 1 ) ≤ i ( G ) s(G)\le|B|(\sqrt{n}+1)\le i(G) s ( G ) ≤ ∣ B ∣ ( n + 1 ) ≤ i ( G ) i ( G ) ≥ n / ( Δ + 1 ) i(G)\ge n/(\Delta+1) i ( G ) ≥ n / ( Δ + 1 ) Lemma 6.1 . Theorem 6.8 gives the rest.
Algorithm 5 is defined for every block size k ≥ 1 k\ge1 k ≥ 1 ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] ε _\varepsilon ε k ε = max ( 1 , ⌊ n 1 − ε ⌋ ) k_\varepsilon=\max(1,\lfloor n^{1-\varepsilon}\rfloor) k ε = max ( 1 , ⌊ n 1 − ε ⌋) max ( 1 , ⌊ n ⌋ ) \max(1,\lfloor\sqrt{n}\rfloor) max ( 1 , ⌊ n ⌋) B ε = { v : deg G ( v ) > k ε } B_\varepsilon=\{v:\deg_G(v)>k_\varepsilon\} B ε = { v : deg G ( v ) > k ε }
s ε ( G ) = ∑ v ∈ B ε ( ⌈ deg G ( v ) k ε ⌉ − 1 ) . s_\varepsilon(G)=\sum_{v\in B_\varepsilon}\left(\left\lceil\frac{\deg_G(v)}{k_\varepsilon}\right\rceil-1\right). s ε ( G ) = v ∈ B ε ∑ ( ⌈ k ε deg G ( v ) ⌉ − 1 ) . Strategy c 13 c_{13} c 13 1 / 2 _{1/2} 1/2 k 1 / 2 = k k_{1/2}=k k 1/2 = k s 1 / 2 ( G ) = s ( G ) s_{1/2}(G)=s(G) s 1/2 ( G ) = s ( G )
Theorem 6.13 (Parametric degree splitting). Let ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] ε _\varepsilon ε S 0 S_0 S 0 G G G
∣ S 0 ∣ ≤ k ε ( i ( G ) + s ε ( G ) ) ≤ n 1 − ε ( i ( G ) + s ε ( G ) ) . |S_0|\le k_\varepsilon(i(G)+s_\varepsilon(G))\le n^{1-\varepsilon}(i(G)+s_\varepsilon(G)). ∣ S 0 ∣ ≤ k ε ( i ( G ) + s ε ( G )) ≤ n 1 − ε ( i ( G ) + s ε ( G )) . If S 0 S_0 S 0 G G G S ε S_\varepsilon S ε ε _\varepsilon ε G G G ∣ S ε ∣ ≤ k ε ( i ( G ) + s ε ( G ) ) |S_\varepsilon|\le k_\varepsilon(i(G)+s_\varepsilon(G)) ∣ S ε ∣ ≤ k ε ( i ( G ) + s ε ( G )) ε = 1 2 \varepsilon=\frac{1}{2} ε = 2 1 Theorem 6.8 .
Proof. The statements and proofs of Lemmas 5.1 , 6.6 and 6.7 use only that k k k k ε k_\varepsilon k ε B ε B_\varepsilon B ε s ε ( G ) s_\varepsilon(G) s ε ( G ) k k k B B B s ( G ) s(G) s ( G ) H ε H_\varepsilon H ε k ε k_\varepsilon k ε i ( H ε ) ≤ i ( G ) + s ε ( G ) i(H_\varepsilon)\le i(G)+s_\varepsilon(G) i ( H ε ) ≤ i ( G ) + s ε ( G ) S 0 S_0 S 0 ∣ S 0 ∣ ≤ ∣ S H ∣ |S_0|\le|S_{H}| ∣ S 0 ∣ ≤ ∣ S H ∣ S H S_H S H H ε H_\varepsilon H ε Lemma 6.1 , applied componentwise with max ( 1 , Δ ( H ε ) ) ≤ k ε \max(1,\Delta(H_\varepsilon))\le k_\varepsilon max ( 1 , Δ ( H ε )) ≤ k ε ∣ S H ∣ ≤ k ε i ( H ε ) |S_H|\le k_\varepsilon i(H_\varepsilon) ∣ S H ∣ ≤ k ε i ( H ε ) k ε ≤ n 1 − ε k_\varepsilon\le n^{1-\varepsilon} k ε ≤ n 1 − ε n 1 − ε ≥ 1 n^{1-\varepsilon}\ge1 n 1 − ε ≥ 1 n ≥ 1 n\ge1 n ≥ 1 S 0 S_0 S 0 S ε S_\varepsilon S ε Lemma 6.7 ), and S ε S_\varepsilon S ε Lemma 4.1 .
Corollary 6.14 (Consequences of Theorem 6.13 ). Let G G G n ≥ 1 n\ge1 n ≥ 1 m m m ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ]
(i) Monotonicity. If 0 < ε ′ ≤ ε 0<\varepsilon'\le\varepsilon 0 < ε ′ ≤ ε k ε ′ ≥ k ε k_{\varepsilon'}\ge k_\varepsilon k ε ′ ≥ k ε B ε ′ ⊆ B ε B_{\varepsilon'}\subseteq B_\varepsilon B ε ′ ⊆ B ε s ε ′ ( G ) ≤ s ε ( G ) s_{\varepsilon'}(G)\le s_\varepsilon(G) s ε ′ ( G ) ≤ s ε ( G )
(ii) Weighted excess. ∑ v ∈ B ε ( deg ( v ) − k ε ) ≤ k ε s ε ( G ) ≤ ∑ v ∈ B ε ( deg ( v ) − 1 ) ≤ 2 m − ∣ B ε ∣ \sum_{v\in B_{\varepsilon}}(\deg(v)-k_\varepsilon)\le k_\varepsilon s_\varepsilon(G)\le\sum_{v\in B_{\varepsilon}}(\deg(v)-1)\le2m-|B_\varepsilon| ∑ v ∈ B ε ( deg ( v ) − k ε ) ≤ k ε s ε ( G ) ≤ ∑ v ∈ B ε ( deg ( v ) − 1 ) ≤ 2 m − ∣ B ε ∣ Theorem 6.13 satisfies k ε ( i ( G ) + s ε ( G ) ) ≤ k ε i ( G ) + 2 m − ∣ B ε ∣ k_\varepsilon(i(G)+s_\varepsilon(G))\le k_\varepsilon i(G)+2m-|B_\varepsilon| k ε ( i ( G ) + s ε ( G )) ≤ k ε i ( G ) + 2 m − ∣ B ε ∣
(iii) Lower bound. k ε i ( G ) + s ε ( G ) ≥ n − i ( G ) k_\varepsilon i(G)+s_\varepsilon(G)\ge n-i(G) k ε i ( G ) + s ε ( G ) ≥ n − i ( G )
(iv) Vanishing excess. s ε ( G ) = 0 s_{\varepsilon}(G)=0 s ε ( G ) = 0 Δ ≤ k ε \Delta\le k_{\varepsilon} Δ ≤ k ε k ε ( i ( G ) + s ε ( G ) ) = k ε i ( G ) ≥ max ( 1 , Δ ) i ( G ) k_{\varepsilon}\left(i(G)+s_{\varepsilon}(G)\right)=k_{\varepsilon}i(G)\ge\max(1,\Delta)i(G) k ε ( i ( G ) + s ε ( G ) ) = k ε i ( G ) ≥ max ( 1 , Δ ) i ( G ) ε < 1 \varepsilon<1 ε < 1 Δ ≤ D \Delta\le D Δ ≤ D D ≥ 1 D\ge1 D ≥ 1 s ε ( G ) = 0 s_{\varepsilon}(G)=0 s ε ( G ) = 0 n ≥ D 1 / ( 1 − ε ) n\ge D^{1/(1-\varepsilon)} n ≥ D 1/ ( 1 − ε ) s 1 / 4 ( G ) = 0 s_{1/4}(G)=0 s 1/4 ( G ) = 0 n ≥ D 4 / 3 n\ge D^{4/3} n ≥ D 4/3 n ≥ 6 n\ge6 n ≥ 6
(vi) Bounded excess. If s ε ( G ) ≤ i ( G ) s_{\varepsilon}(G)\le i(G) s ε ( G ) ≤ i ( G ) ∣ S 0 ∣ ≤ 2 k ε i ( G ) ≤ 2 n 1 − ε i ( G ) |S_0|\le2k_{\varepsilon}i(G)\le2n^{1-\varepsilon}i(G) ∣ S 0 ∣ ≤ 2 k ε i ( G ) ≤ 2 n 1 − ε i ( G ) ε _{\varepsilon} ε ∣ S ε ∣ ≤ 2 n 1 − ε i ( G ) |S_{\varepsilon}|\le2n^{1-\varepsilon}i(G) ∣ S ε ∣ ≤ 2 n 1 − ε i ( G ) S 0 S_0 S 0
(vii) Complete graphs. For n ≥ 2 n\ge2 n ≥ 2 s ε ( K n ) = n ( ⌈ ( n − 1 ) / k ε ⌉ − 1 ) s_{\varepsilon}(K_n)=n\left(\left\lceil(n-1)/k_{\varepsilon}\right\rceil-1\right) s ε ( K n ) = n ( ⌈ ( n − 1 ) / k ε ⌉ − 1 ) 0 0 0 k ε ≥ n − 1 k_{\varepsilon}\ge n-1 k ε ≥ n − 1 n n n ε ∈ ( 0 , 1 ] \varepsilon\in(0,1] ε ∈ ( 0 , 1 ] n 0 n_0 n 0 s ε ( K n ) ≥ n s_{\varepsilon}(K_n)\ge n s ε ( K n ) ≥ n n ≥ n 0 n\ge n_0 n ≥ n 0 K n K_n K n
Proof. (i) n 1 − ε ′ ≥ n 1 − ε n^{1-\varepsilon'}\ge n^{1-\varepsilon} n 1 − ε ′ ≥ n 1 − ε n ≥ 1 n\ge1 n ≥ 1 k ε ′ ≥ k ε k_{\varepsilon'}\ge k_{\varepsilon} k ε ′ ≥ k ε k ε ′ k_{\varepsilon'} k ε ′ k ε k_{\varepsilon} k ε ⌈ d / k ⌉ \lceil d/k\rceil ⌈ d / k ⌉ k k k s ε ′ ( G ) s_{\varepsilon'}(G) s ε ′ ( G ) s ε ( G ) s_{\varepsilon}(G) s ε ( G ) d , k ≥ 1 d,k\ge1 d , k ≥ 1 d / k ≤ ⌈ d / k ⌉ ≤ ( d − 1 ) / k + 1 d/k\le\lceil d/k\rceil\le(d-1)/k+1 d / k ≤ ⌈ d / k ⌉ ≤ ( d − 1 ) / k + 1 d − k ≤ k ( ⌈ d / k ⌉ − 1 ) ≤ d − 1 d-k\le k(\lceil d/k\rceil-1)\le d-1 d − k ≤ k (⌈ d / k ⌉ − 1 ) ≤ d − 1 B ε B_{\varepsilon} B ε ∑ v ∈ B ε deg ( v ) ≤ 2 m \sum_{v\in B_{\varepsilon}}\deg(v)\le2m ∑ v ∈ B ε deg ( v ) ≤ 2 m k k k k ε k_{\varepsilon} k ε B ε B_{\varepsilon} B ε s ε ( G ) s_{\varepsilon}(G) s ε ( G ) ⌈ d / k ε ⌉ − 1 = 0 \lceil d/k_{\varepsilon}\rceil-1=0 ⌈ d / k ε ⌉ − 1 = 0 d ≤ k ε d\le k_{\varepsilon} d ≤ k ε s ε ( G ) = 0 s_{\varepsilon}(G)=0 s ε ( G ) = 0 B ε = ∅ B_{\varepsilon}=\varnothing B ε = ∅ Δ ≤ k ε \Delta\le k_{\varepsilon} Δ ≤ k ε k ε ≥ max ( 1 , Δ ) k_{\varepsilon}\ge\max(1,\Delta) k ε ≥ max ( 1 , Δ ) D ≥ 1 D\ge1 D ≥ 1 ⌊ n 1 − ε ⌋ ≥ D \lfloor n^{1-\varepsilon}\rfloor\ge D ⌊ n 1 − ε ⌋ ≥ D n 1 − ε ≥ D n^{1-\varepsilon}\ge D n 1 − ε ≥ D n ≥ D 1 / ( 1 − ε ) n\ge D^{1/(1-\varepsilon)} n ≥ D 1/ ( 1 − ε ) k ε ≥ D ≥ Δ k_{\varepsilon}\ge D\ge\Delta k ε ≥ D ≥ Δ ε = 1 4 \varepsilon=\frac14 ε = 4 1 4 3 \frac43 3 4 n ≥ 4 n\ge4 n ≥ 4 ⌊ 6 3 / 4 ⌋ = 3 \lfloor6^{3/4}\rfloor=3 ⌊ 6 3/4 ⌋ = 3 k 1 / 4 ≥ 3 = Δ k_{1/4}\ge3=\Delta k 1/4 ≥ 3 = Δ n ≥ 6 n\ge6 n ≥ 6 max ( 1 , Δ ) ≤ k ε ≤ n 1 − ε \max(1,\Delta)\le k_{\varepsilon}\le n^{1-\varepsilon} max ( 1 , Δ ) ≤ k ε ≤ n 1 − ε ∣ S ∣ ≤ max ( 1 , Δ ) i ( G ) |S|\le\max(1,\Delta)i(G) ∣ S ∣ ≤ max ( 1 , Δ ) i ( G ) ε = 1 4 \varepsilon=\frac14 ε = 4 1 Δ ≤ ⌊ n 3 / 4 ⌋ \Delta\le\lfloor n^{3/4}\rfloor Δ ≤ ⌊ n 3/4 ⌋ max ( 1 , Δ ) ≤ n 3 / 4 \max(1,\Delta)\le n^{3/4} max ( 1 , Δ ) ≤ n 3/4 n ≥ 1 n\ge1 n ≥ 1 Theorem 6.13 with i ( G ) + s ε ( G ) ≤ 2 i ( G ) i(G)+s_{\varepsilon}(G)\le2i(G) i ( G ) + s ε ( G ) ≤ 2 i ( G ) K n K_n K n n − 1 n-1 n − 1 k ε ≥ n − 1 k_{\varepsilon}\ge n-1 k ε ≥ n − 1 B ε = ∅ B_{\varepsilon}=\varnothing B ε = ∅ B ε B_{\varepsilon} B ε ⌈ ( n − 1 ) / k ε ⌉ ≥ 2 \lceil(n-1)/k_{\varepsilon}\rceil\ge2 ⌈( n − 1 ) / k ε ⌉ ≥ 2 ε > 0 \varepsilon>0 ε > 0 n 1 − ε / ( n − 1 ) → 0 n^{1-\varepsilon}/(n-1)\to0 n 1 − ε / ( n − 1 ) → 0 k ε ≤ n 1 − ε < n − 1 k_{\varepsilon}\le n^{1-\varepsilon}<n-1 k ε ≤ n 1 − ε < n − 1 n n n
The splitting excess on hard families. Proposition 6.15 and Table 3 give s ( G ) s(G) s ( G ) § 7 , it encodes a UG-hard vertex cover problem, and on further structured families.
Proposition 6.15 (Splitting excess on graph families). Let k = ⌊ n ⌋ k=\lfloor\sqrt{n}\rfloor k = ⌊ n ⌋
(a) Bounded degree. If Δ ≤ D \Delta\le D Δ ≤ D D D D s ( G ) = 0 s(G)=0 s ( G ) = 0 n ≥ D 2 n\ge D^2 n ≥ D 2 n ≥ 10 n\ge10 n ≥ 10 Proposition 6.16 ); for graphs and bipartite graphs of maximum degree at most B B B n ≥ B 2 n\ge B^2 n ≥ B 2 B B B n ≥ B 2 n\ge B^2 n ≥ B 2 H H H Δ ( H ) ≤ 2 D \Delta(H)\le2D Δ ( H ) ≤ 2 D ∣ V ( H ) ∣ ≥ 2 D 2 |V(H)|\ge2D^2 ∣ V ( H ) ∣ ≥ 2 D 2 d d d n ≥ d 2 n\ge d^2 n ≥ d 2 [22 ] ; for grids with n ≥ 16 n\ge16 n ≥ 16 Q q Q_q Q q q ≥ 4 q\ge4 q ≥ 4
(b) Khot–Regev graphs. The YES graph with N N N s b s_b s b d d d n = N s b n=Ns_b n = N s b d s b ds_b d s b s ( G ) ≤ n ( ⌈ d s b / k ⌉ − 1 ) s(G)\le n(\lceil ds_b/k\rceil-1) s ( G ) ≤ n (⌈ d s b / k ⌉ − 1 ) s ( G ) = 0 s(G)=0 s ( G ) = 0 N ≥ d 2 s b N\ge d^2s_b N ≥ d 2 s b
(c) Sparse graphs. s ( G ) ≤ 2 m / k s(G)\le2m/k s ( G ) ≤ 2 m / k s ( G ) ≤ ( 6 n − 12 ) / k s(G)\le(6n-12)/k s ( G ) ≤ ( 6 n − 12 ) / k s ( G ) ≤ ( 4 n − 8 ) / k s(G)\le(4n-8)/k s ( G ) ≤ ( 4 n − 8 ) / k Proposition 6.18 ), and for graphs with m ≤ c n m\le cn m ≤ c n s ( G ) ≤ 2 c n / k ≤ 2 c ( n + 2 ) s(G)\le2cn/k\le2c(\sqrt{n}+2) s ( G ) ≤ 2 c n / k ≤ 2 c ( n + 2 ) n ≥ 4 n\ge4 n ≥ 4
(d) Sparse random graphs. For a constant c > 0 c>0 c > 0 G ( n , c / n ) G(n,c/n) G ( n , c / n ) s ( G ) = 0 s(G)=0 s ( G ) = 0 n → ∞ n\to\infty n → ∞
(e) Few hubs. s ( K 1 , n − 1 ) = s ( W n ) = ⌈ ( n − 1 ) / k ⌉ − 1 s(K_{1,n-1})=s(W_n)=\lceil(n-1)/k\rceil-1 s ( K 1 , n − 1 ) = s ( W n ) = ⌈( n − 1 ) / k ⌉ − 1 a a a b b b s = ( ⌈ ( a + 1 ) / k ⌉ − 1 ) + ( ⌈ ( b + 1 ) / k ⌉ − 1 ) s=(\lceil(a+1)/k\rceil-1)+(\lceil(b+1)/k\rceil-1) s = (⌈( a + 1 ) / k ⌉ − 1 ) + (⌈( b + 1 ) / k ⌉ − 1 )
(f) Dense graphs. If the minimum degree satisfies δ ( G ) > k \delta(G)>k δ ( G ) > k s ( G ) ≥ n ( ⌈ δ ( G ) / k ⌉ − 1 ) s(G)\ge n(\lceil\delta(G)/k\rceil-1) s ( G ) ≥ n (⌈ δ ( G ) / k ⌉ − 1 ) n 1 , … , n r n_1,\ldots,n_r n 1 , … , n r s = ∑ j n j ( ⌈ ( n − n j ) / k ⌉ − 1 ) s=\sum_j n_j(\lceil(n-n_j)/k\rceil-1) s = ∑ j n j (⌈( n − n j ) / k ⌉ − 1 ) n = 2 t n=2t n = 2 t s = n ( ⌈ ( t − 1 ) / k ⌉ − 1 ) s=n(\lceil(t-1)/k\rceil-1) s = n (⌈( t − 1 ) / k ⌉ − 1 )
Proof. (a) ⌊ n ⌋ ≥ D \lfloor\sqrt{n}\rfloor\ge D ⌊ n ⌋ ≥ D n ≥ D 2 n \ge D^2 n ≥ D 2 Δ ≤ k \Delta\le k Δ ≤ k s ( G ) = 0 s(G)=0 s ( G ) = 0 h ( H ) h(H) h ( H ) ∣ V ( H ) ∣ + 6 ∣ E ( H ) ∣ |V(H)|+6|E(H)| ∣ V ( H ) ∣ + 6∣ E ( H ) ∣ max ( Δ ( H ) , 3 ) \max(\Delta(H),3) max ( Δ ( H ) , 3 ) Q q Q_q Q q q ≤ 2 q / 2 q\le2q/2 q ≤ 2 q /2 q ≥ 4 q\ge4 q ≥ 4 ( v , x ) (v,x) ( v , x ) d d d s b s_b s b d s b ≤ N s b ds_b\le\sqrt{N}s_b d s b ≤ N s b N ≥ d 2 N\ge d^2 N ≥ d 2 m ≤ 3 n − 6 m\le3n-6 m ≤ 3 n − 6 m ≤ 2 n − 4 m\le2n-4 m ≤ 2 n − 4 n / ⌊ n ⌋ < n / ( n − 1 ) = n + 1 + 1 / ( n − 1 ) ≤ n + 2 n/\lfloor\sqrt{n}\rfloor<n/(\sqrt{n}-1)=\sqrt{n}+1+1/(\sqrt{n}-1)\le\sqrt{n}+2 n / ⌊ n ⌋ < n / ( n − 1 ) = n + 1 + 1/ ( n − 1 ) ≤ n + 2 n ≥ 4. ( d ) F o r n\ge4. (d) For n ≥ 4. ( d ) F or t t t ( c / n ) t ≤ ( e c / t ) t ≤ ( e c / n ) n (c/n)^t\le(ec/t)^t\le(ec/\sqrt{n})^{\sqrt{n}} ( c / n ) t ≤ ( ec / t ) t ≤ ( ec / n ) n t > e c t>ec t > ec k k k n ( e c / n ) n → 0 n(ec/\sqrt{n})^{\sqrt{n}}\to0 n ( ec / n ) n → 0 s ( G ) = 0 s(G)=0 s ( G ) = 0 n − 1 n-1 n − 1 a + 1 a+1 a + 1 b + 1 b+1 b + 1 3 ≤ k 3\le k 3 ≤ k n ≥ 9 n\ge9 n ≥ 9 s s s B B B ⌈ deg ( v ) / k ⌉ ≥ ⌈ δ ( G ) / k ⌉ \lceil\deg(v)/k\rceil\ge\lceil\delta(G)/k\rceil ⌈ deg ( v ) / k ⌉ ≥ ⌈ δ ( G ) / k ⌉ j j j n − n j n-n_j n − n j t − 1 t-1 t − 1
By Proposition 6.15 (a), on every family of bounded degree D D D n ≥ D 2 n\ge D^2 n ≥ D 2 c 13 c_{13} c 13 G G G Theorem 6.8 gives the ratio ⌊ n ⌋ \lfloor\sqrt{n}\rfloor ⌊ n ⌋ Δ \Delta Δ n \sqrt{n} n n \sqrt{n} n O ( n ) O(n) O ( n ) n 3 / 2 n^{3/2} n 3/2 § 9.4 , Δ ≤ ⌊ n ⌋ \Delta\le\lfloor\sqrt{n}\rfloor Δ ≤ ⌊ n ⌋ Table 6 : n ≥ 106 n\ge106 n ≥ 106 Δ ≤ 6 \Delta\le6 Δ ≤ 6 n ≥ 500 n\ge500 n ≥ 500 Δ ≤ 5 \Delta\le5 Δ ≤ 5 n ≥ 48172 n\ge48172 n ≥ 48172 Δ = 64 \Delta=64 Δ = 64 s = 0 s=0 s = 0
Table 6. Instances of the reductions of Chlebík and Chlebíková. “Ref.” counts instances with i i i ∣ D ∣ |D| ∣ D ∣ ∣ D ∣ / L |D|/L ∣ D ∣/ L ∣ D ∣ − L |D| - L ∣ D ∣ − L ∣ C D ∣ / L τ |C_D|/L_\tau ∣ C D ∣/ L τ
Cubic graphs. MIDS is APX-hard on cubic graphs [6 ] and NP-hard on cubic planar [5 ] and cubic planar bipartite graphs [4 ] . On these graphs the splitting excess is bounded by an absolute constant, and it vanishes from ten vertices on.
Proposition 6.16 (Splitting excess on cubic and bounded-degree graphs). Let k = max ( 1 , ⌊ n ⌋ ) k=\max(1,\lfloor\sqrt{n}\rfloor) k = max ( 1 , ⌊ n ⌋)
(i) If G G G s ( G ) = n s(G)=n s ( G ) = n n ∈ { 4 , 6 , 8 } n\in\{4,6,8\} n ∈ { 4 , 6 , 8 } s ( G ) = 0 s(G)=0 s ( G ) = 0 n ≥ 10 n\ge10 n ≥ 10 s ( G ) ≤ 8 s(G)\le8 s ( G ) ≤ 8
(ii) If Δ ( G ) ≤ 3 \Delta(G)\le3 Δ ( G ) ≤ 3 s ( G ) ≤ 8 s(G)\le8 s ( G ) ≤ 8 s ( G ) = 0 s(G)=0 s ( G ) = 0 n ≥ 9 n\ge9 n ≥ 9
(iii) If Δ ( G ) ≤ D \Delta(G)\le D Δ ( G ) ≤ D D ≥ 2 D\ge2 D ≥ 2 s ( G ) < D 2 ( D − 1 ) s(G)<D^2(D-1) s ( G ) < D 2 ( D − 1 ) s ( G ) = 0 s(G)=0 s ( G ) = 0 n ≥ D 2 n\ge D^2 n ≥ D 2
Proof. (i) A cubic graph has an even number n ≥ 4 n\ge4 n ≥ 4 3 n = 2 m 3n=2m 3 n = 2 m n ∈ { 4 , 6 , 8 } n\in\{4,6,8\} n ∈ { 4 , 6 , 8 } k = 2 k=2 k = 2 3 > k 3>k 3 > k ⌈ 3 / 2 ⌉ − 1 = 1 \lceil3/2\rceil-1=1 ⌈ 3/2 ⌉ − 1 = 1 s ( G ) = n ≤ 8 s(G)=n\le8 s ( G ) = n ≤ 8 n ≥ 10 n\ge10 n ≥ 10 k ≥ 3 = Δ k\ge3=\Delta k ≥ 3 = Δ s ( G ) = 0 s(G)=0 s ( G ) = 0 n ≤ 3 n \le3 n ≤ 3 k = 1 k = 1 k = 1 ⌈ 2 / 1 ⌉ − 1 = 1 \lceil2/1 \rceil- 1 = 1 ⌈ 2/1 ⌉ − 1 = 1 s ( G ) ≤ 3 s(G) \le3 s ( G ) ≤ 3 4 ≤ n ≤ 8 4 \le n \le8 4 ≤ n ≤ 8 k = 2 k = 2 k = 2 s ( G ) ≤ n ≤ 8 s(G) \le n \le8 s ( G ) ≤ n ≤ 8 n ≥ 9 n \ge9 n ≥ 9 k ≥ 3 ≥ Δ k \ge3 \ge\Delta k ≥ 3 ≥ Δ s ( G ) = 0 s(G) = 0 s ( G ) = 0 n ≥ D 2 n \ge D^2 n ≥ D 2 k ≥ D ≥ Δ k \ge D \ge\Delta k ≥ D ≥ Δ s ( G ) = 0 s(G) = 0 s ( G ) = 0 n < D 2 n < D^2 n < D 2 ⌈ deg ( v ) / k ⌉ − 1 ≤ D − 1 \lceil\deg(v)/k \rceil- 1 \le D - 1 ⌈ deg ( v ) / k ⌉ − 1 ≤ D − 1 k ≥ 1 k \ge1 k ≥ 1 s ( G ) ≤ n ( D − 1 ) < D 2 ( D − 1 ) s(G) \le n(D - 1) < D^2(D - 1) s ( G ) ≤ n ( D − 1 ) < D 2 ( D − 1 )
On a cubic graph with n ≥ 10 n \ge10 n ≥ 10 H = G H = G H = G c 13 c_{13} c 13 G G G
Theorem 6.17 (Regular graphs). If G G G d d d d ≥ 1 d \ge1 d ≥ 1 S S S G G G ∣ S ∣ ≤ n / 2 |S| \le n/2 ∣ S ∣ ≤ n /2 ∣ S ∣ / i ( G ) ≤ ( d + 1 ) / 2 |S|/i(G) \le(d + 1)/2 ∣ S ∣/ i ( G ) ≤ ( d + 1 ) /2 n / 4 ≤ i ( G ) ≤ ∣ S ∣ ≤ n / 2 n/4 \le i(G) \le|S| \le n/2 n /4 ≤ i ( G ) ≤ ∣ S ∣ ≤ n /2
Proof. Let I I I G G G I I I d d d V ∖ I V \setminus I V ∖ I V ∖ I V \setminus I V ∖ I d d d I I I I I I V ∖ I V \setminus I V ∖ I d ∣ I ∣ ≤ d ( n − ∣ I ∣ ) d|I| \le d(n - |I|) d ∣ I ∣ ≤ d ( n − ∣ I ∣ ) ∣ I ∣ ≤ n / 2 |I| \le n/2 ∣ I ∣ ≤ n /2 Theorem 4.3 ), and Lemma 6.1 gives i ( G ) ≥ n / ( d + 1 ) i(G) \ge n/(d + 1) i ( G ) ≥ n / ( d + 1 ) ∣ S ∣ / i ( G ) ≤ ( n / 2 ) / ( n / ( d + 1 ) ) = ( d + 1 ) / 2 |S|/i(G) \le(n/2)/(n/(d + 1)) = (d + 1)/2 ∣ S ∣/ i ( G ) ≤ ( n /2 ) / ( n / ( d + 1 )) = ( d + 1 ) /2 d = 3 d = 3 d = 3 n / 4 ≤ i ( G ) n/4 \le i(G) n /4 ≤ i ( G ) ( d + 1 ) / 2 = 2 (d + 1)/2 = 2 ( d + 1 ) /2 = 2
Planar graphs. MIDS is NP-hard on cubic planar graphs [5 ] and NP-complete on cubic planar bipartite graphs [4 ] , hence on planar and on bipartite planar graphs. On planar graphs the splitting excess is not bounded by a constant, but it is at most 2 n + O ( 1 ) 2\sqrt{n} + O(1) 2 n + O ( 1 )
Proposition 6.18 (Splitting excess on planar graphs). Let G G G n n n k = ⌊ n ⌋ k = \lfloor\sqrt{n} \rfloor k = ⌊ n ⌋ B = { v : deg ( v ) > k } B = \{v : \deg(v) > k\} B = { v : deg ( v ) > k } b = ∣ B ∣ b = |B| b = ∣ B ∣
(i) If n ≥ 36 n \ge36 n ≥ 36 b < 2 n / ( k − 5 ) b < 2n/(k - 5) b < 2 n / ( k − 5 ) s ( G ) < 2 n / k + 10 n / ( k ( k − 5 ) ) s(G) < 2n/k + 10n/(k(k - 5)) s ( G ) < 2 n / k + 10 n / ( k ( k − 5 )) n ≥ 400 n \ge400 n ≥ 400 s ( G ) < 2 n + 19 s(G) < 2\sqrt{n} + 19 s ( G ) < 2 n + 19
(ii) If G G G n ≥ 16 n \ge16 n ≥ 16 b < 2 n / ( k − 3 ) b < 2n/(k - 3) b < 2 n / ( k − 3 ) s ( G ) < 2 n / k + 6 n / ( k ( k − 3 ) ) s(G) < 2n/k + 6n/(k(k - 3)) s ( G ) < 2 n / k + 6 n / ( k ( k − 3 )) n ≥ 400 n \ge400 n ≥ 400 s ( G ) < 2 n + 12 s(G) < 2\sqrt{n} + 12 s ( G ) < 2 n + 12
(iii) For every n ≥ 16 n \ge16 n ≥ 16 K 2 , n − 2 K_{2,n-2} K 2 , n − 2 s ( K 2 , n − 2 ) = 2 ( ⌈ ( n − 2 ) / k ⌉ − 1 ) ≥ 2 n − 3 s(K_{2,n-2}) = 2(\lceil(n - 2)/k \rceil- 1) \ge2\sqrt{n} - 3 s ( K 2 , n − 2 ) = 2 (⌈( n − 2 ) / k ⌉ − 1 ) ≥ 2 n − 3
Proof. Let R = V ∖ B R = V \setminus B R = V ∖ B e B e_B e B B B B e B R e_{BR} e B R B B B R R R D = ∑ v ∈ B deg ( v ) = 2 e B + e B R D = \sum_{v \in B} \deg(v) = 2e_B + e_{BR} D = ∑ v ∈ B deg ( v ) = 2 e B + e B R B B B R R R e B R < 2 n e_{BR} < 2n e B R < 2 n p ≥ 3 p \ge3 p ≥ 3 p ≤ 2 p \le2 p ≤ 2 G [ B ] G[B] G [ B ] e B ≤ 3 b e_B \le3b e B ≤ 3 b D < 6 b + 2 n D < 6b + 2n D < 6 b + 2 n B B B k + 1 k + 1 k + 1 b ( k + 1 ) ≤ D < 6 b + 2 n b(k + 1) \le D < 6b + 2n b ( k + 1 ) ≤ D < 6 b + 2 n b ( k − 5 ) < 2 n b(k - 5) < 2n b ( k − 5 ) < 2 n k ≥ 6 k \ge6 k ≥ 6 n ≥ 36 n \ge36 n ≥ 36 s ( G ) ≤ ( D − b ) / k < ( 5 b + 2 n ) / k < 2 n / k + 10 n / ( k ( k − 5 ) ) s(G) \le(D - b)/k < (5b + 2n)/k < 2n/k + 10n/(k(k - 5)) s ( G ) ≤ ( D − b ) / k < ( 5 b + 2 n ) / k < 2 n / k + 10 n / ( k ( k − 5 )) n ≥ 400 n \ge400 n ≥ 400 k ≥ 20 k \ge20 k ≥ 20 k − 5 ≥ 3 k / 4 k - 5 \ge3k/4 k − 5 ≥ 3 k /4 n < ( k + 1 ) 2 n < (k + 1)^2 n < ( k + 1 ) 2 n / k 2 < 1.11 n/k^2 < 1.11 n / k 2 < 1.11 10 n / ( k ( k − 5 ) ) ≤ 40 3 n / k 2 < 14.8 10n/(k(k - 5)) \le\frac{40}{3}n/k^2 < 14.8 10 n / ( k ( k − 5 )) ≤ 3 40 n / k 2 < 14.8 n / k < n + 2 n/k < \sqrt{n} + 2 n / k < n + 2 s ( G ) < 2 n + 4 + 14.8 < 2 n + 19 s(G) < 2\sqrt{n} + 4 + 14.8 < 2\sqrt{n} + 19 s ( G ) < 2 n + 4 + 14.8 < 2 n + 19 G [ B ] G[B] G [ B ] e B ≤ 2 b e_B \le2b e B ≤ 2 b D < 4 b + 2 n D < 4b + 2n D < 4 b + 2 n b ( k − 3 ) < 2 n b(k - 3) < 2n b ( k − 3 ) < 2 n k ≥ 4 k \ge4 k ≥ 4 n ≥ 16 n \ge16 n ≥ 16 s ( G ) < ( 3 b + 2 n ) / k < 2 n / k + 6 n / ( k ( k − 3 ) ) s(G) < (3b + 2n)/k < 2n/k + 6n/(k(k - 3)) s ( G ) < ( 3 b + 2 n ) / k < 2 n / k + 6 n / ( k ( k − 3 )) n ≥ 400 n \ge400 n ≥ 400 k − 3 ≥ 17 k / 20 k - 3 \ge17k/20 k − 3 ≥ 17 k /20 6 n / ( k ( k − 3 ) ) ≤ 120 17 n / k 2 < 7.9 6n/(k(k - 3)) \le\frac{120}{17}n/k^2 < 7.9 6 n / ( k ( k − 3 )) ≤ 17 120 n / k 2 < 7.9 s ( G ) < 2 n + 4 + 7.9 < 2 n + 12 s(G) < 2\sqrt{n} + 4 + 7.9 < 2\sqrt{n} + 12 s ( G ) < 2 n + 4 + 7.9 < 2 n + 12 K 2 , n − 2 K_{2,n-2} K 2 , n − 2 n − 2 ≥ n ≥ k n - 2 \ge\sqrt{n} \ge k n − 2 ≥ n ≥ k B B B 2 ≤ k 2 \le k 2 ≤ k s = 2 ( ⌈ ( n − 2 ) / k ⌉ − 1 ) ≥ 2 ( n − 2 ) / n − 2 = 2 n − 2 − 4 / n ≥ 2 n − 3 s = 2(\lceil(n - 2)/k \rceil- 1) \ge2(n - 2)/\sqrt{n} - 2 = 2\sqrt{n} - 2 - 4/\sqrt{n} \ge2\sqrt{n} - 3 s = 2 (⌈( n − 2 ) / k ⌉ − 1 ) ≥ 2 ( n − 2 ) / n − 2 = 2 n − 2 − 4/ n ≥ 2 n − 3
Circle graphs. A circle graph is the intersection graph of a set of chords of a circle; MIDS is NP-complete on circle graphs and, unless P = NP, not approximable within n ε n^\varepsilon n ε ε < 1 \varepsilon< 1 ε < 1 [3 ] . A chord model of n n n 2 n 2n 2 n 1 , … , 2 n 1,\ldots,2n 1 , … , 2 n v v v ( a v , b v ) (a_v,b_v) ( a v , b v ) a v < b v a_v < b_v a v < b v
Proposition 6.19 (Splitting excess on circle graphs). (i) For a circle graph given by a chord model, deg ( v ) = b v − a v − 1 − 2 ∣ { u : a v < a u < b u < b v } ∣ \deg(v) = b_v - a_v - 1 - 2|\{u : a_v < a_u < b_u < b_v\}| deg ( v ) = b v − a v − 1 − 2∣ { u : a v < a u < b u < b v } ∣ v v v B B B s ( G ) s(G) s ( G ) O ( n log n ) O(n \log n) O ( n log n )
(ii) For every n ≥ 3 n \ge3 n ≥ 3 K n K_n K n K a , b K_{a,b} K a , b a + b = n a + b = n a + b = n n n n s ( K n ) = n ( ⌈ ( n − 1 ) / k ⌉ − 1 ) ≥ n 3 / 2 − n − n s(K_n) = n(\lceil(n - 1)/k \rceil- 1) \ge n^{3/2} - n - \sqrt{n} s ( K n ) = n (⌈( n − 1 ) / k ⌉ − 1 ) ≥ n 3/2 − n − n
Proof. (i) The other 2 n − 2 2n-2 2 n − 2 b v − a v − 1 b_v-a_v-1 b v − a v − 1 a v a_v a v b v b_v b v v v v v v v v v v ∣ { u : a v < a u < b u < b v } ∣ |\{u : a_v < a_u < b_u < b_v\}| ∣ { u : a v < a u < b u < b v } ∣ v v v a v a_v a v O ( n log n ) O(n \log n) O ( n log n ) B B B s ( G ) s(G) s ( G ) O ( n ) O(n) O ( n ) n n n 2 n 2n 2 n K n K_n K n K a , b K_{a,b} K a , b b b b 1 2 \frac{1}{2} 2 1 s ( K n ) s(K_n) s ( K n )
Conjecture 6.20 (Ratio n 1 − ε n^{1-\varepsilon} n 1 − ε ε = 1 4 \varepsilon= \frac{1}{4} ε = 4 1 For every graph G G G n n n S S S ∣ S ∣ / i ( G ) ≤ n 3 / 4 |S|/i(G) \le n^{3/4} ∣ S ∣/ i ( G ) ≤ n 3/4
Since n ≤ n 3 / 4 \sqrt{n} \le n^{3/4} n ≤ n 3/4 n ≥ 1 n \ge1 n ≥ 1 2 n ≤ n 3 / 4 2\sqrt{n} \le n^{3/4} 2 n ≤ n 3/4 n ≥ 16 n \ge16 n ≥ 16 Theorems 6.5 and 6.8 , Corollary 6.12 and Proposition 6.11 show that Conjecture 6.20 holds on every graph with Δ ≤ n \Delta\le\sqrt{n} Δ ≤ n i ( G ) ≥ n i(G) \ge\sqrt{n} i ( G ) ≥ n α ( G ) ≤ n i ( G ) \alpha(G) \le\sqrt{n}i(G) α ( G ) ≤ n i ( G ) n ≥ 16 n \ge16 n ≥ 16 s ( G ) ≤ i ( G ) s(G) \le i(G) s ( G ) ≤ i ( G )
Theorem 6.21 (Conditional consequence of Conjecture 6.20). If Conjecture 6.20 is proved, then P = N P \mathrm{P} = \mathrm{NP} P = NP
Proof. Algorithm 1 runs in polynomial time (Theorem 5.2 ), so Conjecture 6.20 would give a polynomial-time approximation of MIDS within n 1 − ε n^{1-\varepsilon} n 1 − ε ε = 1 4 \varepsilon= \frac{1}{4} ε = 4 1 P = N P \mathrm{P} = \mathrm{NP} P = NP [2 ] (see also Corollary 8.11 ).
Corollary 6.22 (Circle graphs). If Conjecture 6.20 is proved for circle graphs only, then P = N P \mathrm{P} = \mathrm{NP} P = NP
Proof. Algorithm 1 takes the graph and needs no chord model, and it runs in polynomial time (Theorem 5.2 ). The conjecture on circle graphs would give a polynomial-time approximation of MIDS on circle graphs within n ε n^\varepsilon n ε ε = 3 4 < 1 \varepsilon= \frac{3}{4} < 1 ε = 4 3 < 1 P = N P \mathrm{P} = \mathrm{NP} P = NP [3 ] .
Hard Instances and the Unique Games Conjecture
Chlebík and Chlebíková prove their bounded-degree results with two reductions [10 ] , which we use as instance generators.
SC-IDS. For a set system S \mathcal{S} S U \mathcal{U} U S \mathcal{S} S U \mathcal{U} U S S S S S S S ′ S' S ′ S ′ ′ S'' S ′′ i = sc ( S ) + ∣ S ∣ i = \operatorname{sc}(\mathcal{S}) + |\mathcal{S}| i = sc ( S ) + ∣ S ∣ sc \operatorname{sc} sc [10 ] .
VC-IDS. For a graph H H H m H m_H m H u v uv uv Figure 1 : six new vertices a a a b b b c c c d d d x x x y y y u a ua u a a b ab ab b c bc b c c d cd c d d v dv d v b x bx b x x y xy x y y c yc y c h ( H ) h(H) h ( H ) ∣ V ( H ) ∣ + 6 m H |V(H)| + 6m_H ∣ V ( H ) ∣ + 6 m H 8 m H 8m_H 8 m H max ( Δ ( H ) , 3 ) \max(\Delta(H), 3) max ( Δ ( H ) , 3 ) [10 ] ; we prove the identity for the gadget of Figure 1 .
Figure 1. The edge gadget of the VC-IDS reduction: the edge u v uv uv H H H u u u a a a b b b c c c d d d v v v b b b x x x y y y c c c
Proposition 7.1 (VC-IDS identity). For every graph H H H m H m_H m H i ( h ( H ) ) = τ ( H ) + 2 m H i(h(H)) = \tau(H) + 2m_H i ( h ( H )) = τ ( H ) + 2 m H
Proof. Let D D D h ( H ) h(H) h ( H ) u v uv uv x x x { b , x , y } \{b,x,y\} { b , x , y } y y y { x , y , c } \{x,y,c\} { x , y , c } b b b c c c D D D x x x y y y x x x y y y D D D x ∈ D x \in D x ∈ D y ∈ D y \in D y ∈ D u , a , b u,a,b u , a , b v , d , c v,d,c v , d , c b , y ∉ D b,y \notin D b , y ∈ / D c c c { c , d } \{c,d\} { c , d } D D D c c c d d d a a a { u , a } \{u,a\} { u , a } D D D a a a u ∉ D u \notin D u ∈ / D D D D u u u v v v D D D X = D ∩ V ( H ) X = D \cap V(H) X = D ∩ V ( H ) q q q H H H X X X ∣ D ∣ ≥ ∣ X ∣ + 2 m H + q |D| \ge|X| + 2m_H + q ∣ D ∣ ≥ ∣ X ∣ + 2 m H + q q q q X X X H H H ∣ D ∣ ≥ τ ( H ) + 2 m H |D| \ge\tau(H) + 2m_H ∣ D ∣ ≥ τ ( H ) + 2 m H C C C H H H C C C { a , y } \{a,y\} { a , y } v ∈ C v \in C v ∈ C { d , x } \{d,x\} { d , x } u ∈ C u \in C u ∈ C { x , c } \{x,c\} { x , c } u , v ∈ C u,v \in C u , v ∈ C u ∉ C u \notin C u ∈ / C u u u C C C a a a d d d u u u u u u τ ( H ) + 2 m H \tau(H) + 2m_H τ ( H ) + 2 m H
Lemma 7.2 (Decoding a vertex cover). For every independent dominating set D D D h ( H ) h(H) h ( H ) C D C_D C D D ∩ V ( H ) D \cap V(H) D ∩ V ( H ) H H H D D D H H H ∣ C D ∣ ≤ ∣ D ∣ − 2 m H |C_D| \le|D| - 2m_H ∣ C D ∣ ≤ ∣ D ∣ − 2 m H O ( ∣ V ( H ) ∣ + m H ) O(|V(H)| + m_H) O ( ∣ V ( H ) ∣ + m H )
Proof. This is the inequality ∣ D ∣ ≥ ∣ X ∣ + 2 m H + q |D| \ge|X| + 2m_H + q ∣ D ∣ ≥ ∣ X ∣ + 2 m H + q Proposition 7.1 .
Theorem 7.3 (Conditional consequence for vertex cover). Assume that for every fixed ε 0 > 0 \varepsilon_0 > 0 ε 0 > 0 2 − ε 0 2 - \varepsilon_0 2 − ε 0 ε 0 > 0 \varepsilon_0 > 0 ε 0 > 0 D D D ∣ D ∣ ≤ i ( h ( H ) ) + ( 1 − ε 0 ) τ ( H ) |D| \le i(h(H)) + (1 - \varepsilon_0)\tau(H) ∣ D ∣ ≤ i ( h ( H )) + ( 1 − ε 0 ) τ ( H ) H H H [12 ] , and in particular if the theorem reported in [13 ] holds; without any assumption, such a bound would refute UGC unless P = NP.
Proof. Isolated vertices belong to no minimum vertex cover and can be removed from H H H h ( H ) h(H) h ( H ) Lemma 7.2 and Proposition 7.1 the decoded cover satisfies ∣ C D ∣ ≤ ∣ D ∣ − 2 m H ≤ τ ( H ) + ( 1 − ε 0 ) τ ( H ) = ( 2 − ε 0 ) τ ( H ) |C_D| \le|D| - 2m_H \le\tau(H) + (1 - \varepsilon_0)\tau(H) = (2 - \varepsilon_0)\tau(H) ∣ C D ∣ ≤ ∣ D ∣ − 2 m H ≤ τ ( H ) + ( 1 − ε 0 ) τ ( H ) = ( 2 − ε 0 ) τ ( H ) [12 ] derives the assumption from UGC.
Bounded degree. Austrin, Khot and Safra proved that, assuming UGC, Minimum Vertex Cover on graphs of maximum degree d d d 2 − ( 2 + o d ( 1 ) ) log log d / log d 2 - (2 + o_d(1)) \log\log d / \log d 2 − ( 2 + o d ( 1 )) log log d / log d [22 ] . Since h ( H ) h(H) h ( H ) max ( Δ ( H ) , 3 ) \max(\Delta(H),3) max ( Δ ( H ) , 3 )
Corollary 7.4 (Bounded-degree instances). Assume UGC and P ≠ \ne = δ > 0 \delta> 0 δ > 0 d 0 d_0 d 0 d ≥ d 0 d \ge d_0 d ≥ d 0 A \mathcal{A} A H H H d d d
∣ A ( h ( H ) ) ∣ > i ( h ( H ) ) + ( 1 − ( 2 + δ ) log log d log d ) τ ( H ) , |\mathcal{A}(h(H))| > i(h(H)) + \left(1 - (2+\delta)\frac{\log\log d}{\log d}\right)\tau(H), ∣ A ( h ( H )) ∣ > i ( h ( H )) + ( 1 − ( 2 + δ ) log d log log d ) τ ( H ) , and h ( H ) h(H) h ( H ) max ( d , 3 ) \max(d,3) max ( d , 3 )
Proof. Write the factor of [22 ] as 2 − ( 2 + ε d ) log log d / log d 2 - (2 + \varepsilon_d)\log\log d/\log d 2 − ( 2 + ε d ) log log d / log d ε d → 0 \varepsilon_d \to0 ε d → 0 d 0 d_0 d 0 ε d < δ \varepsilon_d < \delta ε d < δ d ≥ d 0 d \ge d_0 d ≥ d 0 H H H Lemma 7.2 and Proposition 7.1 would give a polynomial-time vertex cover algorithm with ratio at most 2 − ( 2 + δ ) log log d / log d 2 - (2+\delta)\log\log d/\log d 2 − ( 2 + δ ) log log d / log d d d d ≠ \ne =
Theorem 7.3 and Corollary 7.4 are conditional implications, not claims about Algorithm 1. The theorem of [13 ] had not been peer reviewed at the time of writing; we cite it as reported and have not checked the formalization. § 9.4 reports the measured values of ∣ D ∣ − i ( h ( H ) ) |D| - i(h(H)) ∣ D ∣ − i ( h ( H )) ∣ C D ∣ / τ ( H ) |C_D|/\tau(H) ∣ C D ∣/ τ ( H )
Application to Boolean Satisfiability
The SAT solver satypy 0.0.4 [23 ] decides a formula in conjunctive normal form in three stages: unit propagation and pure literal elimination, which answers UNSATISFIABLE on a conflict and otherwise commits literals and leaves a residual formula; an exact implication-graph solver when every residual clause has at most two literals; and otherwise a reduction of the residual formula to MIDS, solved by Siriaisa 0.0.8. Every SATISFIABLE answer is returned with an assignment, formed by the committed literals and the decoded literals, that is checked against every clause of the input formula. This section describes the third stage. Let φ \varphi φ p p p x 1 , … , x p x_1,\ldots,x_p x 1 , … , x p q q q C 1 , … , C q C_1,\ldots,C_q C 1 , … , C q
Definition 8.1 (SAT-IDS graph). For an integer β ≥ 1 \beta\ge1 β ≥ 1 G β ( φ ) G_\beta(\varphi) G β ( φ ) 2 p 2p 2 p x r , ¬ x r x_r, \neg x_r x r , ¬ x r β \beta β c j , 1 , … , c j , β c_{j,1},\ldots,c_{j,\beta} c j , 1 , … , c j , β C j C_j C j x r ¬ x r x_r\neg x_r x r ¬ x r c j , t ℓ c_{j,t}\ell c j , t ℓ C j C_j C j t ≤ β t \le\beta t ≤ β ℓ ∈ C j \ell\in C_j ℓ ∈ C j n = 2 p + q β n=2p+q\beta n = 2 p + q β p + β ∑ j ∣ C j ∣ p+\beta\sum_j |C_j| p + β ∑ j ∣ C j ∣
Lemma 8.2 (Structure of the SAT-IDS graph). Let β ≥ p \beta\ge p β ≥ p D D D G = G β ( φ ) G=G_\beta(\varphi) G = G β ( φ )
(i) If D D D D D D x r x_r x r ¬ x r \neg x_r ¬ x r r r r ∣ D ∣ = p |D|=p ∣ D ∣ = p D D D φ \varphi φ
(ii) If D D D c j , t c_{j,t} c j , t D D D c j , 1 , … , c j , β c_{j,1},\ldots,c_{j,\beta} c j , 1 , … , c j , β
(iii) If D D D ∣ D ∣ ≥ β + p |D| \ge\beta+p ∣ D ∣ ≥ β + p
(iv) i ( G ) = p i(G)=p i ( G ) = p φ \varphi φ i ( G ) ≥ β + p i(G)\ge\beta+p i ( G ) ≥ β + p G G G p p p β + p \beta+p β + p
(v) If an assignment of φ \varphi φ i ( G ) ≤ β + p i(G)\le\beta+p i ( G ) ≤ β + p i ( G ) = β + p i(G)=\beta+p i ( G ) = β + p φ \varphi φ
Proof. (i) The neighbours of x r x_r x r ¬ x r \neg x_r ¬ x r D D D D D D D D D D D D p p p c j , t ∉ D c_{j,t}\notin D c j , t ∈ / D D D D C j C_j C j c j , t c_{j,t} c j , t C j C_j C j D D D c j , s c_{j,s} c j , s D D D D D D ∣ D ∣ ≥ 2 β ≥ β + p |D|\ge2\beta\ge\beta+p ∣ D ∣ ≥ 2 β ≥ β + p D D D β \beta β C j C_j C j x r x_r x r C j C_j C j x r x_r x r ¬ x r \neg x_r ¬ x r y y y C j C_j C j y y y C j C_j C j D D D x r x_r x r ¬ x r \neg x_r ¬ x r D D D y y y D D D ∣ D ∣ ≥ β + p |D|\ge\beta+p ∣ D ∣ ≥ β + p p p p p p p β + p \beta+p β + p φ \varphi φ σ \sigma σ C j C_j C j D D D p p p σ \sigma σ c j , 1 , … , c j , β c_{j,1},\ldots,c_{j,\beta} c j , 1 , … , c j , β c j , t c_{j,t} c j , t C j C_j C j D D D ∣ D ∣ = β + p |D|=\beta+p ∣ D ∣ = β + p
Number of copies
Lemma 8.3 (Number of copies). For integers p , q ≥ 1 p,q\ge1 p , q ≥ 1 Λ = 4 q 2 p 4 + 8 p 3 − 4 q p 3 \Lambda=4q^2p^4+8p^3-4qp^3 Λ = 4 q 2 p 4 + 8 p 3 − 4 q p 3 β ∗ = 2 q p 2 + ⌊ Λ ⌋ + 1 − p \beta^*=2qp^2+\lfloor\sqrt{\Lambda}\rfloor+1-p β ∗ = 2 q p 2 + ⌊ Λ ⌋ + 1 − p β ∗ \beta^* β ∗ β \beta β β + p > 2 p 2 p + q β \beta+p>2p\sqrt{2p+q\beta} β + p > 2 p 2 p + q β p ≤ β ∗ ≤ 4 q p 2 + 1 p\le\beta^*\le4qp^2+1 p ≤ β ∗ ≤ 4 q p 2 + 1
Proof. Write C = β + p C=\beta+p C = β + p 2 p + q β = q C + 2 p − q p > 0 2p+q\beta=qC+2p-qp>0 2 p + q β = q C + 2 p − q p > 0 f ( C ) = C 2 − 4 q p 2 C − ( 8 p 3 − 4 q p 3 ) > 0 f(C)=C^2-4qp^2C-(8p^3-4qp^3)>0 f ( C ) = C 2 − 4 q p 2 C − ( 8 p 3 − 4 q p 3 ) > 0 f f f 4 Λ 4\Lambda 4Λ Λ = 4 p 3 ( q 2 p + 2 − q ) > 0 \Lambda=4p^3(q^2p+2-q)>0 Λ = 4 p 3 ( q 2 p + 2 − q ) > 0 q 2 p ≥ q q^2p\ge q q 2 p ≥ q f f f r 1 , 2 = 2 q p 2 ∓ Λ r_{1,2}=2qp^2\mp\sqrt{\Lambda} r 1 , 2 = 2 q p 2 ∓ Λ f ( p ) = p 2 − 8 p 3 < 0 f(p)=p^2-8p^3<0 f ( p ) = p 2 − 8 p 3 < 0 r 1 < p < r 2 r_1<p<r_2 r 1 < p < r 2 C ≥ p + 1 C\ge p+1 C ≥ p + 1 f ( C ) > 0 f(C)>0 f ( C ) > 0 C > r 2 C>r_2 C > r 2 2 q p 2 2qp^2 2 q p 2 r 2 r_2 r 2 2 q p 2 + ⌊ Λ ⌋ + 1 2qp^2+\lfloor\sqrt{\Lambda}\rfloor+1 2 q p 2 + ⌊ Λ ⌋ + 1 β ∗ \beta^* β ∗ Λ ≥ 0 \Lambda\ge0 Λ ≥ 0 β ∗ ≥ p + 1 − p = p \beta^*\ge p+1-p=p β ∗ ≥ p + 1 − p = p q ≥ 2 q\ge2 q ≥ 2 Λ ≤ 4 q p 4 \Lambda\le4qp^4 Λ ≤ 4 q p 4 β ∗ ≤ 4 q p 2 + 1 − p \beta^*\le4qp^2+1-p β ∗ ≤ 4 q p 2 + 1 − p q = 1 q=1 q = 1 Λ = 4 p 4 + 4 p 3 < ( 2 p 2 + p ) 2 \Lambda=4p^4+4p^3<(2p^2+p)^2 Λ = 4 p 4 + 4 p 3 < ( 2 p 2 + p ) 2 β ∗ ≤ 4 p 2 + 1 \beta^*\le4p^2+1 β ∗ ≤ 4 p 2 + 1
Lemma 8.4 (Copies for the ratio 2 p 2p 2 p p ≥ 1 p\ge1 p ≥ 1 β ^ = 2 p 2 − p + 1 \hat{\beta}=2p^2-p+1 β ^ = 2 p 2 − p + 1 β ^ \hat{\beta} β ^ β \beta β β + p > 2 p 2 \beta+p>2p^2 β + p > 2 p 2 β ^ ≥ p + 1 \hat{\beta}\ge p+1 β ^ ≥ p + 1 G β ^ ( φ ) G_{\hat{\beta}}(\varphi) G β ^ ( φ ) n = 2 p + q β ^ ≤ 2 p + 2 q p 2 n=2p+q\hat{\beta}\le2p+2qp^2 n = 2 p + q β ^ ≤ 2 p + 2 q p 2 p + β ^ ∑ j ∣ C j ∣ p+\hat{\beta}\sum_j|C_j| p + β ^ ∑ j ∣ C j ∣
Proof. For an integer β \beta β β + p > 2 p 2 \beta+p>2p^2 β + p > 2 p 2 β ≥ 2 p 2 − p + 1 \beta\ge2p^2-p+1 β ≥ 2 p 2 − p + 1 β ^ − ( p + 1 ) = 2 p ( p − 1 ) ≥ 0 \hat{\beta}-(p+1)=2p(p-1)\ge0 β ^ − ( p + 1 ) = 2 p ( p − 1 ) ≥ 0 Definition 8.1 .
For a literal ℓ \ell ℓ φ \varphi φ o ℓ o_\ell o ℓ ℓ \ell ℓ L = ∑ j ∣ C j ∣ = ∑ ℓ o ℓ L=\sum_j |C_j|=\sum_\ell o_\ell L = ∑ j ∣ C j ∣ = ∑ ℓ o ℓ φ \varphi φ λ \lambda λ o ℓ ≥ 1 o_\ell\ge1 o ℓ ≥ 1 λ ≤ 2 p \lambda\le2p λ ≤ 2 p
Proposition 8.5 (Splitting excess of the SAT-IDS graph). Let β = β ∗ \beta=\beta^* β = β ∗ G = G β ( φ ) G=G_\beta(\varphi) G = G β ( φ ) n n n k = ⌊ n ⌋ k=\lfloor\sqrt{n}\rfloor k = ⌊ n ⌋
(i) k ≥ q p k\ge qp k ≥ q p k k k ℓ \ell ℓ o ℓ ≥ 1 o_\ell\ge1 o ℓ ≥ 1 ℓ \ell ℓ 1 + β o ℓ 1+\beta o_\ell 1 + β o ℓ s ( G ) = ∑ ℓ : o ℓ ≥ 1 ( ⌈ ( 1 + β o ℓ ) / k ⌉ − 1 ) s(G)=\sum_{\ell:o_\ell\ge1}(\lceil(1+\beta o_\ell)/k\rceil-1) s ( G ) = ∑ ℓ : o ℓ ≥ 1 (⌈( 1 + β o ℓ ) / k ⌉ − 1 )
(ii) 2 p L − p L / k − λ < s ( G ) < 2 p L + ( ( p + 1 ) L + λ ) / k 2pL-pL/k-\lambda<s(G)<2pL+((p+1)L+\lambda)/k 2 p L − p L / k − λ < s ( G ) < 2 p L + (( p + 1 ) L + λ ) / k
1 − 1 2 k − 1 L < s ( G ) 2 p L < 1 + 1 k ( 1 + 1 L ) . 1-\frac{1}{2k}-\frac{1}{L}<\frac{s(G)}{2pL}<1+\frac{1}{k}\left(1+\frac{1}{L}\right). 1 − 2 k 1 − L 1 < 2 p L s ( G ) < 1 + k 1 ( 1 + L 1 ) . (iii) If every variable of φ \varphi φ φ \varphi φ λ = 2 p \lambda=2p λ = 2 p L ≥ 2 p L\ge2p L ≥ 2 p s ( G ) > 4 p 2 − 2 p 2 / k − 2 p s(G)>4p^2-2p^2/k-2p s ( G ) > 4 p 2 − 2 p 2 / k − 2 p
Proof. (i) By Lemma 8.3 , n > q β ≥ q ( 2 q p 2 + 1 − p ) = q 2 p 2 + q ( q p 2 + 1 − p ) > q 2 p 2 n>q\beta\ge q(2qp^2+1-p)=q^2p^2+q(qp^2+1-p)>q^2p^2 n > q β ≥ q ( 2 q p 2 + 1 − p ) = q 2 p 2 + q ( q p 2 + 1 − p ) > q 2 p 2 k ≥ q p ≥ p k\ge qp\ge p k ≥ q p ≥ p c j , t c_{j,t} c j , t ∣ C j ∣ ≤ p ≤ k |C_j|\le p\le k ∣ C j ∣ ≤ p ≤ k ℓ \ell ℓ β \beta β o ℓ o_\ell o ℓ 1 + β o ℓ 1+\beta o_\ell 1 + β o ℓ o ℓ = 0 o_\ell=0 o ℓ = 0 1 ≤ k 1\le k 1 ≤ k β + p > 2 p n ≥ 2 p k \beta+p>2p\sqrt n\ge2pk β + p > 2 p n ≥ 2 p k Lemma 8.3 ), β > 2 p k − p ≥ k \beta>2pk-p\ge k β > 2 p k − p ≥ k o ℓ ≥ 1 o_\ell\ge1 o ℓ ≥ 1 1 + β o ℓ 1+\beta o_\ell 1 + β o ℓ k k k s ( G ) s(G) s ( G ) β ∗ ≥ 2 q p 2 + 1 − p ≥ 2 \beta^*\ge2qp^2+1-p\ge2 β ∗ ≥ 2 q p 2 + 1 − p ≥ 2 β − 1 ≥ 1 \beta-1\ge1 β − 1 ≥ 1 Lemma 8.3 , so β − 1 + p ≤ 2 p 2 p + q ( β − 1 ) < 2 p n < 2 p ( k + 1 ) \beta-1+p\le2p\sqrt{2p+q(\beta-1)}<2p\sqrt n<2p(k+1) β − 1 + p ≤ 2 p 2 p + q ( β − 1 ) < 2 p n < 2 p ( k + 1 ) β < 2 p k + p + 1 \beta<2pk+p+1 β < 2 p k + p + 1 β > 2 p k − p \beta>2pk-p β > 2 p k − p 2 p − p / k < β / k < 2 p + ( p + 1 ) / k 2p-p/k<\beta/k<2p+(p+1)/k 2 p − p / k < β / k < 2 p + ( p + 1 ) / k x x x x − 1 ≤ ⌈ x ⌉ − 1 < x x-1\le\lceil x\rceil-1<x x − 1 ≤ ⌈ x ⌉ − 1 < x
β L + λ k − λ ≤ s ( G ) < β L + λ k . \frac{\beta L+\lambda}{k}-\lambda\le s(G)<\frac{\beta L+\lambda}{k}. k β L + λ − λ ≤ s ( G ) < k β L + λ . The lower bound is larger than ( 2 p − p / k ) L − λ (2p-p/k)L-\lambda ( 2 p − p / k ) L − λ ( 2 p + ( p + 1 ) / k ) L + λ / k (2p+(p+1)/k)L+\lambda/k ( 2 p + ( p + 1 ) / k ) L + λ / k 2 p L 2pL 2 p L λ ≤ 2 p \lambda\le2p λ ≤ 2 p ( p + 1 ) / ( 2 p ) ≤ 1 (p+1)/(2p)\le1 ( p + 1 ) / ( 2 p ) ≤ 1 o ℓ ≥ 1 o_\ell\ge1 o ℓ ≥ 1 λ = 2 p \lambda=2p λ = 2 p L = ∑ ℓ o ℓ ≥ 2 p L=\sum_\ell o_\ell\ge2p L = ∑ ℓ o ℓ ≥ 2 p 2 p − p / k > 0 2p-p/k>0 2 p − p / k > 0 s ( G ) > ( 2 p − p / k ) ⋅ 2 p − 2 p s(G)>(2p-p/k)\cdot2p-2p s ( G ) > ( 2 p − p / k ) ⋅ 2 p − 2 p
By Proposition 8.5 (i), k ≥ q p k\ge qp k ≥ q p q p qp q p L L L s ( G ) s(G) s ( G ) 2 p L 2pL 2 p L
Let μ ( φ ) \mu(\varphi) μ ( φ ) φ \varphi φ μ ( φ ) = 0 \mu(\varphi)=0 μ ( φ ) = 0 φ \varphi φ F F F U ( F ) = ⋃ j ∈ F C j U(F)=\bigcup_{j\in F}C_j U ( F ) = ⋃ j ∈ F C j c ( F ) c(F) c ( F ) x r x_r x r x r ∈ U ( F ) x_r\in U(F) x r ∈ U ( F ) ¬ x r ∈ U ( F ) \neg x_r\in U(F) ¬ x r ∈ U ( F ) T T T F F F x r x_r x r T T T ℓ \ell ℓ ℓ \ell ℓ x r , ¬ x r x_r,\neg x_r x r , ¬ x r U ( F ) U(F) U ( F ) x r , ¬ x r x_r,\neg x_r x r , ¬ x r U ( F ) U(F) U ( F ) U ( F ) U(F) U ( F ) T T T C j C_j C j j ∉ F j\notin F j ∈ / F F F F T T T
Theorem 8.6 (Independent domination and maximum satisfiability). Let β ≥ 1 \beta\ge1 β ≥ 1 G = G β ( φ ) G=G_\beta(\varphi) G = G β ( φ )
(i) The independent dominating sets of G G G T ∪ { c j , t : j ∈ F , t ≤ β } T\cup\{c_{j,t}:j\in F,\ t\le\beta\} T ∪ { c j , t : j ∈ F , t ≤ β } F F F T T T F F F β ∣ F ∣ + p − c ( F ) \beta|F|+p-c(F) β ∣ F ∣ + p − c ( F ) i ( G ) = min F a d m i s s i b l e ( β ∣ F ∣ + p − c ( F ) ) i(G)=\min_{F\ \mathrm{admissible}}(\beta|F|+p-c(F)) i ( G ) = min F admissible ( β ∣ F ∣ + p − c ( F ))
(ii) β μ ( φ ) ≤ i ( G ) ≤ β μ ( φ ) + p \beta\mu(\varphi)\le i(G)\le\beta\mu(\varphi)+p β μ ( φ ) ≤ i ( G ) ≤ β μ ( φ ) + p β > p \beta>p β > p μ ( φ ) = ⌊ i ( G ) / β ⌋ \mu(\varphi)=\lfloor i(G)/\beta\rfloor μ ( φ ) = ⌊ i ( G ) / β ⌋
(iii) If β > p \beta>p β > p D D D G G G ⌊ ∣ D ∣ / β ⌋ \lfloor|D|/\beta\rfloor ⌊ ∣ D ∣/ β ⌋ D D D ⌊ ∣ D ∣ / β ⌋ \lfloor|D|/\beta\rfloor ⌊ ∣ D ∣/ β ⌋
(iv) If β > p \beta>p β > p ∣ D ∣ ≤ ρ i ( G ) |D|\le\rho\,i(G) ∣ D ∣ ≤ ρ i ( G ) ρ ≥ 1 \rho\ge1 ρ ≥ 1 ρ ( μ ( φ ) + p / β ) \rho\left(\mu(\varphi)+p/\beta\right) ρ ( μ ( φ ) + p / β )
For β = β ^ \beta=\hat{\beta} β = β ^ β = β ∗ \beta=\beta^* β = β ∗ β ^ ≥ p + 1 \hat{\beta}\ge p+1 β ^ ≥ p + 1 β ∗ ≥ 2 q p 2 + 1 − p > p \beta^*\ge2qp^2+1-p>p β ∗ ≥ 2 q p 2 + 1 − p > p Lemmas 8.4 and 8.3 ).
Proof. (i) Let D D D F F F D D D T T T D D D Lemma 8.2 (ii), D D D c j , 1 , … , c j , β c_{j,1},\ldots,c_{j,\beta} c j , 1 , … , c j , β j ∈ F j \in F j ∈ F D D D T T T U ( F ) U(F) U ( F ) D D D x r , ¬ x r x_r,\neg x_r x r , ¬ x r ℓ ∉ T \ell\notin T ℓ ∈ / T D D D T T T ℓ ∈ U ( F ) \ell\in U(F) ℓ ∈ U ( F ) x r , ¬ x r x_r,\neg x_r x r , ¬ x r U ( F ) U(F) U ( F ) T T T ℓ \ell ℓ U ( F ) U(F) U ( F ) ℓ ∉ T \ell\notin T ℓ ∈ / T ℓ \ell ℓ U ( F ) U(F) U ( F ) T T T U ( F ) U(F) U ( F ) T T T c j , t c_{j,t} c j , t j ∉ F j \notin F j ∈ / F C j C_j C j T T T T T T F F F T T T F F F D = T ∪ { c j , t : j ∈ F , t ≤ β } D=T\cup\{c_{j,t}:j\in F,\ t\leq\beta\} D = T ∪ { c j , t : j ∈ F , t ≤ β } T T T U ( F ) U(F) U ( F ) T T T F F F c j , t c_{j,t} c j , t j ∉ F j\notin F j ∈ / F C j C_j C j T T T T T T p − c ( F ) p-c(F) p − c ( F ) U ( F ) U(F) U ( F ) ∣ D ∣ = β ∣ F ∣ + p − c ( F ) |D|=\beta|F|+p-c(F) ∣ D ∣ = β ∣ F ∣ + p − c ( F ) σ \sigma σ μ ( φ ) \mu(\varphi) μ ( φ ) F σ F_\sigma F σ U ( F σ ) U(F_\sigma) U ( F σ ) σ \sigma σ U ( F σ ) U(F_\sigma) U ( F σ ) c ( F σ ) = 0 c(F_\sigma)=0 c ( F σ ) = 0 σ \sigma σ F σ F_\sigma F σ i ( G ) ≤ β μ ( φ ) + p i(G)\leq\beta\mu(\varphi)+p i ( G ) ≤ β μ ( φ ) + p T T T F F F T T T C j C_j C j j ∉ F j\notin F j ∈ / F μ ( φ ) ≤ ∣ F ∣ \mu(\varphi)\leq|F| μ ( φ ) ≤ ∣ F ∣ β ∣ F ∣ + p − c ( F ) ≥ β ∣ F ∣ ≥ β μ ( φ ) \beta|F|+p-c(F)\geq\beta|F|\geq\beta\mu(\varphi) β ∣ F ∣ + p − c ( F ) ≥ β ∣ F ∣ ≥ β μ ( φ ) c ( F ) ≤ p c(F)\leq p c ( F ) ≤ p β > p \beta>p β > p β μ ( φ ) ≤ i ( G ) < β ( μ ( φ ) + 1 ) \beta\mu(\varphi)\leq i(G)<\beta(\mu(\varphi)+1) β μ ( φ ) ≤ i ( G ) < β ( μ ( φ ) + 1 ) ∣ D ∣ = β ∣ F ∣ + p − c ( F ) |D|=\beta|F|+p-c(F) ∣ D ∣ = β ∣ F ∣ + p − c ( F ) ∣ F ∣ = ⌊ ∣ D ∣ / β ⌋ |F|=\lfloor|D|/\beta\rfloor ∣ F ∣ = ⌊ ∣ D ∣/ β ⌋ F F F ∣ D ∣ / β ≤ ρ i ( G ) / β ≤ ρ ( μ ( φ ) + p / β ) |D|/\beta\leq\rho\,i(G)/\beta\leq\rho\left(\mu(\varphi)+p/\beta\right) ∣ D ∣/ β ≤ ρ i ( G ) / β ≤ ρ ( μ ( φ ) + p / β )
Lemma 8.2 (iv) and (v) are the cases μ ( φ ) = 0 \mu(\varphi)=0 μ ( φ ) = 0 μ ( φ ) = 1 \mu(\varphi)=1 μ ( φ ) = 1 Theorem 8.6 .
With β = β ^ \beta=\hat{\beta} β = β ^ G = G β ( φ ) G=G_{\beta}(\varphi) G = G β ( φ ) S S S Proposition 8.13 ), it answers SATISFIABLE, with the literals of S S S ∣ S ∣ < β |S|<\beta ∣ S ∣ < β ∣ S ∣ > 2 p 2 |S|>2p^2 ∣ S ∣ > 2 p 2 ∣ S ∣ / p > 2 p |S|/p>2p ∣ S ∣/ p > 2 p β ∗ \beta^* β ∗ Lemma 8.3 , with the threshold ∣ S ∣ > 2 p |S|>2\sqrt{p} ∣ S ∣ > 2 p 2 n 2\sqrt{n} 2 n
Theorem 8.7 (Decisions of the MIDS stage). Let β = β ^ \beta=\hat{\beta} β = β ^ G = G β ( φ ) G=G_{\beta}(\varphi) G = G β ( φ ) n n n S S S G G G
(i) If ∣ S ∣ < β |S|<\beta ∣ S ∣ < β S S S φ \varphi φ
(ii) If ∣ S ∣ ≥ β |S|\geq\beta ∣ S ∣ ≥ β ∣ S ∣ ≥ β + p > 2 p 2 |S|\geq\beta+p>2p^2 ∣ S ∣ ≥ β + p > 2 p 2
(iii) If φ \varphi φ
(iv) If φ \varphi φ S S S ∣ S ∣ / i ( G ) ≥ ( β + p ) / p > 2 p |S|/i(G)\geq(\beta+p)/p>2p ∣ S ∣/ i ( G ) ≥ ( β + p ) / p > 2 p
(v) If ∣ S ∣ / i ( G ) ≤ 2 p |S|/i(G)\leq2p ∣ S ∣/ i ( G ) ≤ 2 p
Proof. S S S G G G Theorem 4.3 ), and β ≥ p + 1 \beta\geq p+1 β ≥ p + 1 Lemma 8.4 ). (i) ∣ S ∣ < β < β + p |S|<\beta<\beta+p ∣ S ∣ < β < β + p S S S Lemma 8.2 (iii), and Lemma 8.2 (i) gives the assignment. It consists of one literal of every variable of φ \varphi φ φ \varphi φ ∣ S ∣ ≥ β > p |S|\geq\beta>p ∣ S ∣ ≥ β > p ∣ S ∣ ≥ β + p |S|\geq\beta+p ∣ S ∣ ≥ β + p Lemma 8.2 (iv), and β + p > 2 p 2 \beta+p>2p^2 β + p > 2 p 2 Lemma 8.4 . (iii) ∣ S ∣ ≥ i ( G ) ≥ β + p |S|\geq i(G)\geq\beta+p ∣ S ∣ ≥ i ( G ) ≥ β + p Lemma 8.2 (iv), and (ii) applies. (iv) i ( G ) = p i(G)=p i ( G ) = p Lemma 8.2 (iv); by (i) and (ii) the answer is UNSATISFIABLE if and only if ∣ S ∣ ≥ β |S|\geq\beta ∣ S ∣ ≥ β Lemma 8.2 (i) and (iii), if and only if S S S ∣ S ∣ ≥ β + p |S|\geq\beta+p ∣ S ∣ ≥ β + p φ \varphi φ ∣ S ∣ ≤ 2 p 2 < β + p |S|\leq2p^2<\beta+p ∣ S ∣ ≤ 2 p 2 < β + p S S S Lemma 8.2 (iii), and the answer is SATISFIABLE by (iv) and (i); if φ \varphi φ
Independently of any conjecture, Theorem 8.7 shows that satypy answers UNSATISFIABLE on every unsatisfiable formula, that every SATISFIABLE answer carries a satisfying assignment, and that a wrong answer can only be UNSATISFIABLE on a satisfiable formula on which Algorithm 1 has ratio larger than 2 p = 2 i ( G ) 2p=2i(G) 2 p = 2 i ( G )
The proved bound of the degree-splitting strategy. Theorem 6.8 cannot replace the ratio assumption of Theorem 8.7 (v), for any number of copies.
Proposition 8.8 (No separation by the splitting bound). For every β ≥ 1 \beta\ge1 β ≥ 1 and every satisfiable φ \varphi φ the graph G = G β ( φ ) G = G_{\beta}(\varphi) G = G β ( φ ) satisfies ⌊ n ⌋ ( i ( G ) + s ( G ) ) ≥ p + q β ≥ β + p \lfloor\sqrt{n}\rfloor(i(G)+s(G)) \ge p+q\beta\ge\beta+p ⌊ n ⌋ ( i ( G ) + s ( G )) ≥ p + q β ≥ β + p Hence the bound of Theorem 6.8 on a satisfiable formula is never smaller than the size β + p \beta+p β + p that Lemma 8.2 (iii) guarantees for every independent dominating set with a clause vertex, and it does not imply that the output contains no clause vertex; in particular this holds for β = β ^ \beta=\hat{\beta} β = β ^ for β = β ∗ \beta=\beta^* β = β ∗ and for β = β t \beta=\beta_t β = β t of Theorem 8.9 .
Proof. i ( G ) = p i(G)=p i ( G ) = p Lemma 8.2 (iv), and n = 2 p + q β n=2p+q\beta n = 2 p + q β ⌊ n ⌋ ( p + s ( G ) ) ≥ n − p = p + q β ≥ p + β \lfloor\sqrt{n}\rfloor(p+s(G)) \ge n-p=p+q\beta\ge p+\beta ⌊ n ⌋ ( p + s ( G )) ≥ n − p = p + q β ≥ p + β
SAT-IDS graphs for the ratio n 1 − 1 / t n^{1-1/t} n 1 − 1/ t n 1 − ε n^{1-\varepsilon} n 1 − ε ε = 1 / t \varepsilon=1/t ε = 1/ t
Theorem 8.9 (Gap of the SAT-IDS graph for the ratio n 1 − 1 / t n^{1-1/t} n 1 − 1/ t For an integer t ≥ 2 t \ge2 t ≥ 2 let β t = p t ( 3 q ) t − 1 + 1 \beta_t=p^t(3q)^{t-1}+1 β t = p t ( 3 q ) t − 1 + 1 and G = G β t ( φ ) G=G_{\beta_t}(\varphi) G = G β t ( φ ) with n = 2 p + q β t = 3 t − 1 p t q t + q + 2 p n=2p+q\beta_t=3^{t-1}p^tq^t+q+2p n = 2 p + q β t = 3 t − 1 p t q t + q + 2 p vertices.
(i) β t + p > p n 1 − 1 / t \beta_t+p>pn^{1-1/t} β t + p > p n 1 − 1/ t i ( G ) = p i(G)=p i ( G ) = p φ \varphi φ i ( G ) ≥ β t + p > p n 1 − 1 / t i(G)\ge\beta_t+p>pn^{1-1/t} i ( G ) ≥ β t + p > p n 1 − 1/ t
(ii) For every independent dominating set D D D of G G G with ∣ D ∣ ≤ n 1 − 1 / t i ( G ) |D|\le n^{1-1/t}i(G) ∣ D ∣ ≤ n 1 − 1/ t i ( G ) φ \varphi φ is satisfiable if and only if ∣ D ∣ < β t |D|<\beta_t ∣ D ∣ < β t and then the literal vertices of D D D form a satisfying assignment.
(iii) G G G p + β t ∑ j ∣ C j ∣ p+\beta_t\sum_j|C_j| p + β t ∑ j ∣ C j ∣ p p p q q q t t t
Proof. (i) β t > p \beta_t>p β t > p 2 p + q β t < 3 q β t 2p+q\beta_t<3q\beta_t 2 p + q β t < 3 q β t β t > p t ( 3 q ) t − 1 \beta_t>p^t(3q)^{t-1} β t > p t ( 3 q ) t − 1 β t 1 / t > p ( 3 q ) ( t − 1 ) / t \beta_t^{1/t}>p(3q)^{(t-1)/t} β t 1/ t > p ( 3 q ) ( t − 1 ) / t β t = β t 1 / t β t ( t − 1 ) / t > p ( 3 q β t ) 1 − 1 / t > p n 1 − 1 / t \beta_t=\beta_t^{1/t}\beta_t^{(t-1)/t}>p(3q\beta_t)^{1-1/t}>pn^{1-1/t} β t = β t 1/ t β t ( t − 1 ) / t > p ( 3 q β t ) 1 − 1/ t > p n 1 − 1/ t β t + p > p n 1 − 1 / t \beta_t+p>pn^{1-1/t} β t + p > p n 1 − 1/ t Lemma 8.2 (iv) applies because β t ≥ p \beta_t\ge p β t ≥ p φ \varphi φ ∣ D ∣ ≤ n 1 − 1 / t p < β t + p |D|\le n^{1-1/t}p<\beta_t+p ∣ D ∣ ≤ n 1 − 1/ t p < β t + p D D D Lemma 8.2 (iii), and Lemma 8.2 (i) gives ∣ D ∣ = p < β t |D|=p<\beta_t ∣ D ∣ = p < β t φ \varphi φ ∣ D ∣ ≥ i ( G ) ≥ β t + p |D|\ge i(G)\ge\beta_t+p ∣ D ∣ ≥ i ( G ) ≥ β t + p Definition 8.1 ; n n n p p p q q q 2 t 2t 2 t 2 t + 1 2t+1 2 t + 1
Corollary 8.10 (Two values of the ratio). Let φ \varphi φ be satisfiable, β ≥ p \beta\ge p β ≥ p G = G β ( φ ) G=G_{\beta}(\varphi) G = G β ( φ ) with n n n vertices, and D D D an independent dominating set of G G G Then either ∣ D ∣ / i ( G ) = 1 |D|/i(G)=1 ∣ D ∣/ i ( G ) = 1 and the literal vertices of D D D form a satisfying assignment, or D D D contains a clause vertex and ∣ D ∣ / i ( G ) ≥ ( β + p ) / p |D|/i(G)\ge(\beta+p)/p ∣ D ∣/ i ( G ) ≥ ( β + p ) / p For β = β ^ \beta=\hat{\beta} β = β ^ ( β + p ) / p > 2 p (\beta+p)/p>2p ( β + p ) / p > 2 p for β = β ∗ \beta=\beta^* β = β ∗ ( β + p ) / p > 2 n (\beta+p)/p>2\sqrt{n} ( β + p ) / p > 2 n for β = β t \beta=\beta_t β = β t with t ≥ 2 t\ge2 t ≥ 2 ( β + p ) / p > n 1 − 1 / t (\beta+p)/p>n^{1-1/t} ( β + p ) / p > n 1 − 1/ t in particular ( β 4 + p ) / p > n 3 / 4 (\beta_4+p)/p>n^{3/4} ( β 4 + p ) / p > n 3/4 Hence, for β = β ^ \beta=\hat{\beta} β = β ^ and every ρ ≤ 2 p \rho\le2p ρ ≤ 2 p for β = β ∗ \beta=\beta^* β = β ∗ and every ρ ≤ 2 n \rho\le2\sqrt{n} ρ ≤ 2 n and for β = β t \beta=\beta_t β = β t and every ρ ≤ n 1 − 1 / t \rho\le n^{1-1/t} ρ ≤ n 1 − 1/ t ∣ D ∣ / i ( G ) ≤ ρ |D|/i(G)\le\rho ∣ D ∣/ i ( G ) ≤ ρ holds if and only if D D D is a minimum independent dominating set of G G G
Proof. i ( G ) = p i(G)=p i ( G ) = p Lemma 8.2 (iv). If D D D ∣ D ∣ = p |D|=p ∣ D ∣ = p Lemma 8.2 (i); otherwise ∣ D ∣ ≥ β + p |D|\ge\beta+p ∣ D ∣ ≥ β + p Lemma 8.2 (iii). The inequalities for β ^ \hat{\beta} β ^ β ∗ \beta^* β ∗ β t \beta_t β t Lemmas 8.4 and 8.3 and Theorem 8.9 (i), divided by p p p ∣ D ∣ / i ( G ) > ρ |D|/i(G)>\rho ∣ D ∣/ i ( G ) > ρ ∣ D ∣ = i ( G ) |D|=i(G) ∣ D ∣ = i ( G )
Corollary 8.11 (Inapproximability through the SAT-IDS graph). For every ε > 0 \varepsilon>0 ε > 0 unless P = N P \mathrm{P}=\mathrm{NP} P = NP no polynomial-time algorithm returns, on every graph with n n n vertices, an independent dominating set of size at most n 1 − ε i ( G ) n^{1-\varepsilon}i(G) n 1 − ε i ( G )
Proof. Let t ≥ max ( 2 , 1 / ε ) t\ge\max(2,1/\varepsilon) t ≥ max ( 2 , 1/ ε ) n 1 − ε ≤ n 1 − 1 / t n^{1-\varepsilon}\le n^{1-1/t} n 1 − ε ≤ n 1 − 1/ t φ \varphi φ G β t ( φ ) G_{\beta_t}(\varphi) G β t ( φ ) Theorem 8.9 (iii), and by Theorem 8.9 (ii) the size of the returned set decides φ \varphi φ
Corollary 8.11 is the theorem of Halldórsson [2 ] ; Theorem 8.9 gives a self-contained proof of it through the SAT-IDS graph.
Corollary 8.12 (Conditional consequence for SAT). If Conjecture 6.20 is proved, then the MIDS stage of satypy with β = β 4 = 27 p 4 q 3 + 1 \beta=\beta_4=27p^4q^3+1 β = β 4 = 27 p 4 q 3 + 1 in place of β ^ \hat{\beta} β ^ answering SATISFIABLE if and only if ∣ S ∣ < β 4 |S|<\beta_4 ∣ S ∣ < β 4 decides every formula in conjunctive normal form correctly in polynomial time.
Proof. Unit propagation, pure literal elimination and the implication-graph solver are exact and run in polynomial time. G β 4 ( φ ) G_{\beta4}(\varphi) G β 4 ( φ ) n = 27 p 4 q 4 + q + 2 p n = 27p^{4}q^{4} + q + 2p n = 27 p 4 q 4 + q + 2 p Theorem 8.9 (iii)), and Algorithm 1 runs on it in polynomial time (Theorem 5.2 ). Conjecture 6.20 gives ∣ S ∣ ≤ n 3 / 4 i ( G ) |S| \le n^{3/4}i(G) ∣ S ∣ ≤ n 3/4 i ( G ) Theorem 8.9 (ii) with t = 4 t = 4 t = 4
Corollary 8.12 is a second route to the conclusion P = NP of Theorem 6.21 .
Branching on the clause named by the output. When ∣ S ∣ ≥ β |S| \ge\beta ∣ S ∣ ≥ β satypy decodes the literal vertices of S S S S S S φ \varphi φ C C C φ ∧ ℓ \varphi\land\ell φ ∧ ℓ ℓ ∈ C \ell\in C ℓ ∈ C d d d d = 2 d = 2 d = 2 Theorem 8.7 .
Proposition 8.13 (Branching). Let β > p \beta> p β > p G = G β ( φ ) G = G_{\beta}(\varphi) G = G β ( φ ) S S S G G G ∣ S ∣ ≥ β |S| \ge\beta ∣ S ∣ ≥ β w w w
(i) S S S ⌊ ∣ S ∣ / β ⌋ ≥ 1 \lfloor|S|/\beta\rfloor\ge1 ⌊ ∣ S ∣/ β ⌋ ≥ 1 ⌊ ∣ S ∣ / β ⌋ \lfloor|S|/\beta\rfloor ⌊ ∣ S ∣/ β ⌋ φ \varphi φ
(ii) For every clause C C C φ \varphi φ φ \varphi φ φ ∧ ℓ \varphi\land\ell φ ∧ ℓ ℓ ∈ C \ell\in C ℓ ∈ C
(iii) Branching to depth d d d ∑ h = 0 d w h \sum_{h=0}^{d} w^{h} ∑ h = 0 d w h p p p q q q d d d
(iv) Every UNSATISFIABLE answer on an unsatisfiable formula and every SATISFIABLE answer is correct. If a satisfiable φ \varphi φ φ = φ 0 , φ 1 , … , φ d \varphi= \varphi_{0}, \varphi_{1}, \ldots, \varphi_{d} φ = φ 0 , φ 1 , … , φ d φ h + 1 \varphi_{h+1} φ h + 1 φ h ∧ ℓ h \varphi_{h} \land\ell_{h} φ h ∧ ℓ h ℓ h \ell_{h} ℓ h φ h \varphi_{h} φ h
Proof. (i) Theorem 8.6 (iii); ∣ S ∣ / β ≥ 1 |S|/\beta\ge1 ∣ S ∣/ β ≥ 1 ∣ S ∣ ≥ β |S| \ge\beta ∣ S ∣ ≥ β φ \varphi φ C C C ℓ ∈ C \ell\in C ℓ ∈ C φ ∧ ℓ \varphi\land\ell φ ∧ ℓ w w w d d d p p p q q q Lemma 8.4 . (iv) SATISFIABLE answers carry checked assignments. An unsatisfiable formula is answered UNSATISFIABLE at every node: by (ii) every branch is unsatisfiable, and at depth 0 by Theorem 8.7 (iii). Let φ 0 \varphi_{0} φ 0 ∣ S ∣ ≥ β |S| \ge\beta ∣ S ∣ ≥ β Lemma 8.2 (i) and (iii)). If d ≥ 1 d \ge1 d ≥ 1 φ 0 ∧ ℓ 0 \varphi_{0} \land\ell_{0} φ 0 ∧ ℓ 0 φ 1 \varphi_{1} φ 1 d − 1 d - 1 d − 1 d d d
Experiments
All experiments use SIRIAISA 0.0.8 and the scripts of the folder car/ of the repository: run_car.py (§ 9.2 ), car_bipartite.py (§ 9.3 ), car_ugc.py (§ 9.4 ), and car_split.py, car_cubic.py, car_circle.py and car_bounded.py (§ 9.5 ); § 9.6 uses the command batch_iris of the package. § 9.7 uses the scripts small_formulas.py and strategy_search.py of the folder car/ of the satypy repository [23 ] , which imports that repository’s own satyPy/. The scripts were written with Claude (Claude Opus 5.5) and run by the author; they import the repository’s own siriasia/, so they run whether or not the package is installed. The environment is Windows 11, Python 3.12.3, NetworkX 3.6.1 [19 ] , NumPy 2.4.6 and SciPy 1.17.1 [24 ] ; wall-clock times are machine dependent.
Reference values
The reference values are computed by the scripts only and are never given to Siriaisa; every set returned by Siriaisa or by an integer program is verified to be an independent dominating set (respectively a vertex cover or a set cover) before its size is used.
min ∑ v ∈ V x v s.t. ∑ u ∈ N [ v ] x u ≥ 1 ∀ v ∈ V , x u + x v ≤ 1 ∀ { u , v } ∈ E , x ∈ { 0 , 1 } V \min\sum_{v\in V} x_v \quad\text{s.t.}\quad\sum_{u\in N[v]} x_u \ge1\ \ \forall v\in V,\qquad x_u+x_v\le1\ \ \forall\{u,v\}\in E,\qquad x\in\{0,1\}^{V} min v ∈ V ∑ x v s.t. u ∈ N [ v ] ∑ x u ≥ 1 ∀ v ∈ V , x u + x v ≤ 1 ∀ { u , v } ∈ E , x ∈ { 0 , 1 } V solved by scipy.optimize.milp, which calls the HiGHS branch-and-cut solver [25 ] , with a sparse constraint matrix (scipy.sparse) and a time limit. When HiGHS reports an optimal status, the rounded objective is i ( G ) i(G) i ( G ) mip_dual_bound of HiGHS gives the certified lower bound ⌈ L ⌉ ≤ i ( G ) \lceil L\rceil\le i(G) ⌈ L ⌉ ≤ i ( G ) [ ⌈ L ⌉ , min ( ∣ S ∣ , incumbent ) ] [\lceil L\rceil,\min(|S|,\text{incumbent})] [⌈ L ⌉ , min ( ∣ S ∣ , incumbent )] open unless ∣ S ∣ = ⌈ L ⌉ |S|=\lceil L\rceil ∣ S ∣ = ⌈ L ⌉ min ∑ x v \min\sum x_v min ∑ x v x u + x v ≥ 1 x_u+x_v\ge1 x u + x v ≥ 1 min ∑ S x S \min\sum_{S}x_S min ∑ S x S ∑ S ∋ e x S ≥ 1 \sum_{S\ni e}x_S\ge1 ∑ S ∋ e x S ≥ 1
Linear relaxation of vertex cover. For the VC-IDS instances, the value of the linear relaxation of vertex cover is half the size of a maximum matching of the bipartite double cover H × K 2 H\times K_2 H × K 2 [26 ] ; it is computed with the Hopcroft–Karp algorithm [27 ] of NetworkX (bipartite.hopcroft_karp_matching) and rounded up, a certified lower bound on τ ( H ) \tau(H) τ ( H )
Closed forms and identities. i = ⌈ n / 3 ⌉ i=\lceil n/3\rceil i = ⌈ n /3 ⌉ i ( K a , b ) = min ( a , b ) i(K_{a,b})=\min(a,b) i ( K a , b ) = min ( a , b ) i = 2 i=2 i = 2 i = s c + ∣ S ∣ i=\mathrm{sc}+|S| i = sc + ∣ S ∣ [10 ] and i ( h ( H ) ) = τ ( H ) + 2 m H i(h(H))=\tau(H)+2m_H i ( h ( H )) = τ ( H ) + 2 m H Proposition 7.1 ), which turn bounds on s c \mathrm{sc} sc τ \tau τ i i i
Constructive upper bounds. For the Khot–Regev instances, the planted cover of the reduction, made independent greedily on violated constraints, bounds τ ( H ) \tau(H) τ ( H ) Proposition 7.1 turns it into an explicit independent dominating set of h ( H ) h(H) h ( H ) C D C_D C D Lemma 7.2 ) is a second upper bound.
Generators. All random graphs are built with NetworkX generators (gnp_random_graph, bipartite.random_graph, random_regular_graph, bipartite.configuration_model, random_labeled_tree and others), each with its own seed derived from the master seed and the instance name.
The certified lower bound L B LB L B Lemma 6.3 is used inside Siriaisa to stop its searches, not as a reference value.
Structured and random families
The script run_car.py generates 10,000 instances with at most 40 vertices from fifteen families (master seed 12345) and computes the exact optimum by the integer program with a time limit of 30 s. Every instance is tagged with the bound of Corollary 6.2 for its family: 1 for the rigid families, and the maximum degree for the bounded-degree and random families. Table 4 reports the results. The output is optimal on 9,999 instances; the remaining one is a Barabási–Albert graph with n = 20 n=20 n = 20 m = 36 m=36 m = 36 Δ = 7 \Delta=7 Δ = 7 ∣ S ∣ = 6 |S|=6 ∣ S ∣ = 6 i ( G ) = 5 i(G)=5 i ( G ) = 5
Table 4 : The suite of 10 000 graphs: number of instances, optimal outputs, mean and maximum ratio ∣ S ∣ / i ( G ) |S|/i(G) ∣ S ∣/ i ( G )
Table 4.
Bipartite graphs
MIDS is NP-complete on bipartite graphs [4 ] , so on these graphs there is no König-type formula for the optimum.
The script car_bipartite.py (option –quick) generates 112 bipartite graphs with 64 to 256 vertices from sixteen families: random bipartite graphs G ( n 1 , n 2 , p ) G(n_1,n_2,p) G ( n 1 , n 2 , p ) 1 : 2 1:2 1 : 2 d d d d = 3 , 4 , 8 d = 3, 4, 8 d = 3 , 4 , 8 G × K 2 G \times K_2 G × K 2 Q 6 Q_6 Q 6 Q 8 Q_8 Q 8 § 9.1 .
Table 5 reports the results. The optimum was proved on 95 instances, and the output is optimal on all of them. On the 17 open instances, all with n ≥ 200 n \ge200 n ≥ 200 ∣ S ∣ / ⌈ L ⌉ |S|/\lceil L\rceil ∣ S ∣/ ⌈ L ⌉ ∣ S ∣ |S| ∣ S ∣ G ( n / 3 , 2 n / 3 , p ) G(n/3, 2n/3, p) G ( n /3 , 2 n /3 , p ) n = 200 n = 200 n = 200 c 9 c_9 c 9 c 11 c_{11} c 11 Theorem 6.4 requires. SIRIAISA took at most 10.8 s per instance and 362.2 s in total; the integer programs took 1 439.5 s and the whole run 1 803.9 s.
Table 5. Bipartite graphs: instances, instances with the optimum proved (“Ref.”), optimal, suboptimal and open outputs, maximum and mean ratio (certified upper bounds on open instances), and the time of Siriaisa in seconds.
Instances of the hardness reductions
The script car_ugc.py (option –quick, integer programs limited to 60 s) builds 55 instances of the two reductions of § 7 . The SC-IDS instances are bipartite, of maximum degree B ∈ { 4 , 5 , 6 } B \in\{4, 5, 6\} B ∈ { 4 , 5 , 6 } B − 1 B - 1 B − 1 B B B i = s c + ∣ S ∣ i = \mathrm{sc} + |\mathcal{S}| i = sc + ∣ S ∣ h ( H ) h(H) h ( H ) H H H d d d H H H d ∈ { 3 , 4 , 5 } d \in\{3, 4, 5\} d ∈ { 3 , 4 , 5 } d d d H H H [15 ] : a Unique Games instance on a random 4-regular graph with 40 vertices and a planted labelling, 16 subsets per block drawn from the p p p k = 4 k = 4 k = 4 p = 0.45 p = 0.45 p = 0.45 η = 0 \eta= 0 η = 0 k = 3 k = 3 k = 3 p = 0.35 p = 0.35 p = 0.35 η = 0.1 \eta= 0.1 η = 0.1 [12 ] ); these h ( H ) h(H) h ( H ) τ ( H ) \tau(H) τ ( H ) L τ L_{\tau} L τ U τ U_{\tau} U τ Lemma 7.2 ; by Proposition 7.1 , L τ + 2 m H ≤ i ( h ( H ) ) ≤ U τ + 2 m H L_{\tau} + 2m_H \le i(h(H)) \le U_{\tau} + 2m_H L τ + 2 m H ≤ i ( h ( H )) ≤ U τ + 2 m H L τ = U τ L_{\tau} = U_{\tau} L τ = U τ § 9.1 ).
Table 6 reports the results. On the 18 SC-IDS instances the output is optimal. On the VC-IDS instances τ ( H ) \tau(H) τ ( H ) ∣ D ∣ / L |D|/L ∣ D ∣/ L ∣ D ∣ − L |D| - L ∣ D ∣ − L ∣ C D ∣ / L τ ≤ 1.35 |C_D|/L_{\tau} \le1.35 ∣ C D ∣/ L τ ≤ 1.35 H H H [22 ] , so they measure the algorithm on bounded-degree VC-IDS graphs without testing Corollary 7.4. The whole run took 1 061.5 s; Siriaisa took at most 25.6 s per instance.
The splitting excess on hard families
Four scripts measure the splitting excess s ( G ) s(G) s ( G ) § 6 ; all of them were run with the option –quick, so that n ≤ 400 n \le400 n ≤ 400 n ≤ 400 ( ‘ c a r s p l i t . p y ‘ , ‘ c a r c u b i c . p y ‘ , ‘ c a r c i r c l e . p y ‘ ) o r o f 60 s f o r n \le400 (`car_split.py`, `car_cubic.py`, `car_circle.py`) or of 60 s for n ≤ 400 ( ‘ c a r s pl i t . p y ‘ , ‘ c a r c u bi c . p y ‘ , ‘ c a r c i r c l e . p y ‘ ) or o f 60 s f or car_bounded.py). Each script asserts on every instance the statements of § 6 that apply to it, and no assertion failed.
Hard and structured families. The script car_split.py (seed 20261101) builds 110 instances of 29 families and computes, on each, k k k B B B s ( G ) s(G) s ( G ) H H H S 0 S^0 S 0 G G G ∣ V ( H ) ∣ = n − ∣ B ∣ + ∑ v ∈ B ⌈ deg ( v ) / k ⌉ |V(H)| = n - |B| + \sum_{v\in B}\lceil\deg(v)/k\rceil ∣ V ( H ) ∣ = n − ∣ B ∣ + ∑ v ∈ B ⌈ deg ( v ) / k ⌉ Δ ( H ) ≤ k \Delta(H) \le k Δ ( H ) ≤ k S 0 S^0 S 0 G G G Lemma 6.7 ), and that ∣ S 0 ∣ ≤ k ( U + s ( G ) ) |S^0| \le k\,(U + s(G)) ∣ S 0 ∣ ≤ k ( U + s ( G )) Theorem 6.8 ). Table 7 reports the results. s ( G ) = 0 s(G) = 0 s ( G ) = 0 k k k = s ( K 400 ) = s(K_{400}) = s ( K 400 ) s ( G ) / n 3 / 2 ≤ 0.950 s(G)/n^{3/2} \le0.950 s ( G ) / n 3/2 ≤ 0.950 S 0 S^0 S 0 s ( G ) > 0 s(G) > 0 s ( G ) > 0 ∣ S 0 ∣ / ( k ( U + s ( G ) ) ) |S^0|/(k\,(U + s(G))) ∣ S 0 ∣/ ( k ( U + s ( G ))) K 200 , 200 K_{200,200} K 200 , 200 i = 200 i = 200 i = 200 G ( n , 3 / n ) G(n,3/n) G ( n , 3/ n ) n ≤ 400 n \le400 n ≤ 400 ⌈ n / ( Δ + 1 ) ⌉ \lceil n/(\Delta+ 1)\rceil ⌈ n / ( Δ + 1 )⌉ ⌈ n / ( Δ + 1 ) ⌉ \lceil n/(\Delta+ 1)\rceil ⌈ n / ( Δ + 1 )⌉
Table 7. Splitting excess on hard and structured families (k = ⌊ n ⌋ k=\lfloor\sqrt{n}\rfloor k = ⌊ n ⌋ s ( G ) = 0 s(G)=0 s ( G ) = 0 s ( G ) s(G) s ( G ) s ( G ) / n 3 / 2 s(G)/n^{3/2} s ( G ) / n 3/2 S 0 S_0 S 0 i ( G ) i(G) i ( G ) ∣ S ∣ / L |S|/L ∣ S ∣/ L L L L d d d d d d
Cubic graphs. The script car_cubic.py (seed 20261102) builds 61 instances: every cubic graph on 4, 6 and 8 vertices (one, two and six graphs, collected as isomorphism classes of random 3-regular graphs), random cubic graphs of maximum degree 3 on 3 to 8 vertices, twelve named cubic graphs, and random cubic, cubic bipartite (three edge-disjoint random perfect matchings), double covers of random cubic graphs, cubic planar (duals of Delaunay triangulations with a triangular outer face), cubic planar bipartite (grown from the cube by inserting two rungs across an even face, which preserves planarity, bipartiteness and degree 3), random cubic graphs with 20% of the edges deleted, prisms, Möbius ladders and generalized Petersen graphs with 100 to 402 vertices. It asserts Proposition 6.16(i)–(ii), that the copy graph equals G G G s ( G ) = 0 s(G)=0 s ( G ) = 0 ∣ S ∣ ≤ n / 2 |S| \le n/2 ∣ S ∣ ≤ n /2 ∣ S ∣ ≤ 2 L |S| \le2L ∣ S ∣ ≤ 2 L s ( G ) = n s(G)=n s ( G ) = n n ∈ { 4 , 6 , 8 } n\in\{4,6,8\} n ∈ { 4 , 6 , 8 } s ( G ) = 0 s(G)=0 s ( G ) = 0 n ≥ 10 n\ge10 n ≥ 10 n ≤ 8 n\le8 n ≤ 8 s ( G ) ≤ 6 s(G)\le6 s ( G ) ≤ 6 ∣ S ∣ / L ≤ 1.0792 |S|/L\le1.0792 ∣ S ∣/ L ≤ 1.0792 G P ( 200 , 2 ) GP(200,2) GP ( 200 , 2 ) ∣ S ∣ = 120 |S|=120 ∣ S ∣ = 120 L = 103 L=103 L = 103 ∣ S ∣ / n |S|/n ∣ S ∣/ n K 3 , 3 K_{3,3} K 3 , 3 n ≥ 10 n\ge10 n ≥ 10 c 13 c_{13} c 13 n ≥ 10 n\ge10 n ≥ 10
Table 8. Cubic and subcubic graphs: the values of s ( G ) s(G) s ( G ) G G G ∣ S ∣ / n |S|/n ∣ S ∣/ n i ( G ) i(G) i ( G ) ∣ S ∣ / L |S|/L ∣ S ∣/ L L L L
Circle graphs. The script car_circle.py (seed 20261103) builds 40 circle graphs from chord models with 100 and 400 chords: chords with uniform random endpoints, short random chords of expected degree about 3, 10 and n \sqrt{n} n Proposition 6.19 (ii) of K n K_n K n K n / 2 , n / 2 K_{n/2,n/2} K n /2 , n /2 K n / 4 , 3 n / 4 K_{n/4,3n/4} K n /4 , 3 n /4 s ( G ) s(G) s ( G ) Proposition 6.19 (i), checks them against the circle graph built from the crossings, and checks that the models of the complete, complete bipartite, star, path and cycle families give these graphs. Table 9 reports the results. The degrees from the model agree with the graph on all instances; computing s ( G ) s(G) s ( G ) s ( K 400 ) = 7 600 s(K_{400}) = 7\,600 s ( K 400 ) = 7 600 s ( G ) / s ( K n ) ≤ 0.563 s(G)/s(K_n) \le0.563 s ( G ) / s ( K n ) ≤ 0.563 s ( G ) = 0 s(G) = 0 s ( G ) = 0 i ( K a , b ) = min ( a , b ) i(K_{a,b}) = \min(a,b) i ( K a , b ) = min ( a , b ) i = ⌈ n / 3 ⌉ i = \lceil n/3\rceil i = ⌈ n /3 ⌉ ∣ S ∣ / L ≤ 1.2143 |S|/L \le1.2143 ∣ S ∣/ L ≤ 1.2143
Table 9. Circle graphs built from chord models: largest number of edges and maximum degree, instances with s ( G ) = 0 s(G) = 0 s ( G ) = 0 s ( G ) s(G) s ( G ) s ( G ) / s ( K n ) s(G)/s(K_n) s ( G ) / s ( K n ) S 0 S_0 S 0 i ( G ) i(G) i ( G ) ∣ S ∣ / L |S|/L ∣ S ∣/ L L L L
Bounded degree with n ≥ B 2 n \ge B^2 n ≥ B 2 On graphs of maximum degree at most B B B n ≥ B 2 n \ge B^2 n ≥ B 2 s ( G ) = 0 s(G) = 0 s ( G ) = 0 Proposition 6.15 (a)), and MIDS is NP-hard to approximate within δ B \delta B δ B B ≥ B 0 B \ge B_0 B ≥ B 0 [10 ] . The script car_bounded.py (seed 20261104) builds 44 such graphs for B ∈ { 4 , 8 , 16 , 32 } B \in\{4, 8, 16, 32\} B ∈ { 4 , 8 , 16 , 32 } n ≥ max ( B 2 , 256 ) n \ge\max(B^2, 256) n ≥ max ( B 2 , 256 ) B B B B B B B B B B B B h ( H ) h(H) h ( H ) B B B H H H s b ∈ { 4 , 8 } s_b \in\{4, 8\} s b ∈ { 4 , 8 } Δ ≤ 3 s b \Delta\le3s_b Δ ≤ 3 s b 9 s b + 4 9s_b + 4 9 s b + 4 D D D t t t B B B t B tB tB ( B − 1 ) (B-1) ( B − 1 ) B B B D D D ∣ D ∣ = n / ( B + 1 ) = ⌈ n / ( Δ + 1 ) ⌉ |D| = n/(B + 1) = \lceil n/(\Delta+ 1) \rceil ∣ D ∣ = n / ( B + 1 ) = ⌈ n / ( Δ + 1 )⌉ i ( G ) = ∣ D ∣ i(G) = |D| i ( G ) = ∣ D ∣ i = s c + ∣ S ∣ i = \mathit{sc} + |S| i = sc + ∣ S ∣ i = τ ( H ) + 2 m H i = \tau(H) + 2m_H i = τ ( H ) + 2 m H s c \mathit{sc} sc τ ( H ) \tau(H) τ ( H ) s ( G ) = 0 s(G) = 0 s ( G ) = 0 ∣ S ∣ ≤ n / 2 |S| \le n/2 ∣ S ∣ ≤ n /2 ⌈ n / ( Δ + 1 ) ⌉ \lceil n/(\Delta+ 1) \rceil ⌈ n / ( Δ + 1 )⌉ Table 10 reports the results. s ( G ) = 0 s(G) = 0 s ( G ) = 0 ⌈ n / ( Δ + 1 ) ⌉ \lceil n/(\Delta+ 1) \rceil ⌈ n / ( Δ + 1 )⌉ ∣ S ∣ / L |S|/L ∣ S ∣/ L B = 4 B = 4 B = 4 B = 32 B = 32 B = 32 L = 338 L = 338 L = 338 L = 158 L = 158 L = 158
Table 10. Graphs of maximum degree B B B n ≥ B 2 n \ge B^2 n ≥ B 2 s ( G ) = 0 s(G) = 0 s ( G ) = 0 s ( G ) = 0 s(G) = 0 s ( G ) = 0 ∣ S ∣ / L |S|/L ∣ S ∣/ L i ( G ) i(G) i ( G ) ∣ S ∣ / L |S|/L ∣ S ∣/ L L L L
Complements of the DIMACS clique benchmark
The complements of the 68 graphs of the DIMACS clique benchmark [28 ] , in the form distributed with the NPBench collection [29 ] , were solved with batch_iris on the folder experiment/ of the repository, with the size option and logging; Table 11 reports the size of the returned independent dominating set and the time of Siriaisa recorded in the log. The optimum is not known for these instances, and no integer program was run. The time ranged from 0.016 s (MANN_a9) to 15.0 s (p_hat700-1), with mean 2.87 s and total 195.1 s.
Table 11. Complements of the DIMACS clique benchmark graphs: size ∣ S ∣ |S| ∣ S ∣
The SAT-IDS graphs of satypy
The scripts small_formulas.py and strategy_search.py decide formulas with satypy 0.0.4, with β = β ^ \beta= \hat{\beta} β = β ^ Lemma 8.4 ) and branching to depth 2 (Proposition 8.13 ), and with exhaustive search over all assignments, and compare the answers.
Small formulas. The script small_formulas.py used the eight DIMACS files of the folders benchmarks/simple and benchmarks/test_formulas of the satypy repository with at most ten variables and 180 random 3-CNF formulas, five for every number of variables from 3 to 5 and every number of clauses from 1 to 12 (seed 2026). All 188 answers agree with exhaustive search: 70 formulas are decided by unit propagation and pure literal elimination, 115 satisfiable formulas on the SAT-IDS graph of their residual formula, with ∣ S ∣ = p |S| = p ∣ S ∣ = p Table 12 lists the graphs by residual size ( p , q ) (p, q) ( p , q ) ∣ S ∣ = β + p |S| = \beta+ p ∣ S ∣ = β + p Theorem 8.6 (iii) the output contains the clause vertices of exactly one clause, and μ ( φ ) = 1 \mu(\varphi) = 1 μ ( φ ) = 1
Table 12: The SAT-IDS graphs of the 118 formulas of small_formulas.py decided on the MIDS graph, grouped by the residual size ( p , q ) (p,q) ( p , q ) β = β ^ \beta=\hat{\beta} β = β ^ ∣ S ∣ |S| ∣ S ∣ 2 p 2 2p^2 2 p 2 Theorem 8.7 .
Table 12.
Formulas built for the MIDS stage. The script strategy_search.py generates 3-CNF formulas with 3 to 6 variables and at most 16 clauses (seed 2026) of three kinds and keeps those whose residual formula reaches the SAT-IDS graph: satisfiable formulas with a single satisfying assignment, planted and completed by clauses it satisfies; satisfiable formulas satisfied by neither constant assignment; and unsatisfiable formulas. It obtained 20, 20 and 19 such formulas. For every formula it records the answer of satypy and, on the SAT-IDS graph of the residual formula, the output of every strategy c 1 , … , c 18 c_1,\ldots,c_{18} c 1 , … , c 18 ∣ S ∣ = p |S|=p ∣ S ∣ = p ∣ S ∣ = β + p |S|=\beta+p ∣ S ∣ = β + p μ ( φ ) = 1 \mu(\varphi)=1 μ ( φ ) = 1 ⌊ ∣ S ∣ / β ⌋ ≥ μ ( φ ) \lfloor|S|/\beta\rfloor\ge\mu(\varphi) ⌊ ∣ S ∣/ β ⌋ ≥ μ ( φ ) ⌊ ∣ S ∣ / β ⌋ \lfloor|S|/\beta\rfloor ⌊ ∣ S ∣/ β ⌋ Theorem 8.6 (ii) and Theorem 8.6 (iii) state. The graphs have 166 to 1084 vertices and 483 to 3222 edges, and each formula takes at most 30.7 seconds. Table 13 gives, for every strategy, the number of satisfiable formulas on which it returns p p p
Table 13: Number of the 40 satisfiable formulas of strategy_search.py on whose SAT-IDS graph each strategy of Algorithm 1 returns a minimum independent dominating set (p p p
Table 13.
By Lemma 8.4 , the SAT-IDS graph with β ^ = 2 p 2 − p + 1 \hat{\beta}=2p^2-p+1 β ^ = 2 p 2 − p + 1 2 q p 2 2qp^2 2 q p 2 Table 14 gives its size for residual 3-CNF formulas with the numbers of variables and clauses of the uniform random benchmark uf20–91 and of three instances of the aim family.
Table 14. Size of the SAT-IDS graph of a residual 3-CNF formula with p p p q q q β ^ \hat{\beta} β ^ Lemma 8.4 ); ∣ E ∣ = p + 3 q β ^ |E| = p + 3q\hat{\beta} ∣ E ∣ = p + 3 q β ^
Conclusion
Siriaisa 0.0.8 returns an independent dominating set (Theorem 4.3 ) in O ( ( n + m ) α A ( n ) ) O((n + m)\alpha_A(n)) O (( n + m ) α A ( n )) Theorem 5.2 ). It combines twelve base strategies, five improvers and a refinement; the exact solver of the ensemble is a conditioned dynamic program on induced forests, which replaces the bipartite exact solvers of Salvador because MIDS is NP-complete on bipartite graphs. The output has ratio at most Δ \Delta Δ Theorem 6.4 ), and has ratio at most n \sqrt{n} n Theorem 6.5 ; the degree-splitting strategy yields a dominating set of size at most ⌊ n ⌋ ( i ( G ) + s ( G ) ) \lfloor\sqrt{n}\rfloor(i(G) + s(G)) ⌊ n ⌋ ( i ( G ) + s ( G )) Theorem 6.8 ); the excess s ( G ) s(G) s ( G ) n ≥ Δ 2 n \geq\Delta^2 n ≥ Δ 2 6.15 ). On cubic graphs, on which MIDS is APX-hard, s ( G ) ≤ 8 s(G) \leq8 s ( G ) ≤ 8 s ( G ) = 0 s(G) = 0 s ( G ) = 0 n ≥ 10 n \geq10 n ≥ 10 Proposition 6.16 and Theorem 6.17 ); on planar graphs with n ≥ 400 n \geq400 n ≥ 400 s ( G ) < 2 n + 19 s(G) < 2\sqrt{n} + 19 s ( G ) < 2 n + 19 K 2 , n − 2 K_{2,n-2} K 2 , n − 2 s ≥ 2 n − 3 s \geq2\sqrt{n} - 3 s ≥ 2 n − 3 Proposition 6.18 ). On circle graphs, on which MIDS is not approximable within n ε n^{\varepsilon} n ε ε < 1 \varepsilon< 1 ε < 1 s ( G ) s(G) s ( G ) O ( n log n ) O(n \log n) O ( n log n ) s ( K n ) s(K_n) s ( K n ) Proposition 6.19 ), and Conjecture 6.20 restricted to circle graphs would imply P = NP (Corollary 6.22). On 10 000 structured and random graphs the output is optimal on 9 999; on 112 bipartite graphs it is optimal on all 95 instances with a proved optimum, and 17 are open; on the instances of the reductions of Chlebík and Chlebíková it is optimal on the 18 SC-IDS instances and on 2 of the 30 VC-IDS instances with a proved optimum, and the vertex cover decoded on the Khot–Regev instances has ratio between 1.25 and 1.8665. In the experiments of § 9.5 , the output is optimal on all 49 cubic graphs with a proved optimum, on all 8 planted perfect codes of degree up to 32, on 34 of the 38 circle graphs with a proved optimum, and on 79 of the 87 instances of the hard and structured families with a proved optimum.
On the SAT-IDS graph of the solver satypy 0.0.4, every independent dominating set has p p p β + p > 2 p 2 \beta+ p > 2p^2 β + p > 2 p 2 2 p 2p 2 p Theorem 8.7 ); the bound of Theorem 6.8 never separates satisfiable from unsatisfiable formulas (Proposition 8.8 ), branching on the clause named by the output is exact and polynomial for every fixed depth (Proposition 8.13 ), and with β t = p t ( 3 q ) t − 1 + 1 \beta_t = p^t(3q)^{t-1} + 1 β t = p t ( 3 q ) t − 1 + 1 n 1 − 1 / t n^{1-1/t} n 1 − 1/ t Theorem 8.9 ), so that Conjecture 6.20 would decide every formula in polynomial time (Corollary 8.12 ); its independent domination number determines the minimum number of falsified clauses (Theorem 8.6 ), with β ∗ \beta^* β ∗ 2 p L 2pL 2 p L Proposition 8.5 ), and on 247 small formulas every answer agrees with exhaustive search, with an optimal output on all 155 satisfiable instances of the graph (§ 9.7 ).
We do not claim that Siriaisa has ratio n 3 / 4 n^{3/4} n 3/4 Conjecture 6.20 , and a proof would imply P = NP (Theorem 6.21 ). Nor do we claim any bound of the form of Theorem 7.3 or Corollary 7.4, which would refute UGC unless P = NP, and would imply P = NP if the theorem reported in [13 ] holds. The implementation is freely available as the siriaisa package on PyPI [14 ] .
Acknowledgements
The author would like to thank Iris, Marilin, Sonia, Yoselin, and Arelis for their support.
Statements and Declarations
Declaration of interests
The author declares no competing interests.
Funding sources
This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.
Declaration of generative AI in scientific writing
The author designed the strategies of Siriaisa, and used Claude Opus 5.5 to implement them by vibe coding, to write the experiment scripts of the folder car/, and to improve the readability of this manuscript; the author ran all the experiments. After using this tool, the author reviewed and edited the code and the content as needed and takes full responsibility for the content of the publication.
Data availability
Code and data: https://github.com/frankvegadelgado/mids (release v0.0.8); the experiments of § 9 are reproduced by running the scripts of car/ and the command batch_iris on the folder experiment/.
