Write Model In Paper

MaximumIndependentSet in docs/paper/reductions.typ is the gold-standard model example. Search for problem-def("MaximumIndependentSet") to see the complete entry. Use it as a template for style, depth, and structure.

The problem-def Function

#problem-def("ProblemName")[
  Formal definition...          // parameter 1: def
][
  Background, example, figure...  // parameter 2: body
]

Three parameters:

• name (string) — problem name matching display-name dictionary key
• def (content) — formal mathematical definition
• body (content) — background, examples, figures, algorithm list

Auto-generated between def and body:

• Variant complexity table (from Rust declare_variants! metadata)
• Reduction links (from reduction graph JSON)
• Schema field table (from problem schema JSON)

Step 1: Register Display Name

Add to the display-name dictionary near the top of reductions.typ:

"ProblemName": [Display Name],

Step 2: Write the Formal Definition (def parameter)

One self-contained sentence or short paragraph. Requirements:

1. Introduce all inputs first — graph, weights, sets, variables with their domains
2. State the objective or constraint — what is being optimized or satisfied
3. Define all notation before use — every symbol must be introduced before it appears

Pattern for optimization problems

Given [inputs with domains], find [solution variable] [maximizing/minimizing] [objective] such that [constraints].

Pattern for satisfaction problems

Given [inputs with domains], find [solution variable] such that [constraints].

Example (MIS)

Given $G = (V, E)$ with vertex weights $w: V -> RR$, find $S subset.eq V$
maximizing $sum_(v in S) w(v)$ such that no two vertices in $S$ are