State Compression DP for Graph Connectivity Problems: Algorithms and Implementations

State compression DP solves graph connectivity problems by encoding vertex subsets as bitmasks, enabling polynomial-time solutions for exponential-space problems like Steiner trees and Hamiltonian paths.

The hzwer/shareoi repository hosts a comprehensive collection of competitive programming training materials specifically covering state compression DP for graph connectivity problems. This curated archive contains specialized slide decks that explain how to apply subset dynamic programming to solve otherwise intractable connectivity challenges in OI/ICPC competitions.

Understanding State Compression DP

State compression dynamic programming (also called subset DP or bitmap DP) represents sets of vertices using integer bitmasks rather than explicit collections. When solving graph connectivity problems, this technique stores connectivity information—such as which terminals are already connected or the current component structure—directly in the bitmask state.

The approach relies on the observation that for $k$ relevant vertices, there are $2^k$ possible subsets. By mapping each subset to a bitmask (where the $i$-th bit indicates inclusion of vertex $i$), algorithms iterate over subsets using efficient bit operations like sub = (sub - 1) & mask.

Repository Structure and Key Resources

The hzwer/shareoi repository organizes educational content under thematic directories. For connectivity-focused state compression DP, the relevant materials reside in the 动态规划/ (Dynamic Programming) folder:

File Path	Content Focus
动态规划/状态压缩类型动态规划_朱全民..ppt	General subset DP fundamentals, bitmask iteration techniques, and complexity analysis
动态规划/基于连通性状态压缩的动态规划问题_陈丹琦.ppt	Specialized connectivity applications including Steiner trees, Hamiltonian paths, and spanning-tree enumeration
图论/图的连通_黄哲威.pdf	Prerequisite graph theory concepts including connected components and cut vertices
数据结构/可并堆_王天懿.ppt	Mergeable heap data structures for optimizing Dijkstra steps within DP transitions

These files form a complete learning pipeline: master general subset iteration, then specialize to connectivity constraints, and finally optimize with advanced data structures.

Core Connectivity Problems and DP Formulations

Steiner Tree DP

The Steiner tree problem asks for the minimum-weight tree connecting $k$ specified terminal vertices in a weighted graph. The state compression DP formulation uses:

• State: dp[mask][v] = minimum cost of a tree connecting the terminals in mask and ending at vertex v
• Transition: Combine two smaller subsets at the same vertex: dp[mask][v] = min(dp[sub][v] + dp[mask^sub][v])
• Propagation: Run Dijkstra's algorithm for each mask to spread costs through the graph edges

This yields the classic Dreyfus-Wagner algorithm with complexity $O(3^k \cdot (n + m) \log n)$.

Hamiltonian Path and Cycle Enumeration

For counting or optimizing paths that visit each vertex exactly once:

• State: dp[mask][v] = number of ways (or minimum cost) to form a path covering vertices in mask and terminating at v
• Transition: dp[mask][v] += dp[mask ^ (1<<v)][u] for all edges $(u,v)$ where $u \in mask$
• Complexity: $O(2^n \cdot n^2)$, feasible for $n \leq 20$

Spanning Tree Enumeration with Kirchhoff's Theorem

Advanced applications combine state compression with Kirchhoff's matrix-tree theorem to count connected subgraphs satisfying specific degree constraints, particularly useful for network reliability problems.

Implementation: Steiner Tree Solver

The following C++ implementation mirrors the algorithm described in 动态规划/基于连通性状态压缩的动态规划问题_陈丹琦.ppt. It demonstrates combining subset iteration with Dijkstra propagation:

// steiner.cpp – subset DP for the Steiner Tree problem
// Compile with: g++ -std=c++17 -O2 steiner.cpp -o steiner
#include <bits/stdc++.h>
using namespace std;

const long long INF = 4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;                     // n vertices, m edges, k terminals
    cin >> n >> m >> k;
    vector<int> term(k);               // 0‑based indices of terminals
    for (int i = 0; i < k; ++i) { cin >> term[i]; --term[i]; }

    // adjacency list
    vector<vector<pair<int,int>>> g(n);
    for (int i = 0, u, v, w; i < m; ++i) {
        cin >> u >> v >> w; --u; --v;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }

    int S = 1 << k;                    // number of subsets
    vector<vector<long long>> dp(S, vector<long long>(n, INF));

    // initialise single‑terminal states
    for (int i = 0; i < k; ++i)
        dp[1<<i][term[i]] = 0;

    // iterate over subsets
    for (int mask = 1; mask < S; ++mask) {
        // combine two smaller subsets
        for (int sub = (mask-1)&mask; sub; sub = (sub-1)&mask) {
            int other = mask ^ sub;
            for (int v = 0; v < n; ++v) {
                dp[mask][v] = min(dp[mask][v],
                                   dp[sub][v] + dp[other][v]);
            }
        }
        // run Dijkstra to propagate through the graph
        priority_queue<pair<long long,int>,
                       vector<pair<long long,int>>,
                       greater<pair<long long,int>>> pq;
        vector<char> inq(n, 0);
        for (int v = 0; v < n; ++v)
            if (dp[mask][v] < INF) {
                pq.push({dp[mask][v], v});
                inq[v] = 1;
            }
        while (!pq.empty()) {
            auto [dist, u] = pq.top(); pq.pop();
            if (dist != dp[mask][u]) continue;
            for (auto [to, w] : g[u]) {
                if (dp[mask][to] > dist + w) {
                    dp[mask][to] = dist + w;
                    pq.push({dp[mask][to], to});
                }
            }
        }
    }

    long long ans = INF;
    for (int v = 0; v < n; ++v) ans = min(ans, dp[S-1][v]);
    cout << ans << '\n';
    return 0;
}

Key implementation details:

• The outer loop iterates mask from $1$ to $2^k-1$
• The inner subset iteration for (int sub = (mask-1)&mask; sub; sub = (sub-1)&mask) enumerates all non-empty proper submasks in $O(3^k)$ total across all masks
• Dijkstra's algorithm runs for each mask to relax edge weights, avoiding $O(n^2)$ all-pairs shortest path precomputation

Optimization Techniques

State Reduction Pruning

Eliminate masks that already form connected components without required terminals. The slides in 基于连通性状态压缩的动态规划问题_陈丹琦.ppt describe canonical labeling techniques to compress equivalent connectivity patterns, reducing the state space from $2^k$ to the $k$-th Bell number.

Mergeable Heaps

When edge weights change dynamically or the graph is dense, replace Dijkstra's binary heap with a Fibonacci heap or pairing heap as detailed in 数据结构/可并堆_王天懿.ppt. This reduces the transition cost from $O(m \log n)$ to $O(m + n \log n)$ per mask.

Summary

• State compression DP encodes vertex subsets as bitmasks to solve exponential graph problems in polynomial time relative to $2^k$
• The hzwer/shareoi repository provides specialized training materials in 动态规划/基于连通性状态压缩的动态规划问题_陈丹琦.ppt for mastering these techniques
• Steiner tree problems use dp[mask][v] states with subset combination and shortest-path propagation, achieving $O(3^k \cdot (n+m)\log n)$ complexity
• Hamiltonian path problems employ similar states but transition through adjacency lists rather than subset merging
• Prerequisites include strong knowledge of graph connectivity (from 图论/图的连通_黄哲威.pdf) and heap data structures for optimization

Frequently Asked Questions

What is the difference between general state compression DP and connectivity-specific variants?

General state compression DP focuses on subset selection problems like the traveling salesman problem or set cover, where the mask simply tracks visited elements. Connectivity-specific variants embed additional graph structure into the state—such as which vertices belong to the same connected component or maintaining forest structures—to ensure the final solution forms a valid connected subgraph.

What is the time complexity of the Steiner tree DP algorithm?

The standard implementation runs in $O(3^k \cdot (n + m) \log n)$ time, where $k$ is the number of terminals, $n$ is the vertex count, and $m$ is the edge count. The $3^k$ factor emerges because each mask $mask$ has $2^{|mask|}$ submasks, and $\sum_{mask} 2^{|mask|} = 3^k$. Space complexity is $O(2^k \cdot n)$ for storing the DP table.

Can state compression DP handle directed graphs?

Yes, the technique extends naturally to directed graphs. For Steiner trees in directed graphs (Steiner arborescences), the DP transition only considers edges directed toward the root, and the Dijkstra propagation step becomes a shortest path computation on the directed graph. The complexity remains identical, though the constant factors increase due to asymmetric adjacency.

What mathematical prerequisites are needed before studying these algorithms?

You should understand bitwise operations (AND, OR, XOR, bit shifts), basic graph theory (connectivity, trees, shortest paths), and dynamic programming fundamentals. The repository recommends reviewing 图论/图的连通_黄哲威.pdf for graph connectivity concepts and understanding Dijkstra's algorithm before attempting the connectivity DP implementations.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}