Closure problem¶

The optimization problem of selecting a maximum-weight vertex set in a directed graph subject to the rule that selecting a vertex also selects every vertex reachable along its outgoing dependencies.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3714
Domain group: Formal Sciences
Origin domain: Operations Research
Subdomain: Combinatorial Optimization → Operations Research

Core Idea¶

A closure of a directed graph contains every successor of each selected vertex; the maximum-closure problem asks for a closure maximizing the sum of vertex weights. Positive and negative vertex weights are encoded as source and sink capacities, dependency arcs receive effectively infinite capacity, and a minimum cut identifies the optimal closed set. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Best Pick With Tag-Alongs

Imagine picking toys from a list, but some toys come with rules: if you take the train, you must also take its track. Some toys give you points and some cost you points. The closure problem is finding the group of toys that follows every rule and gives the most points.

Best Group That Follows the Rules

Picture a set of tasks drawn as dots, with arrows meaning 'if you pick this, you must also pick that'. Each dot has a value, some positive like earnings and some negative like costs. A closure is a group of dots that obeys every arrow: whenever a dot is in the group, everything it points to is in the group too. The maximum-closure problem asks for the closure with the biggest total value. It can be solved quickly by turning it into a problem about cutting a network of pipes in the cheapest way.

Maximum-Weight Closed Set

In a directed graph, a closure is a set of vertices that contains every successor of each vertex in it: if a vertex is chosen and has an arrow to another vertex, that one must be chosen too. Given a weight on each vertex, positive or negative, the maximum-closure problem asks for the closure with the largest total weight. It models choices with prerequisites, where taking something valuable forces you to also take some costly things it depends on. It can be solved efficiently by building a flow network: connect positive-weight vertices from a source and negative-weight vertices to a sink with capacities equal to their weights, give the dependency arrows effectively infinite capacity, and find a minimum cut. The side of the cut containing the source gives the best closure.

Given a directed graph with vertex weights, a closure is a vertex set closed under successors: if v is in the set and v → u is an arc, then u is in the set. The maximum-closure problem asks for a closure of maximum total weight, where weights may be positive or negative. The standard reduction encodes positive weights as capacities of arcs from a source, negative weights (in absolute value) as capacities of arcs to a sink, and each dependency arc with effectively infinite capacity so that no finite cut can violate closure. A minimum s–t cut then identifies the optimal closed set as the source side, since the cut value equals the total positive weight minus the closure's weight. The problem is defined by both conditions together: successor-closure under every directed edge and maximality of declared total weight among all such sets. Relaxing closure, or optimizing something other than the sum of vertex weights, gives a different problem.

Scope of Application¶

Closure problem belongs to combinatorial optimization and is useful where the analyst can specify the typed combinatorial optimization carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate the selected vertex set is successor-closed under every directed edge and has maximum total declared weight among all such sets. The scope is broad within that domain but bounded by the need for the selected vertex set is successor-closed under every directed edge and has maximum total declared weight among all such sets. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the selected vertex set is successor-closed under every directed edge and has maximum total declared weight among all such sets the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Closure problem can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Closure problem. Closure problem compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed combinatorial optimization carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the selected vertex set is successor-closed under every directed edge and has maximum total declared weight among all such sets independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of combinatorial optimization because they reuse the typed combinatorial optimization carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, Positive and negative vertex weights are encoded as source and sink capacities, dependency arcs receive effectively infinite capacity, and a minimum cut identifies the optimal closed set., and type the carrier, state every parameter and convention in the definition, test that the selected vertex set is successor-closed under every directed edge and has maximum total declared weight among all such sets, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Closure problem Domain-specific

Parents (1) — outgoing typed relations

Closure problem is a kind of Constraint Prime

What makes it its own entry: the domain-specific identity determined by the selected vertex set is successor-closed under every directed edge and has maximum total declared weight among all such sets.

Hierarchy path (1) — routes to 1 parentless root

Closure problem → is a kind of Constraint

Neighborhood in Abstraction Space¶

Closure problem sits in a crowded region of the domain-specific corpus (4^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Combinatorial Optimization on Graphs (16 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25