Source-linked AI summary
Exact Algorithms for Maximum Independent Set
Mingyu Xiao, Hiroshi Nagamochi
TL;DR
The paper asks whether exact MIS can be solved faster under polynomial-space constraints and for bounded-degree graphs. It combines low-degree algorithms hierarchically with measure-and-conquer, structural analysis, case reduction, and edge branching, obtaining improved running times including 1.1996^n n^{O(1)} for MIS.
Problem
Exact MIS algorithms had longstanding worst-case running-time bounds, including a 1.2109^n n^{O(1)} exponential-space algorithm and slower published polynomial-space bounds.
Method
The algorithms hierarchically combine fast low-degree MIS procedures with measure-and-conquer, divide-and-conquer, case reduction, and branching on edges.
Results
The paper obtains a 1.1996^n n^{O(1)} polynomial-space algorithm for MIS, plus 1.1893^n n^{O(1)} for MIS-6 and 1.1970^n n^{O(1)} for MIS-7.
Takeaways & Limitations
The results improve published exact running-time bounds for MIS while using polynomial space, including improvements for maximum degrees 6 and 7.
Takeaways & Limitations
The MIS-7 analysis assumes w0=w1=w2=0 and determines weights w3 through w6 during the analysis.
Abstract
from arXiv · showhide
We show that the maximum independent set problem (MIS) on an $n$-vertex graph can be solved in $1.1996^nn^{O(1)}$ time and polynomial space, which even is faster than Robson's $1.2109^{n}n^{O(1)}$-time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of $1.1893^nn^{O(1)}$ and $1.1970^nn^{O(1)}$, respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analyses on the structure of bounded-degree graphs.
1 Introduction
The paper improves exact polynomial-space algorithms for maximum independent set, surpassing prior published bounds and extending improvements to bounded-degree graphs. Its approach hierarchically combines low-degree MIS algorithms with measure-and-conquer, case-reduction techniques, and a new edge-branching rule.
- Introduction: MIS remains a fundamental benchmark problem for worst-case analyses of exact algorithms, despite decades of prior contributions.
- Our contributions: 1.1996^n n^{O(1)} time with polynomial space solves MIS, improving on Robson’s 1.2109^n n^{O(1)} exponential-space algorithm.
- Our contributions: 1.1893^n n^{O(1)} and 1.1970^n n^{O(1)} time solve MIS-6 and MIS-7, respectively.
- Our contributions: The algorithms use divide-and-conquer to build higher-degree MIS algorithms from procedures for lower-degree graphs.
- Our contributions: Measure-and-conquer is combined with the hierarchical approach to propagate improvements from low-degree instances to high-degree instances.
- Our contributions: A case-reduction method simplifies analyses, while branching on edges handles difficult edges between end-vertices with many common neighbors.
2 Preliminaries
The preliminaries define graph notation, branch-and-reduce search, measure-and-conquer analysis, and preprocessing reductions used by the algorithms. They also specify removable and unconfined vertices, folding reductions, line-graph reductions, and the reduction procedure’s output.
- 2.1 Notation system: A graph G=(V,E) is simple and undirected, with n=|V| and α(G) denoting the maximum independent-set size.
- 2.1 Notation system: For vertex subsets, G−X deletes X and incident edges, G[X] induces X, G/X contracts X, and N(X), N[X] denote open and closed neighborhoods.
- 2.1 Notation system: For a vertex v, δ(v) is its degree; N2(v) contains vertices at distance two, while ev, fv, and qv describe local edges and low-degree vertices.
- 2.1 Notation system: Inner- and outer-neighbors classify each neighbor of v according to adjacency with v, with corresponding inner- and outer-degrees.
- 2.2 Branching algorithms and the measure-and-conquer method: Branch-and-reduce recursively creates smaller instances, combines their solutions, and bounds search-tree size through a recurrence over measure decreases.
- 2.2 Branching algorithms and the measure-and-conquer method: Amortization uses saved measure decrease, called a shift, to incorporate favorable branching operations into worst-case analysis.
- 2.2 Branching algorithms and the measure-and-conquer method: Measure-and-conquer assigns degree-dependent vertex weights, while reduction rules simplify local structures before branching.
- Reduction rules: Unconfined vertices are removable, meaning deleting one preserves α(G); complete k-independent sets and specified line-graph components are also reduced.
3 Divide-and-conquer method
The divide-and-conquer framework combines algorithms for low-degree graphs with procedures that reduce higher-degree instances. Applying this hierarchy yields progressively improved algorithms for MIS-6, MIS-7, MIS-8, and general MIS.
- Framework: The framework divides instances by maximum degree and reduces higher-degree graphs until a low-degree algorithm can solve them.For maximum degree at least j, reduction and branching lower the degree to at most j−1; the low-degree subalgorithm then applies.
- Framework: The combined algorithm uses a weighted vertex measure to bound the search-tree size and coordinate the high-degree procedure with the low-degree algorithm.The measure is a weighted sum of degree counts, and it is chosen so that it does not increase during reductions and decreases during branching.
- Results: 1.19951^n n^{O(1)} time solves general MIS in the presented application of the framework.The calculation uses τ′8 = 1.19749, τ8 = 1.19951, and λ = 1.
- Design considerations: The high-degree and low-degree procedures cannot always be designed independently because their branching factors and vertex weights constrain the combined algorithm.The paper therefore designs the high-degree procedure using the performance and weight values of the lower-degree algorithm as constraints.
- Hierarchy: The hierarchy constructs MIS-6 from MIS-5, MIS-7 from MIS-6, MIS-8 from MIS-7, and general MIS from MIS-8.This propagates improvements from algorithms for low-degree graphs to graphs with higher or unrestricted maximum degree.
4 Branching on High-Degree Vertices
The high-degree-vertex strategy branches on a maximum-degree vertex, analyzes the measure decreases in both branches, and uses a technical lemma to reduce the recurrence analysis dramatically.
- Branching rule: Branching on a maximum-degree vertex creates two subinstances: one excludes the vertex, while the other includes its extending grandchildren and removes their closed neighborhood.The corresponding measure decreases are denoted Δout(v) and Δin(v), producing recurrence C(μ) = C(μ−Δout(v)) + C(μ−Δin(v)).
- Measure analysis: The measure assigns nonincreasing marginal weights to higher-degree vertices, with the additional condition 2Δθ ≤ Δθ−1 for MIS-θ.These inequalities are automatically satisfied by the optimized weights used for MIS-6, MIS-7, and MIS-8.
- Measure analysis: Higher-degree neighbors make the exclusion branch decrease smaller because Δi ≥ Δi+1.The inclusion branch can remove additional vertices beyond N[v], producing a larger measure decrease under the stated local conditions.
- Recurrence analysis: The recurrence analysis examines neighbor-degree configurations and uses graph structure to establish lower bounds on the inclusion-branch decrease.The decrease depends on local quantities such as edges between N[v] and distance-two vertices and the number of lower-degree vertices at distance two.
- Recurrence analysis: Lemma 5 reduces the number of concrete recurrences from (d + 1)^{d−3} to d − 2 by eliminating redundant neighbor-degree cases.For d = 6, this changes 2401 recurrences to 5; the method can also reduce previous MIS analyses to about 50 recurrences.
5 Branching on Edges
The edge-branching rule addresses dense neighborhoods where vertex branching gives weak bounds. It transforms an edge case into two subinstances while preserving the independent-set optimum through alternative-set structure.
- Motivation: Small fv and dense local neighborhoods can make vertex branching ineffective, motivating a rule that branches directly on edges.The paper targets edges whose endpoints have many common neighbors, called short edges.
- Alternative sets: Alternative sets are equal-sized disjoint independent sets such that some maximum independent set chooses one set or the other.For such sets A and B, the transformed graph G† satisfies α(G) = α(G†) + |A|.
- Edge branching: Branching on an edge either removes both endpoints or constructs G† after removing their common neighbors and adding edges between suitable exclusive neighbors.The transformation connects each nonadjacent pair consisting of an exclusive neighbor of one endpoint and an exclusive neighbor of the other.
- Edge selection: In MIS-6, MIS-7, and MIS-8, the algorithm branches only on optimal short edges under degree- and common-neighbor conditions specific to each degree bound.For degree bounds 7 and 8, short edges require both endpoints to have degree θ and at least four common neighbors.
6 Algorithms
The algorithms combine branching for low-degree MIS with procedures that eliminate higher-degree vertices, switching hierarchically between degree bounds. This yields improved branching factors and running times for bounded-degree and general graphs.
- Algorithmic framework: For θ = 6, 7, and 8, the algorithm branches on high-degree vertices, short edges, and then selected maximum-degree vertices, invoking MIS-(θ −1) below the threshold.The selected maximum-degree vertices are chosen using structural criteria based on neighborhoods and neighbor degrees.
- Structural selection: A reduced graph of maximum degree 6, 7, or 8 with no short edges always contains an optimal vertex for the corresponding algorithm.This structural guarantee supports the selection rule used in the final branching stage.
- Running-time analysis: Each recurrence has branching factor at most 1.18922 for mis6, 1.19698 for mis7, and 1.19951 for mis8.These bounds follow from the chosen vertex-weight setting.
- Running-time results: Maximum independent set can be found in 1.1893^n n^{O(1)} time for maximum degree 6 and 1.1970^n n^{O(1)} time for maximum degree 7.The theorem covers maximum degrees 6, 7, and 8; the supplied passage explicitly shows the bounds for 6 and 7.
- General graphs: For general graphs, branching while the degree is at least 9 and then invoking mis8 yields a 1.1996^n n^{O(1)}-time polynomial-space algorithm.The high-degree procedure has branching factor 1.19749, while the overall stated theorem gives the 1.1996 bound.
7 Analysis of mis6(G)
The mis6 analysis bounds measure changes for reductions and branching configurations, identifies short-edge recurrences as the bottleneck, and optimizes vertex weights through a quasiconvex program.
- Measure design: Contracting vertices does not increase the measure under the imposed weight constraints.The proof verifies the required inequality across low- and high-degree cases.
- Reduction analysis: Reduction RG(G, s) never increases the measure, and decreases it by at least 2∆w_d when the maximum degree drops in a graph with minimum degree at least 3.This supplies progress for the reduction phase of mis6.
- Vertex branching: For a vertex v with no special neighbors, at least 2δ(v) edges connect N(v) to N2(v), strengthening the measure decrease around N[v].When special neighbors exist, the analysis derives alternative lower bounds involving w3 and ∆w6.
- Short-edge branching: The worst mis6 recurrences arise from branching on short edges whose endpoints both have degree 6, rather than from branching on vertices of degree at least 7.The analysis introduces a positive shift because a degree-at-least-7 vertex is created after the second short-edge branch.
- Optimization result: The recurrences are converted into quasiconvex constraints, producing an upper bound of 1.18922 on the branching factor with optimized vertex weights.A feasible shift of σ = 0.10647 completes the verification for θ = 6.
8 Analysis of mis7(G)
The mis7 analysis extends the mis6 framework with degree-7 weights, structural bounds for optimal vertices, and recurrence optimization, yielding a branching-factor bound of 1.19698.
- Measure and framework: MIS-7 retains the hierarchical branch-and-reduce framework and uses weights with w1 = w2 = 0 and w7 = 1.Weights for degrees 3 through 6 are optimized, and higher-degree weights continue linearly.
- High-degree branching: For vertices of degree at least 8, the analysis considers the degree-8 case as sufficient for the relevant recurrence constraints.This reduction follows from the recurrence comparison supplied by Lemma 5.
- Branching structure: MIS-7 branches on optimal short edges and then on optimal degree-7 vertices after short edges are exhausted.The selected degree-7 vertices exploit outer-degree properties and neighborhood structure.
- Branching structure: An optimal degree-7 vertex exists in every reduced maximum-degree-7 graph with no short edges.This structural fact supports the final branching stage of mis7.
- Optimization result: Solving the quasiconvex program gives an upper bound of 1.19698 on the branching factor for all mis7 recurrences.The optimization combines the recurrence constraints, including the invocation of mis6 in the hierarchical procedure.
9 Analysis of mis8(G)
The mis8(G) analysis combines degree-based branching, short-edge branching, and a switch to MIS-7, yielding an upper bound of 1.19951 on all recurrence branching factors.
- Degree-8 branching: Step 4 analyzes branching on an optimal degree-8 vertex through recurrences whose correctness is supported by a structural lemma.The lemma bounds measure decreases according to the degree-8 neighborhood structure.
- Degree reduction: Step 5 invokes mis7(G), extending the hierarchical analysis from degree-8 instances to the degree-7 subproblem.This invocation is incorporated into the recurrence constraints.
- Branching-factor analysis: 1.19951 is the upper bound on the branching factor for all recurrences after solving the quasiconvex program.The bound is obtained by setting degree-dependent vertex weights.
10 Proof of Lemma 8
The proof of Lemma 8 establishes structural conditions guaranteeing optimal vertices in reduced graphs of maximum degree 6, 7, and 8, with exceptional line-graph structures treated separately.
- Maximum degree 6: The degree-6 proof derives these conditions by analyzing neighborhood edge counts, inner-degrees, outer-degrees, and several configurations of G[N(v)].The cases include cycles, disjoint triangles, paths, and triangles in the neighborhood graph.
- Maximum degree 6: Lemma 16 guarantees a degree-6 vertex satisfying one of several neighborhood-structure conditions unless the graph is the line graph of a 4-regular graph.The conditions are expressed through counts such as k3, k4, k5, k6 and the quantity fv + (fv−|N2(v)|) + qv.
- Maximum degree 7: Lemma 17 shows that a 7-regular graph not equal to the line graph of a (4,5)-bipartite graph has a vertex with fv + (fv−|N2(v)|) ≥26.The proof uses properties of neighborhood clique structure and cross-edges between inner and outer neighborhoods.
- Maximum degree 7: Lemma 18 guarantees at least one optimal vertex in every reduced graph of maximum degree 7 without short edges.This converts the structural analysis into the vertex-existence property needed by the algorithm.
- Maximum degree 8: Lemma 19 gives fv + (fv−|N2(v)|) ≥36 in an 8-regular graph containing a bridge-type vertex.The result supplies the structural bound used for the degree-8 analysis.
11 Concluding Remarks
The concluding analysis explains how measure-and-conquer, short-edge branching, and graph-structural selection of optimal vertices improve MIS recurrences while reducing case complexity.
- Simplifying analysis: Lemma 5 reduces many recurrence cases without losing optimality of the branching factors, simplifying correctness analysis in the branch-and-reduce framework.The method can also be applied to analyses of previous algorithms without modifying their algorithms.
- Improved recurrences: Short-edge branching improves the bounds on ∆(N[v]) to 3d∆wd for d = 6, 7 and 4d∆wd for d ≥8 in the stated worst cases.These bounds strengthen earlier worst-case analyses for branching on maximum-degree vertices.
- Improved recurrences: Choosing an optimal vertex, whose existence follows from graph-theoretic arguments, further increases the measure-decrease bound for the relevant branching cases.For d = 8 and k8 = d, the bound becomes (4d + 4)∆wd.
- Remaining bottleneck: The final worst case is branching on a degree-8 vertex with eight degree-8 neighbors and fv = 36 edges between N(v) and N2(v).This configuration is identified as a crucial bottleneck of the MIS algorithm.