problemreductions/models/graph/
mod.rs

1//! Graph problems.
2//!
3//! Problems whose input is a graph (optionally weighted):
4//! - [`AcyclicPartition`]: Partition a digraph into bounded-weight groups with an acyclic quotient graph
5//! - [`BoundedDiameterSpanningTree`]: Spanning tree with bounded weight and diameter
6//! - [`DegreeConstrainedSpanningTree`]: Spanning tree with maximum vertex degree at most K
7//! - [`DirectedHamiltonianPath`]: Directed Hamiltonian path (decision problem)
8//! - [`MaximumIndependentSet`]: Maximum weight independent set
9//! - [`MaximumLeafSpanningTree`]: Spanning tree maximizing number of leaves
10//! - [`MaximalIS`]: Maximal independent set
11//! - [`MinimumVertexCover`]: Minimum weight vertex cover
12//! - [`MinimumCoveringByCliques`]: Minimum number of cliques covering all edges
13//! - [`MonochromaticTriangle`]: 2-color edges so that no triangle is monochromatic
14//! - [`MinimumIntersectionGraphBasis`]: Minimum universe size for intersection graph representation
15//! - [`MinimumCapacitatedSpanningTree`]: Minimum weight spanning tree with subtree capacity constraints
16//! - [`MinimumDominatingSet`]: Minimum dominating set
17//! - [`MinimumMetricDimension`]: Minimum resolving set (metric dimension)
18//! - [`MinimumEdgeCostFlow`]: Minimum edge-cost integral flow
19//! - [`MinimumGeometricConnectedDominatingSet`]: Minimum connected dominating set in a geometric point set
20//! - [`MinimumFeedbackVertexSet`]: Minimum weight feedback vertex set in a directed graph
21//! - [`MaximumClique`]: Maximum weight clique
22//! - [`MaximumAchromaticNumber`]: Maximum number of colors in a complete proper coloring
23//! - [`MaximumDomaticNumber`]: Maximum partition into disjoint dominating sets
24//! - [`MaxCut`]: Maximum cut on weighted graphs
25//! - [`MinimumCutIntoBoundedSets`]: Minimum cut into bounded sets (Garey & Johnson ND17)
26//! - [`MinimumDummyActivitiesPert`]: Minimum dummy activities in activity-on-arc PERT networks
27//! - [`HamiltonianCircuit`]: Hamiltonian circuit (decision problem)
28//! - [`IsomorphicSpanningTree`]: Isomorphic spanning tree (satisfaction)
29//! - [`Kernel`]: Kernel of a directed graph (independent and absorbing vertex subset)
30//! - [`KClique`]: Clique decision problem with threshold k
31//! - [`KthBestSpanningTree`]: K distinct bounded spanning trees (satisfaction)
32//! - [`KColoring`]: K-vertex coloring
33//! - [`PartitionIntoTriangles`]: Partition vertices into triangles
34//! - [`MaximumMatching`]: Maximum weight matching
35//! - [`MinimumMaximalMatching`]: Minimum-size maximal matching
36//! - [`TravelingSalesman`]: Traveling Salesman (minimum weight Hamiltonian cycle)
37//! - [`SpinGlass`]: Ising model Hamiltonian
38//! - [`MinimumMultiwayCut`]: Minimum weight multiway cut
39//! - [`HamiltonianPath`]: Hamiltonian path (simple path visiting every vertex)
40//! - [`HamiltonianPathBetweenTwoVertices`]: Hamiltonian path between two specified vertices (decision problem)
41//! - [`LongestPath`]: Maximum-length simple s-t path
42//! - [`ShortestWeightConstrainedPath`]: Bicriteria simple s-t path with length and weight bounds
43//! - [`PartitionIntoCliques`]: Partition vertices into K groups each inducing a clique
44//! - [`PartitionIntoForests`]: Partition vertices into K classes each inducing an acyclic subgraph
45//! - [`PartitionIntoPerfectMatchings`]: Partition vertices into K groups each inducing a perfect matching
46//! - [`PartitionIntoPathsOfLength2`]: Partition vertices into triples with at least two edges each
47//! - [`BicliqueCover`]: Biclique cover on bipartite graphs
48//! - [`SteinerTreeInGraphs`]: Minimum weight Steiner tree connecting terminal vertices
49//! - [`BalancedCompleteBipartiteSubgraph`]: Balanced biclique decision problem
50//! - [`BiconnectivityAugmentation`]: Biconnectivity augmentation with weighted potential edges
51//! - [`BoundedComponentSpanningForest`]: Partition vertices into bounded-weight connected components
52//! - [`BottleneckTravelingSalesman`]: Hamiltonian cycle minimizing the maximum selected edge weight
53//! - [`MultipleCopyFileAllocation`]: File-copy placement under storage and access costs
54//! - [`OptimalLinearArrangement`]: Optimal linear arrangement (total edge length at most K)
55//! - [`PartialFeedbackEdgeSet`]: Remove at most K edges to hit every short cycle
56//! - [`RootedTreeArrangement`]: Rooted-tree embedding with bounded total edge stretch
57//! - [`MinimumFeedbackArcSet`]: Minimum feedback arc set on directed graphs
58//! - [`MinMaxMulticenter`]: Min-max multicenter (vertex p-center, satisfaction)
59//! - [`MinimumSumMulticenter`]: Min-sum multicenter (p-median)
60//! - [`MultipleChoiceBranching`]: Directed branching with partition constraints
61//! - [`LengthBoundedDisjointPaths`]: Length-bounded internally disjoint s-t paths
62//! - [`PathConstrainedNetworkFlow`]: Integral flow on a prescribed collection of directed s-t paths
63//! - [`RuralPostman`]: Rural Postman (circuit covering required edges)
64//! - [`MixedChinesePostman`]: Mixed-graph postman tour with bounded total length
65//! - [`SteinerTree`]: Minimum-weight tree spanning all required terminals
66//! - [`SubgraphIsomorphism`]: Subgraph isomorphism (decision problem)
67//! - [`DirectedTwoCommodityIntegralFlow`]: Directed two-commodity integral flow (satisfaction)
68//! - [`IntegralFlowBundles`]: Integral flow feasibility with overlapping bundle capacities
69//! - [`IntegralFlowHomologousArcs`]: Integral flow with arc-pair equality constraints
70//! - [`IntegralFlowWithMultipliers`]: Integral flow with vertex multipliers on a directed graph
71//! - [`UndirectedFlowLowerBounds`]: Feasible s-t flow in an undirected graph with lower/upper bounds
72//! - [`UndirectedTwoCommodityIntegralFlow`]: Two-commodity integral flow on undirected graphs
73//! - [`StrongConnectivityAugmentation`]: Strong connectivity augmentation with weighted candidate arcs
74//! - [`DisjointConnectingPaths`]: Vertex-disjoint paths connecting prescribed terminal pairs
75//! - [`MinimumGraphBandwidth`]: Minimum graph bandwidth (minimize maximum edge stretch)
76
77pub(crate) mod acyclic_partition;
78pub(crate) mod balanced_complete_bipartite_subgraph;
79pub(crate) mod biclique_cover;
80pub(crate) mod biconnectivity_augmentation;
81pub(crate) mod bottleneck_traveling_salesman;
82pub(crate) mod bounded_component_spanning_forest;
83pub(crate) mod bounded_diameter_spanning_tree;
84pub(crate) mod degree_constrained_spanning_tree;
85pub(crate) mod directed_hamiltonian_path;
86pub(crate) mod directed_two_commodity_integral_flow;
87pub(crate) mod disjoint_connecting_paths;
88pub(crate) mod generalized_hex;
89pub(crate) mod graph_partitioning;
90pub(crate) mod hamiltonian_circuit;
91pub(crate) mod hamiltonian_path;
92pub(crate) mod hamiltonian_path_between_two_vertices;
93pub(crate) mod integral_flow_bundles;
94pub(crate) mod integral_flow_homologous_arcs;
95pub(crate) mod integral_flow_with_multipliers;
96pub(crate) mod isomorphic_spanning_tree;
97pub(crate) mod kclique;
98pub(crate) mod kcoloring;
99pub(crate) mod kernel;
100pub(crate) mod kth_best_spanning_tree;
101pub(crate) mod length_bounded_disjoint_paths;
102pub(crate) mod longest_circuit;
103pub(crate) mod longest_path;
104pub(crate) mod max_cut;
105pub(crate) mod maximal_is;
106pub(crate) mod maximum_achromatic_number;
107pub(crate) mod maximum_clique;
108pub(crate) mod maximum_domatic_number;
109pub(crate) mod maximum_independent_set;
110pub(crate) mod maximum_leaf_spanning_tree;
111pub(crate) mod maximum_matching;
112pub(crate) mod min_max_multicenter;
113pub(crate) mod minimum_capacitated_spanning_tree;
114pub(crate) mod minimum_covering_by_cliques;
115pub(crate) mod minimum_cut_into_bounded_sets;
116pub(crate) mod minimum_dominating_set;
117pub(crate) mod minimum_dummy_activities_pert;
118pub(crate) mod minimum_edge_cost_flow;
119pub(crate) mod minimum_feedback_arc_set;
120pub(crate) mod minimum_feedback_vertex_set;
121pub(crate) mod minimum_geometric_connected_dominating_set;
122pub(crate) mod minimum_graph_bandwidth;
123pub(crate) mod minimum_intersection_graph_basis;
124pub(crate) mod minimum_maximal_matching;
125pub(crate) mod minimum_metric_dimension;
126pub(crate) mod minimum_multiway_cut;
127pub(crate) mod minimum_sum_multicenter;
128pub(crate) mod minimum_vertex_cover;
129pub(crate) mod mixed_chinese_postman;
130pub(crate) mod monochromatic_triangle;
131pub(crate) mod multiple_choice_branching;
132pub(crate) mod multiple_copy_file_allocation;
133pub(crate) mod optimal_linear_arrangement;
134pub(crate) mod partial_feedback_edge_set;
135pub(crate) mod partition_into_cliques;
136pub(crate) mod partition_into_forests;
137pub(crate) mod partition_into_paths_of_length_2;
138pub(crate) mod partition_into_perfect_matchings;
139pub(crate) mod partition_into_triangles;
140pub(crate) mod path_constrained_network_flow;
141pub(crate) mod rooted_tree_arrangement;
142pub(crate) mod rural_postman;
143pub(crate) mod shortest_weight_constrained_path;
144pub(crate) mod spin_glass;
145pub(crate) mod steiner_tree;
146pub(crate) mod steiner_tree_in_graphs;
147pub(crate) mod strong_connectivity_augmentation;
148pub(crate) mod subgraph_isomorphism;
149pub(crate) mod traveling_salesman;
150pub(crate) mod undirected_flow_lower_bounds;
151pub(crate) mod undirected_two_commodity_integral_flow;
152pub use acyclic_partition::AcyclicPartition;
153pub use balanced_complete_bipartite_subgraph::BalancedCompleteBipartiteSubgraph;
154pub use biclique_cover::BicliqueCover;
155pub use biconnectivity_augmentation::BiconnectivityAugmentation;
156pub use bottleneck_traveling_salesman::BottleneckTravelingSalesman;
157pub use bounded_component_spanning_forest::BoundedComponentSpanningForest;
158pub use bounded_diameter_spanning_tree::BoundedDiameterSpanningTree;
159pub use degree_constrained_spanning_tree::DegreeConstrainedSpanningTree;
160pub use directed_hamiltonian_path::DirectedHamiltonianPath;
161pub use directed_two_commodity_integral_flow::DirectedTwoCommodityIntegralFlow;
162pub use disjoint_connecting_paths::DisjointConnectingPaths;
163pub use generalized_hex::GeneralizedHex;
164pub use graph_partitioning::GraphPartitioning;
165pub use hamiltonian_circuit::HamiltonianCircuit;
166pub use hamiltonian_path::HamiltonianPath;
167pub use hamiltonian_path_between_two_vertices::HamiltonianPathBetweenTwoVertices;
168pub use integral_flow_bundles::IntegralFlowBundles;
169pub use integral_flow_homologous_arcs::IntegralFlowHomologousArcs;
170pub use integral_flow_with_multipliers::IntegralFlowWithMultipliers;
171pub use isomorphic_spanning_tree::IsomorphicSpanningTree;
172pub use kclique::KClique;
173pub use kcoloring::KColoring;
174pub use kernel::Kernel;
175pub use kth_best_spanning_tree::KthBestSpanningTree;
176pub use length_bounded_disjoint_paths::LengthBoundedDisjointPaths;
177pub use longest_circuit::LongestCircuit;
178pub use longest_path::LongestPath;
179pub use max_cut::MaxCut;
180pub use maximal_is::MaximalIS;
181pub use maximum_achromatic_number::MaximumAchromaticNumber;
182pub use maximum_clique::MaximumClique;
183pub use maximum_domatic_number::MaximumDomaticNumber;
184pub use maximum_independent_set::MaximumIndependentSet;
185pub use maximum_leaf_spanning_tree::MaximumLeafSpanningTree;
186pub use maximum_matching::MaximumMatching;
187pub use min_max_multicenter::MinMaxMulticenter;
188pub use minimum_capacitated_spanning_tree::MinimumCapacitatedSpanningTree;
189pub use minimum_covering_by_cliques::MinimumCoveringByCliques;
190pub use minimum_cut_into_bounded_sets::MinimumCutIntoBoundedSets;
191pub use minimum_dominating_set::MinimumDominatingSet;
192pub use minimum_dummy_activities_pert::MinimumDummyActivitiesPert;
193pub use minimum_edge_cost_flow::MinimumEdgeCostFlow;
194pub use minimum_feedback_arc_set::MinimumFeedbackArcSet;
195pub use minimum_feedback_vertex_set::MinimumFeedbackVertexSet;
196pub use minimum_geometric_connected_dominating_set::MinimumGeometricConnectedDominatingSet;
197pub use minimum_graph_bandwidth::MinimumGraphBandwidth;
198pub use minimum_intersection_graph_basis::MinimumIntersectionGraphBasis;
199pub use minimum_maximal_matching::MinimumMaximalMatching;
200pub use minimum_metric_dimension::MinimumMetricDimension;
201pub use minimum_multiway_cut::MinimumMultiwayCut;
202pub use minimum_sum_multicenter::MinimumSumMulticenter;
203pub use minimum_vertex_cover::MinimumVertexCover;
204pub use mixed_chinese_postman::MixedChinesePostman;
205pub use monochromatic_triangle::MonochromaticTriangle;
206pub use multiple_choice_branching::MultipleChoiceBranching;
207pub use multiple_copy_file_allocation::MultipleCopyFileAllocation;
208pub use optimal_linear_arrangement::OptimalLinearArrangement;
209pub use partial_feedback_edge_set::PartialFeedbackEdgeSet;
210pub use partition_into_cliques::PartitionIntoCliques;
211pub use partition_into_forests::PartitionIntoForests;
212pub use partition_into_paths_of_length_2::PartitionIntoPathsOfLength2;
213pub use partition_into_perfect_matchings::PartitionIntoPerfectMatchings;
214pub use partition_into_triangles::PartitionIntoTriangles;
215pub use path_constrained_network_flow::PathConstrainedNetworkFlow;
216pub use rooted_tree_arrangement::RootedTreeArrangement;
217pub use rural_postman::RuralPostman;
218pub use shortest_weight_constrained_path::ShortestWeightConstrainedPath;
219pub use spin_glass::SpinGlass;
220pub use steiner_tree::SteinerTree;
221pub use steiner_tree_in_graphs::SteinerTreeInGraphs;
222pub use strong_connectivity_augmentation::StrongConnectivityAugmentation;
223pub use subgraph_isomorphism::SubgraphIsomorphism;
224pub use traveling_salesman::TravelingSalesman;
225pub use undirected_flow_lower_bounds::UndirectedFlowLowerBounds;
226pub use undirected_two_commodity_integral_flow::UndirectedTwoCommodityIntegralFlow;
227#[cfg(feature = "example-db")]
228pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
229    let mut specs = Vec::new();
230    specs.extend(acyclic_partition::canonical_model_example_specs());
231    specs.extend(bounded_diameter_spanning_tree::canonical_model_example_specs());
232    specs.extend(degree_constrained_spanning_tree::canonical_model_example_specs());
233    specs.extend(directed_hamiltonian_path::canonical_model_example_specs());
234    specs.extend(maximum_independent_set::canonical_model_example_specs());
235    specs.extend(maximum_leaf_spanning_tree::canonical_model_example_specs());
236    specs.extend(minimum_vertex_cover::canonical_model_example_specs());
237    specs.extend(minimum_vertex_cover::decision_canonical_model_example_specs());
238    specs.extend(max_cut::canonical_model_example_specs());
239    specs.extend(generalized_hex::canonical_model_example_specs());
240    specs.extend(hamiltonian_circuit::canonical_model_example_specs());
241    specs.extend(hamiltonian_path::canonical_model_example_specs());
242    specs.extend(hamiltonian_path_between_two_vertices::canonical_model_example_specs());
243    specs.extend(integral_flow_bundles::canonical_model_example_specs());
244    specs.extend(integral_flow_with_multipliers::canonical_model_example_specs());
245    specs.extend(isomorphic_spanning_tree::canonical_model_example_specs());
246    specs.extend(kclique::canonical_model_example_specs());
247    specs.extend(kernel::canonical_model_example_specs());
248    specs.extend(kcoloring::canonical_model_example_specs());
249    specs.extend(kth_best_spanning_tree::canonical_model_example_specs());
250    specs.extend(length_bounded_disjoint_paths::canonical_model_example_specs());
251    specs.extend(longest_circuit::canonical_model_example_specs());
252    specs.extend(longest_path::canonical_model_example_specs());
253    specs.extend(minimum_covering_by_cliques::canonical_model_example_specs());
254    specs.extend(monochromatic_triangle::canonical_model_example_specs());
255    specs.extend(minimum_intersection_graph_basis::canonical_model_example_specs());
256    specs.extend(minimum_dominating_set::canonical_model_example_specs());
257    specs.extend(minimum_dominating_set::decision_canonical_model_example_specs());
258    specs.extend(minimum_metric_dimension::canonical_model_example_specs());
259    specs.extend(minimum_geometric_connected_dominating_set::canonical_model_example_specs());
260    specs.extend(maximum_matching::canonical_model_example_specs());
261    specs.extend(minimum_maximal_matching::canonical_model_example_specs());
262    specs.extend(traveling_salesman::canonical_model_example_specs());
263    specs.extend(maximum_achromatic_number::canonical_model_example_specs());
264    specs.extend(maximum_domatic_number::canonical_model_example_specs());
265    specs.extend(maximum_clique::canonical_model_example_specs());
266    specs.extend(maximal_is::canonical_model_example_specs());
267    specs.extend(minimum_cut_into_bounded_sets::canonical_model_example_specs());
268    specs.extend(minimum_dummy_activities_pert::canonical_model_example_specs());
269    specs.extend(multiple_copy_file_allocation::canonical_model_example_specs());
270    specs.extend(minimum_feedback_vertex_set::canonical_model_example_specs());
271    specs.extend(min_max_multicenter::canonical_model_example_specs());
272    specs.extend(minimum_multiway_cut::canonical_model_example_specs());
273    specs.extend(minimum_sum_multicenter::canonical_model_example_specs());
274    specs.extend(shortest_weight_constrained_path::canonical_model_example_specs());
275    specs.extend(multiple_choice_branching::canonical_model_example_specs());
276    specs.extend(spin_glass::canonical_model_example_specs());
277    specs.extend(biclique_cover::canonical_model_example_specs());
278    specs.extend(balanced_complete_bipartite_subgraph::canonical_model_example_specs());
279    specs.extend(biconnectivity_augmentation::canonical_model_example_specs());
280    specs.extend(bottleneck_traveling_salesman::canonical_model_example_specs());
281    specs.extend(bounded_component_spanning_forest::canonical_model_example_specs());
282    specs.extend(partition_into_triangles::canonical_model_example_specs());
283    specs.extend(partition_into_cliques::canonical_model_example_specs());
284    specs.extend(partition_into_forests::canonical_model_example_specs());
285    specs.extend(partition_into_perfect_matchings::canonical_model_example_specs());
286    specs.extend(partition_into_paths_of_length_2::canonical_model_example_specs());
287    specs.extend(path_constrained_network_flow::canonical_model_example_specs());
288    specs.extend(rooted_tree_arrangement::canonical_model_example_specs());
289    specs.extend(steiner_tree::canonical_model_example_specs());
290    specs.extend(steiner_tree_in_graphs::canonical_model_example_specs());
291    specs.extend(directed_two_commodity_integral_flow::canonical_model_example_specs());
292    specs.extend(disjoint_connecting_paths::canonical_model_example_specs());
293    specs.extend(undirected_flow_lower_bounds::canonical_model_example_specs());
294    specs.extend(undirected_two_commodity_integral_flow::canonical_model_example_specs());
295    specs.extend(strong_connectivity_augmentation::canonical_model_example_specs());
296    specs.extend(rural_postman::canonical_model_example_specs());
297    specs.extend(integral_flow_homologous_arcs::canonical_model_example_specs());
298    specs.extend(minimum_capacitated_spanning_tree::canonical_model_example_specs());
299    specs.extend(minimum_edge_cost_flow::canonical_model_example_specs());
300    specs.extend(minimum_graph_bandwidth::canonical_model_example_specs());
301    specs.extend(minimum_feedback_arc_set::canonical_model_example_specs());
302    specs.extend(optimal_linear_arrangement::canonical_model_example_specs());
303    specs.extend(partial_feedback_edge_set::canonical_model_example_specs());
304    specs.extend(mixed_chinese_postman::canonical_model_example_specs());
305    specs.extend(subgraph_isomorphism::canonical_model_example_specs());
306    specs.extend(graph_partitioning::canonical_model_example_specs());
307    specs
308}
problemreductions/models/graph/mod.rs

problemreductions/models/graph/
mod.rs
