Repository navigation
[Model] MultipleChoiceBranching #253
Description
name: Problem
about: Propose a new problem type
title: "[Model] MultipleChoiceBranching"
labels: model
assignees: ''
Motivation
MULTIPLE CHOICE BRANCHING from Garey & Johnson, A2 ND11. An NP-complete problem on directed graphs combining branching (arborescence) structure with partition constraints on arcs. The problem asks for a high-weight subset of arcs that forms an acyclic, in-degree-at-most-one subgraph (a branching/forest of arborescences) while respecting a partition constraint that at most one arc from each group is selected. Without the partition constraint, the problem reduces to maximum weight branching — a 2-matroid intersection problem solvable in polynomial time (Tarjan, 1977).
Associated reduction rules:
- As target: R32 (3SAT -> MULTIPLE CHOICE BRANCHING) via Garey and Johnson (unpublished)
Definition
Name: MultipleChoiceBranching
Canonical name: MULTIPLE CHOICE BRANCHING
Reference: Garey & Johnson, Computers and Intractability, A2 ND11
Mathematical definition:
INSTANCE: Directed graph G = (V, A), a weight w(a) in Z^+ for each arc a in A, a partition of A into disjoint sets A_1, A_2, ..., A_m, and a positive integer K.
QUESTION: Is there a subset A' of A with sum_{a in A'} w(a) >= K such that no two arcs in A' enter the same vertex, A' contains no cycles, and A' contains at most one arc from each of the A_i, 1 <= i <= m?
Variables
- Count: |A| binary variables (one per arc), indicating whether the arc is selected
- Per-variable domain: {0, 1} — 0 means arc not selected, 1 means arc selected
dims():vec![2; graph.num_arcs()]- Meaning: Variable x_a = 1 means arc a is included in the subset A'. The constraints are: (1) for each vertex v, at most one arc entering v has x_a = 1 (in-degree constraint), (2) the selected arcs form an acyclic subgraph (no directed cycle), (3) for each partition group A_i, at most one arc has x_a = 1 (multiple choice constraint), and (4) the total weight of selected arcs is at least K.
Schema (data type)
Type name: MultipleChoiceBranching
Variants: weight type (W)
| Field | Type | Description |
|---|---|---|
graph |
DirectedGraph |
Directed graph G = (V, A) |
weights |
Vec<W> |
Positive integer weight w(a) for each arc a |
partition |
Vec<Vec<usize>> |
Partition of arcs into disjoint groups A_1, ..., A_m. Each inner Vec<usize> contains 0-based indices into the arcs. The groups must be pairwise disjoint and their union must cover all arcs (i.e., every arc index in 0..graph.num_arcs() appears in exactly one group). |
threshold |
W |
Weight threshold K |
Size fields (for overhead expressions): num_vertices (from graph.num_vertices()), num_arcs (from graph.num_arcs()), num_partition_groups (from partition.len())
Notes:
- This is a satisfaction (decision) problem:
Metric = bool, implementingSatisfactionProblem. - The "no two arcs enter the same vertex" and "no cycles" constraints together define a branching (a forest of in-arborescences).
- The partition constraint adds the "multiple choice" aspect on top of the branching structure.
- Let m =
partition.len()denote the number of partition groups. The partition must be disjoint and cover all arcs. DirectedGraphis defined insrc/topology/directed_graph.rs, wrapping petgraph'sDiGraph<(), ()>. It providesnum_vertices(),num_arcs(),arcs(),is_dag(). Usevariant_params since there is no generic graph type parameter.
Complexity
- Best known exact algorithm: Brute-force enumeration over all 2^|A| subsets of arcs, checking branching + partition + weight constraints for each.
declare_variants!complexity string:"2^num_arcs"(brute-force over all arc subsets)- NP-completeness: NP-complete (Garey and Johnson, unpublished). Transformation from 3SAT. Remains NP-complete even if G is strongly connected and all weights are equal.
- Polynomial special cases:
- If all A_i have |A_i| = 1 (no choice constraint), the problem becomes maximum weight branching, solvable in polynomial time via 2-matroid intersection (Tarjan, 1977; Edmonds, 1967).
- If the graph is symmetric, the problem reduces to the "multiple choice spanning tree" problem, also a 2-matroid intersection problem solvable in polynomial time (Suurballe, 1975, as referenced in Garey & Johnson, 1979; exact publication venue unverified).
- References:
- R. E. Tarjan (1977). "Finding optimum branchings." Networks 7, pp. 25--35.
- J. W. Suurballe (1975). "Minimal spanning trees subject to disjoint arc set constraints." (as referenced in Garey & Johnson, 1979; exact publication venue unverified)
- J. Edmonds (1967). "Optimum branchings." Journal of Research of the National Bureau of Standards 71B, pp. 233--240.
Extra Remark
Full book text:
INSTANCE: Directed graph G = (V,A), a weight w(a) in Z^+ for each arc a in A, a partition of A into disjoint sets A_1, A_2, ..., A_m, and a positive integer K.
QUESTION: Is there a subset A' in A with sum_{a in A'} w(a) >= K such that no two arcs in A' enter the same vertex, A' contains no cycles, and A' contains at most one arc from each of the A_i, 1 <= i <= m?
Reference: [Garey and Johnson, --]. Transformation from 3SAT.
Comment: Remains NP-complete even if G is strongly connected and all weights are equal. If all Ai have |Ai| = 1, the problem becomes simply that of finding a "maximum weight branching," a 2-matroid intersection problem that can be solved in polynomial time (e.g., see [Tarjan, 1977]). (In a strongly connected graph, a maximum weight branching can be viewed as a maximum weight directed spanning tree.) Similarly, if the graph is symmetric, the problem becomes equivalent to the "multiple choice spanning tree" problem, another 2-matroid intersection problem that can be solved in polynomial time [Suurballe, 1975].
How to solve
- It can be solved by (existing) bruteforce — enumerate all subsets of arcs (at most one per partition group) and check branching + weight constraints.
- It can be solved by reducing to integer programming — binary variables for each arc, constraints for in-degree, acyclicity (via ordering variables), partition groups, and weight threshold.
- Other: For the special case without partition constraints, Edmonds' algorithm (maximum weight branching) runs in O(|V| * |A|) time.
Example Instance
Instance 1 (YES — valid branching exists):
Directed graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 8 arcs:
- Arcs with weights: a0=(0->1, w=3), a1=(0->2, w=2), a2=(1->3, w=4), a3=(2->3, w=1), a4=(1->4, w=2), a5=(3->5, w=3), a6=(4->5, w=1), a7=(2->4, w=3)
- Partition: A_1 = {a0, a1} (arcs from vertex 0), A_2 = {a2, a3} (arcs to vertex 3), A_3 = {a4, a7} (arcs to vertex 4), A_4 = {a5, a6} (arcs to vertex 5)
- K = 10
- Solution: A' = {a0, a2, a7, a5} = {0->1 (w=3), 1->3 (w=4), 2->4 (w=3), 3->5 (w=3)}
- Total weight = 3+4+3+3 = 13 >= K=10
- In-degree check: vertex 1 entered by a0 only, vertex 3 by a2 only, vertex 4 by a7 only, vertex 5 by a5 only -- OK
- Acyclicity: 0->1->3->5 and 2->4, no cycles -- OK
- Partition: a0 from A_1, a2 from A_2, a7 from A_3, a5 from A_4 -- at most one per group -- OK
- Answer: YES
Instance 2 (NO — no valid branching meets threshold):
Directed graph G with 4 vertices {0, 1, 2, 3} and 4 arcs:
- Arcs with weights: a0=(0->1, w=2), a1=(1->2, w=2), a2=(2->3, w=2), a3=(3->1, w=2)
- Partition: A_1 = {a0, a3} (arcs entering vertex 1), A_2 = {a1, a2}
- K = 6
- From A_1, select at most one: a0 or a3. From A_2, select at most one: a1 or a2.
- Best acyclic branching: a0 + a1 (weight 4), or a0 + a2 (but a2=2->3, need path from 0 through something), or a3 + a2 (but 3->1 and 2->3 form a cycle if both selected... actually no: a3=3->1, a2=2->3. Selected arcs: 3->1 and 2->3. Check cycle: 2->3->1, no cycle back to 2.)
- Max weight achievable = 4 < K=6
- Answer: NO
Activity
zazabap commentedon Mar 11, 2026
Issue Quality Check — Model
Overall: 2 passed, 0 failed, 2 warnings
Usefulness
Pass.
MultipleChoiceBranchingdoes not exist in the codebase (confirmed viapred show). The problem is from Garey & Johnson's compendium (A2, ND11) and combines branching structure with partition constraints — a genuinely novel input structure for this reduction graph. The issue mentions an associated reduction from 3SAT (R32, Garey and Johnson unpublished), which would connect it to the existingKSatisfiabilitynode.One minor note: the Motivation section would benefit from explicitly naming which implemented problems this would connect to (e.g., "enables reduction from
KSatisfiability") rather than referencing the abstract "3SAT -> MULTIPLE CHOICE BRANCHING" rule.Non-trivial
Pass. This is a directed graph problem with three simultaneous constraints: (1) in-degree at most one (branching structure), (2) acyclicity, and (3) at most one arc per partition group. No existing problem in the codebase combines these constraints. The closest problems are on undirected graphs (MIS, MaxCut, etc.), formulas (SAT), sets, or algebraic structures. This is genuinely distinct.
Correctness
Warn — two items could not be fully verified.
Verified references:
Unverified references:
Complexity section gap:
The issue does not provide a concrete best-known exact algorithm time bound (e.g.,
"2^num_arcs"or similar). Thedeclare_variants!macro requires a complexity string with concrete numeric values. The current description ("general case requires exponential time") is too vague for implementation. A brute-force bound ofO(product of |A_i|)is mentioned but not formalized into a complexity expression.Well-written
Warn — mostly good, with minor items to address.
Strengths:
Items to address:
declare_variants!macro needs a concrete expression like"2^num_arcs". Please add a specific worst-case time bound.partitionfield: The typeVec<Vec<usize>>stores arc indices, but it should be clarified whether indices are 0-based and correspond to the order in thearcsvector. Also, the invariant that partition groups are disjoint and cover all arcs should be noted.m: Used in the definition ("A_1, A_2, ..., A_m") and partition description but not formally defined as the number of partition groups. Consider adding "let m = |partition|" for consistency.MultipleChoiceBranchingis acceptable for a satisfaction problem (no Maximum/Minimum prefix needed). ✅Recommendations
"2^num_arcs"(brute force over all arc subsets). If the partition structure can be exploited, a tighter bound referencing partition group sizes could be used, but the simpler expression is safer for implementation.thresholdfield in the schema makes this a decision problem, which is correct. However, consider whether an optimization variant (maximize total weight subject to branching + partition constraints) would also be useful — it could be added as a separate model later.isPANN commentedon Mar 13, 2026
Changelog — mechanical fixes applied:
partitionfield: Expanded description to explicitly state that inner vectors contain 0-based indices into thearcsvector, groups must be pairwise disjoint, and their union must cover all arcs (every index in0..arcs.len()appears in exactly one group).isPANN commentedon Mar 13, 2026
Changelog (fix-issue-batch, 2026-03-13)
num_vertices+arcsfields with singlegraph: DirectedGraphfield —DirectedGraph(insrc/topology/directed_graph.rs) wraps petgraph'sDiGraph<(), ()>, providesnum_vertices(),num_arcs(),arcs(),is_dag().graph:num_vertices(fromgraph.num_vertices()),num_arcs(fromgraph.num_arcs()),num_partition_groups(frompartition.len()).dims()to usegraph.num_arcs().DirectedGraphtype andvariant_params![].Add plan for #253: [Model] MultipleChoiceBranching
Implement #253: [Model] MultipleChoiceBranching
Fix #253: [Model] MultipleChoiceBranching (#656)