Module graph 

Graph problems.

Problems whose input is a graph (optionally weighted):

• AcyclicPartition: Partition a digraph into bounded-weight groups with an acyclic quotient graph
• BoundedDiameterSpanningTree: Spanning tree with bounded weight and diameter
• DegreeConstrainedSpanningTree: Spanning tree with maximum vertex degree at most K
• DirectedHamiltonianPath: Directed Hamiltonian path (decision problem)
• MaximumIndependentSet: Maximum weight independent set
• MaximumLeafSpanningTree: Spanning tree maximizing number of leaves
• MaximalIS: Maximal independent set
• MinimumVertexCover: Minimum weight vertex cover
• MinimumCoveringByCliques: Minimum number of cliques covering all edges
• MonochromaticTriangle: 2-color edges so that no triangle is monochromatic
• MinimumIntersectionGraphBasis: Minimum universe size for intersection graph representation
• MinimumCapacitatedSpanningTree: Minimum weight spanning tree with subtree capacity constraints
• MinimumDominatingSet: Minimum dominating set
• MinimumMetricDimension: Minimum resolving set (metric dimension)
• MinimumEdgeCostFlow: Minimum edge-cost integral flow
• MinimumGeometricConnectedDominatingSet: Minimum connected dominating set in a geometric point set
• MinimumFeedbackVertexSet: Minimum weight feedback vertex set in a directed graph
• MaximumClique: Maximum weight clique
• MaximumAchromaticNumber: Maximum number of colors in a complete proper coloring
• MaximumDomaticNumber: Maximum partition into disjoint dominating sets
• MaxCut: Maximum cut on weighted graphs
• MinimumCutIntoBoundedSets: Minimum cut into bounded sets (Garey & Johnson ND17)
• MinimumDummyActivitiesPert: Minimum dummy activities in activity-on-arc PERT networks
• HamiltonianCircuit: Hamiltonian circuit (decision problem)
• IsomorphicSpanningTree: Isomorphic spanning tree (satisfaction)
• Kernel: Kernel of a directed graph (independent and absorbing vertex subset)
• KClique: Clique decision problem with threshold k
• KthBestSpanningTree: K distinct bounded spanning trees (satisfaction)
• KColoring: K-vertex coloring
• PartitionIntoTriangles: Partition vertices into triangles
• MaximumMatching: Maximum weight matching
• MinimumMaximalMatching: Minimum-size maximal matching
• TravelingSalesman: Traveling Salesman (minimum weight Hamiltonian cycle)
• SpinGlass: Ising model Hamiltonian
• MinimumMultiwayCut: Minimum weight multiway cut
• HamiltonianPath: Hamiltonian path (simple path visiting every vertex)
• HamiltonianPathBetweenTwoVertices: Hamiltonian path between two specified vertices (decision problem)
• LongestPath: Maximum-length simple s-t path
• ShortestWeightConstrainedPath: Bicriteria simple s-t path with length and weight bounds
• PartitionIntoCliques: Partition vertices into K groups each inducing a clique
• PartitionIntoForests: Partition vertices into K classes each inducing an acyclic subgraph
• PartitionIntoPerfectMatchings: Partition vertices into K groups each inducing a perfect matching
• PartitionIntoPathsOfLength2: Partition vertices into triples with at least two edges each
• BicliqueCover: Biclique cover on bipartite graphs
• SteinerTreeInGraphs: Minimum weight Steiner tree connecting terminal vertices
• BalancedCompleteBipartiteSubgraph: Balanced biclique decision problem
• BiconnectivityAugmentation: Biconnectivity augmentation with weighted potential edges
• BoundedComponentSpanningForest: Partition vertices into bounded-weight connected components
• BottleneckTravelingSalesman: Hamiltonian cycle minimizing the maximum selected edge weight
• MultipleCopyFileAllocation: File-copy placement under storage and access costs
• OptimalLinearArrangement: Optimal linear arrangement (total edge length at most K)
• PartialFeedbackEdgeSet: Remove at most K edges to hit every short cycle
• RootedTreeArrangement: Rooted-tree embedding with bounded total edge stretch
• MinimumFeedbackArcSet: Minimum feedback arc set on directed graphs
• MinMaxMulticenter: Min-max multicenter (vertex p-center, satisfaction)
• MinimumSumMulticenter: Min-sum multicenter (p-median)
• MultipleChoiceBranching: Directed branching with partition constraints
• LengthBoundedDisjointPaths: Length-bounded internally disjoint s-t paths
• PathConstrainedNetworkFlow: Integral flow on a prescribed collection of directed s-t paths
• RuralPostman: Rural Postman (circuit covering required edges)
• MixedChinesePostman: Mixed-graph postman tour with bounded total length
• SteinerTree: Minimum-weight tree spanning all required terminals
• SubgraphIsomorphism: Subgraph isomorphism (decision problem)
• DirectedTwoCommodityIntegralFlow: Directed two-commodity integral flow (satisfaction)
• IntegralFlowBundles: Integral flow feasibility with overlapping bundle capacities
• IntegralFlowHomologousArcs: Integral flow with arc-pair equality constraints
• IntegralFlowWithMultipliers: Integral flow with vertex multipliers on a directed graph
• UndirectedFlowLowerBounds: Feasible s-t flow in an undirected graph with lower/upper bounds
• UndirectedTwoCommodityIntegralFlow: Two-commodity integral flow on undirected graphs
• StrongConnectivityAugmentation: Strong connectivity augmentation with weighted candidate arcs
• DisjointConnectingPaths: Vertex-disjoint paths connecting prescribed terminal pairs
• MinimumGraphBandwidth: Minimum graph bandwidth (minimize maximum edge stretch)

Structs

AcyclicPartition

Acyclic Partition (Garey & Johnson ND15).

BalancedCompleteBipartiteSubgraph

BicliqueCover

The Biclique Cover problem.

BiconnectivityAugmentation

The Biconnectivity Augmentation problem.

BottleneckTravelingSalesman

The Bottleneck Traveling Salesman problem on a simple weighted graph.

BoundedComponentSpanningForest

The Bounded Component Spanning Forest problem.

BoundedDiameterSpanningTree

Bounded Diameter Spanning Tree problem.

DegreeConstrainedSpanningTree

Degree-Constrained Spanning Tree problem.

DirectedHamiltonianPath

The Directed Hamiltonian Path problem.

DirectedTwoCommodityIntegralFlow

Directed Two-Commodity Integral Flow problem.

DisjointConnectingPaths

Disjoint Connecting Paths on an undirected graph.

GeneralizedHex

Generalized Hex on an undirected graph.

GraphPartitioning

The Graph Partitioning (Minimum Bisection) problem.

HamiltonianCircuit

The Hamiltonian Circuit problem.

HamiltonianPath

The Hamiltonian Path problem.

HamiltonianPathBetweenTwoVertices

The Hamiltonian Path Between Two Vertices problem.

IntegralFlowBundles

Integral Flow with Bundles (Garey & Johnson ND36).

IntegralFlowHomologousArcs

Integral flow with homologous arcs.

IntegralFlowWithMultipliers

IsomorphicSpanningTree

Isomorphic Spanning Tree problem.

KClique

The k-Clique decision problem.

KColoring

The Graph K-Coloring problem.

Kernel

The Kernel problem.

KthBestSpanningTree

Kth Best Spanning Tree.

LengthBoundedDisjointPaths

Length-Bounded Disjoint Paths on an undirected graph.

LongestCircuit

The Longest Circuit problem.

LongestPath

The Longest Path problem.

MaxCut

The Maximum Cut problem.

MaximalIS

The Maximal Independent Set problem.

MaximumAchromaticNumber

The Maximum Achromatic Number problem.

MaximumClique

The MaximumClique problem.

MaximumDomaticNumber

The Maximum Domatic Number problem.

MaximumIndependentSet

The Independent Set problem.

MaximumLeafSpanningTree

The Maximum Leaf Spanning Tree problem.

MaximumMatching

The Maximum Matching problem.

MinMaxMulticenter

The Min-Max Multicenter (vertex p-center) problem.

MinimumCapacitatedSpanningTree

The Minimum Capacitated Spanning Tree problem.

MinimumCoveringByCliques

The Minimum Covering by Cliques problem.

MinimumCutIntoBoundedSets

Minimum Cut Into Bounded Sets (Garey & Johnson ND17).

MinimumDominatingSet

The Dominating Set problem.

MinimumDummyActivitiesPert

Minimum Dummy Activities in PERT Networks.

MinimumEdgeCostFlow

Minimum Edge-Cost Flow problem.

MinimumFeedbackArcSet

The Minimum Feedback Arc Set problem.

MinimumFeedbackVertexSet

The Minimum Feedback Vertex Set problem.

MinimumGeometricConnectedDominatingSet

Minimum Geometric Connected Dominating Set.

MinimumGraphBandwidth

The Minimum Graph Bandwidth problem.

MinimumIntersectionGraphBasis

The Minimum Intersection Graph Basis problem.

MinimumMaximalMatching

The Minimum Maximal Matching problem.

MinimumMetricDimension

The Minimum Metric Dimension problem.

MinimumMultiwayCut

The Minimum Multiway Cut problem.

MinimumSumMulticenter

The Min-Sum Multicenter (p-median) problem.

MinimumVertexCover

The Vertex Covering problem.

MixedChinesePostman

Mixed Chinese Postman.

MonochromaticTriangle

The Monochromatic Triangle problem.

MultipleChoiceBranching

The Multiple Choice Branching problem.

MultipleCopyFileAllocation

Multiple Copy File Allocation problem.

OptimalLinearArrangement

The Optimal Linear Arrangement problem.

PartialFeedbackEdgeSet

The Partial Feedback Edge Set problem.

PartitionIntoCliques

The Partition Into Cliques problem.

PartitionIntoForests

The Partition Into Forests problem.

PartitionIntoPathsOfLength2

Partition into Paths of Length 2 problem.

PartitionIntoPerfectMatchings

The Partition Into Perfect Matchings problem.

PartitionIntoTriangles

The Partition Into Triangles problem.

PathConstrainedNetworkFlow

Path-Constrained Network Flow.

RootedTreeArrangement

RuralPostman

The Rural Postman problem.

ShortestWeightConstrainedPath

The Shortest Weight-Constrained Path problem.

SpinGlass

The Spin Glass (Ising model) problem.

SteinerTree

The Steiner Tree problem.

SteinerTreeInGraphs

The Steiner Tree in Graphs problem.

StrongConnectivityAugmentation

Strong Connectivity Augmentation.

SubgraphIsomorphism

The Subgraph Isomorphism problem.

TravelingSalesman

The Traveling Salesman problem.

UndirectedFlowLowerBounds

UndirectedTwoCommodityIntegralFlow

Undirected two-commodity integral flow on a capacitated graph.