Combinatorial Optimization on Graphs

← Back to Domain-Specific Families

Abstractions about optimization problems defined over graphs and networks — matchings, flows, and cuts such as circulation, closure, and multi-commodity flow problems — and routing problems including the traveling-salesman, Steiner tree, and shortest-path variants solved by structured algorithms like Held–Karp.

16 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• 3-dimensional matching — A matching in a tripartite 3-uniform hypergraph: a set of triples no two of which share any coordinate, with optimization and perfect-decision variants.
• Balanced matrix — A binary matrix containing no odd-order square submatrix in which every row and column has exactly two ones.
• Baranyai's theorem — The theorem that a complete uniform hypergraph can be decomposed into perfect matchings whenever the edge size divides the number of vertices.
• Circulation problem — A network-flow feasibility or optimization problem assigning edge flows within lower and upper bounds while conserving flow at every vertex.
• 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.
• Diameter (graph theory) — Measure a connected graph by the maximum shortest-path distance over all pairs of vertices.
• Dissociation number — The maximum number of vertices in a graph whose induced subgraph has maximum degree at most one.
• Gomory–Hu tree — A weighted tree representing every pairwise minimum-cut value of an undirected capacitated graph through the minimum edge on the corresponding tree path.
• Held–Karp algorithm — An exact dynamic-programming algorithm for the traveling-salesman problem that stores the cheapest start-to-end path through each subset of cities, reducing tour enumeration to exponential subset recurrence.
• Multi-commodity flow problem — Route multiple source–sink commodities through one capacitated network while each commodity obeys flow conservation and all commodities jointly share edge capacities, optimizing congestion, cost, or satisfied demand.
• Quasi-bipartite graph — A Steiner-tree instance in which the nonterminal vertices form an independent set, so every edge has at least one terminal endpoint.
• Recursive tree — A rooted labeled non-plane tree whose labels increase strictly along every path away from the root, often generated by attaching each new label to an earlier vertex.
• Set TSP problem — A traveling-salesman generalization seeking a minimum-cost tour that visits at least one vertex from every specified group.
• Shortest path problem — The optimization problem of finding a path between specified graph vertices whose accumulated edge or path weight is minimal among all admissible paths.
• Steiner tree problem — The optimization problem of connecting specified terminal points at minimum total cost while permitting additional intermediate Steiner points or vertices.
• Submodular flow — A combinatorial optimization problem that minimizes linear flow cost subject to edge bounds and submodular constraints on net flow across every vertex subset.