New · arXiv 2606.13834 — “Solving Subgraph Extraction Problems Using ΔSearch”

Hard graph problems,
solved one Δ at a time.

DeltaSearch is a general heuristic framework for subgraph extraction. Every candidate move is scored with an O(1) incremental delta over a Reward–Penalty objective — no full re-scans, no configuration, no drama.

Get started  ·  pip install delta-search Read the paper
  • Python 3.10+
  • Zero runtime dependencies
  • MIT licensed
  • mypy strict
  • CI green · 5 versions
  • 0
    NP-hard problems
  • 0
    solver strategies
  • 0
    tests passing
  • 0
    coverage, enforced
  • 0
    runtime dependencies
  • O(1)
    per candidate move
Overview

A single engine for six NP-hard problems

Subgraph extraction is everywhere — network design, facility placement, coverage, routing. DeltaSearch factors the hard part into one optional framework: a small, typed, dependency-free interface you apply to your own problem in minutes.

One framework, many problems

Maximum Planar Subgraph, Connected Dominating Set, Independent Set, Prize Collecting Vertex Cover, Facility Location, Steiner Tree — monotone and non-monotone alike. Same interface, six realizations.

General purpose

Constant-time moves

Every candidate mutation is scored with an O(1) incremental delta — no re-evaluation of the whole graph. An undo stack makes every step reversible, so backtracking costs nothing extra.

O(1) deltas · undo-stack

Built like it ships

Fully typed (mypy --strict), thread-safe graphs, 320+ tests, 80%+ enforced coverage, CI green across five Python releases — and a pure-standard-library runtime.

Zero deps · Typed · CI green
Framework

Five steps from input graph to answer

A tiny protocol, a greedy core, and pluggable solvers. Define your own problem in a handful of methods, or reach for a built-in one.

  1. Seed

    evaluate_initial_state builds a starting subgraph.

  2. Enumerate

    enumerate_actions lists candidate add/remove moves.

  3. Score

    calculate_delta returns reward − penalty in O(1).

  4. Commit · Undo

    apply_action or undo_action, always reversible.

  5. Converge

    Stop on budget, stall, or objective target.

In practice

A real run, rendered by the real library

  • The screenshot is an actual Maximum Planar Subgraph solve rendered with DeltaSearch’s solver — no hand-drawn demo data.
  • 62 nodes · 229 candidate edges. The solver keeps adding edges while a planarity check runs incrementally on each candidate move.
  • It lands exactly on the planar bound: 3V − 6 = 180 edges — the optimal limit for a simple planar graph.
  • The whole run evaluates one edge at a time in constant work per move, instead of re-checking the full graph at every iteration.
Rendered result of a Maximum Planar Subgraph solve: selected edges glow in violet and cyan over the faint input graph
✓ 3V − 6 bound reached · GreedySolver · MaximumPlanarSubgraphProblem
Built-in problems

The classics, covered out of the box

Each problem is a fleshed-out SubgraphExtractionProblem — instantiate it on a Graph, hand it to a solver, done.

Monotone

Maximum Planar Subgraph

MaximumPlanarSubgraphProblem

Keep as many edges as possible while the subgraph stays planar.

Monotone

Minimum Connected Dominating Set

MinimumConnectedDominatingSetProblem

The smallest connected vertex set that dominates the whole graph.

Monotone

Maximum Weight Independent Set

MaximumWeightedIndependentSetProblem

The heaviest set of mutually non-adjacent vertices.

Non-monotone

Prize Collecting Vertex Cover

PrizeCollectingVertexCoverProblem

Balance vertex cost against uncovered-edge penalties, collecting prizes.

Non-monotone

Uncapacitated Facility Location

UncapacitatedFacilityLocationProblem

Where to open facilities to serve demand at the lowest total cost.

Non-monotone

Minimum Weighted Steiner Tree

MinimumWeightedSteinerTreeProblem

Connect a set of terminals through optional nodes at minimum edge cost.

Performance

Fast to the answer. Easy to trust.

Constant-time deltas

Each move is scored from local context via calculate_delta, not a full graph re-evaluation.

Undo-stack rollback

Every mutation is logged in an undo stack. Backtracking restores prior state without re-scoring.

Thread-safe by default

ThreadSafeGraph wraps every read and write in an RLock for safe parallel search.

Observable convergence

The observer protocol exposes every action, delta, and objective — logging, metrics, and tracing for free.

objective vs iteration · real run
Convergence chart from a real solve: objective climbs monotonically to the planar bound
Max Planar Subgraph 62 nodes 229 edges in 180 edges out
Solvers

More than greedy

The greedy core is the floor, not the ceiling. Every strategy shares the same problem interface, so you can upgrade the search without rewriting the problem.

MultiStartSolver

Many random starts; the best result wins.

BeamSearchSolver

Top-κ candidate states explored in parallel.

AnytimeSolver

Best-so-far progress under a time budget.

AdaptiveBeamSolver

Diversity-aware beam ordering for better coverage.

LearnedGuidanceSolver

Online ML steers action choice as it explores.

MultiObjectiveSolver

Pareto-optimal frontiers across competing objectives.

StreamingSolver

Keep solving as the graph mutates under you.

HybridPipeline

Two-stage retrieval + reasoning, end to end.

API

Three lines to your first solve

Define a problem, point a solver at it, and read the result. Optional observers, early-stopping, and NetworkX interop when you need them.

solve.py 
from delta_search import Graph, GreedySolver, PrizeCollectingVertexCoverProblem

# Build an input graph with O(1) adjacency lookups.
graph = Graph[int].from_edges(
    [(1, 2), (2, 3), (3, 1), (3, 4),
     (4, 5), (5, 2), (1, 5)]
)

# Solve: cover every edge, keep the prize, pay vertex cost.
problem = PrizeCollectingVertexCoverProblem(graph, default_penalty=2.0)
result = GreedySolver(problem).solve(max_iterations=200)

print(result.best_objective)   # 95.0 — objective found
print(result.iteration)        # steps taken to get there
More patterns — custom problems, observers, early stopping, and NetworkX interop — in the docs/ directory. Install: pip install delta-search

Ship better graphs.

One pip install away from six NP-hard problems, constant-time moves, and a search you can actually watch converge.

Star on GitHub Read the arXiv paper

pip install delta-search · Python 3.10+ · MIT