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

problemreductions/models/graph/
mod.rs
