Six places teams reach for the wrong category

The six traps that cause teams to size a sprint as a quarter. Read them; recognize the patterns; redirect the work.

Six recurring misidentifications. Treating shortest-path-with-positive-costs as hard because the network is large — Dijkstra handles millions of nodes. Treating matching" data-term="bipartite matching">bipartite matching as hard because the count is large — Hopcroft-Karp handles tens of thousands per second. Treating linear programming as hard because there are many variables — HiGHS handles millions. Treating two-piece constraint problems as SAT problems — they are linear-time via graph methods. Treating problems on DAGs as if cycles were possible — the acyclic structure collapses many NP-hard problems to polynomial. Treating problems with matroid structure as needing search when greedy is provably optimal. In every case the fix is the same: name the structural property, look up the named algorithm, find the Rust crate. See page 37 for the checklist and page 38 for the lookalikes.

A detector that flags an estimate against the six recurring traps. Run it on the planning doc. Every true is a sprint that has probably been quoted as a quarter.

struct Estimate {
    description: String,
    proposed_tool: &'static str,
    has_positive_weights_only: bool,
    is_two_sided_matching: bool,
    has_only_continuous_vars: bool,
    every_constraint_has_two_vars: bool,
    data_is_dag: bool,
    has_matroid_structure: bool,
}

fn wrong_category(e: &Estimate) -> Vec<&'static str> {
    let mut flags = Vec::new();
    if e.has_positive_weights_only && !e.proposed_tool.contains("dijkstra") {
        flags.push("shortest path with positive weights — use Dijkstra, not SAT");
    }
    if e.is_two_sided_matching && e.proposed_tool.contains("ILP") {
        flags.push("two-sided matching — Hopcroft-Karp or Hungarian, not ILP");
    }
    if e.has_only_continuous_vars && e.proposed_tool.contains("search") {
        flags.push("continuous LP — model in good_lp, don't search");
    }
    if e.every_constraint_has_two_vars && e.proposed_tool.contains("SAT") {
        flags.push("2-SAT — implication graph + SCC, not CDCL");
    }
    if e.data_is_dag && e.proposed_tool.contains("heuristic") {
        flags.push("DAG — toposort + DP, not heuristic search");
    }
    if e.has_matroid_structure && e.proposed_tool.contains("ILP") {
        flags.push("matroid — greedy is provably optimal");
    }
    flags
}

struct is Rust's record type — a single value with several named fields, each with its own type. This page's Estimate bundles a description, the proposed tool, and six boolean flags into one passable thing. Constructed with struct literal syntax: Estimate { name: value, ... } (field name on the left, value on the right). Fields are read or written with . notation — e.proposed_tool, e.data_is_dag. Functions take structs by reference (&Estimate) to inspect without consuming, by mutable reference (&mut Estimate) to update in place, or by value (Estimate) to take ownership. Compared to a tuple, the field names document what each piece means — e.is_two_sided_matching reads better than e.3.

// Declaration — named fields, each with its own type.
struct Estimate {
    description:                   String,        // owns the text
    proposed_tool:                 &'static str,  // borrowed literal
    has_positive_weights_only:     bool,
    is_two_sided_matching:         bool,
    has_only_continuous_vars:      bool,
    every_constraint_has_two_vars: bool,
    data_is_dag:                   bool,
    has_matroid_structure:         bool,
}


// Construction — struct literal syntax with named fields:
let e = Estimate {
    description:                   String::from("Match drivers to deliveries"),
    proposed_tool:                 "writing a SAT solver",
    has_positive_weights_only:     false,
    is_two_sided_matching:         true,
    has_only_continuous_vars:      false,
    every_constraint_has_two_vars: false,
    data_is_dag:                   false,
    has_matroid_structure:         false,
};


// Field access with .
let tool = e.proposed_tool;
let bipartite = e.is_two_sided_matching;


// Pass by reference for read-only inspection — page 39's signature:
fn wrong_category(e: &Estimate) -> Vec<&'static str> { /* ... */ }
let flags = wrong_category(&e);


// Pass by mutable reference to update in place:
fn mark_as_dag(e: &mut Estimate) {
    e.data_is_dag = true;
}


// Two ergonomic shorthands worth knowing:

// 1. Field init shorthand — when a variable matches a field name,
//    you can omit the colon and value:
let description = String::from("...");
let proposed_tool = "dijkstra";
let e = Estimate {
    description,                       // shorthand for description: description
    proposed_tool,                     // shorthand for proposed_tool: proposed_tool
    has_positive_weights_only: true,
    is_two_sided_matching: false,
    has_only_continuous_vars: false,
    every_constraint_has_two_vars: false,
    data_is_dag: false,
    has_matroid_structure: false,
};

// 2. Struct-update syntax — copy any missing fields from another value:
let e2 = Estimate {
    description: String::from("revised"),
    ..e                                // every other field copied from e
};


// Three flavors of struct, briefly:
//
//   struct Foo { x: i32, y: i32 }     named fields    ← the common case
//   struct Bar(i32, i32);              tuple struct   ← positional access (.0, .1)
//   struct Baz;                         unit struct    ← no fields, type-level marker
//
// Unit structs are surprisingly useful for type-level state machines
// and zero-sized markers.

In plain terms

This page is the mirror — the six places where, in your team's planning meetings, the wrong category has probably been chosen.

Mistake one: big input means hard. No. Input size is one parameter. A shortest-path query over a network of ten million points is still Dijkstra, still a millisecond per query with the right data structure. Reach for SAT or heuristics only when the structure is genuinely combinatorial — not when the problem is just big.

Mistake two: matching looks like assignment looks like ILP. Yes, the assignment problem can be modeled as ILP. No, you do not need ILP. Bipartite matching is Hopcroft-Karp for unweighted and the Hungarian algorithm for weighted, both polynomial, both one library call in Rust's pathfinding.

Mistake three: linear programming sounds expensive. It is not. HiGHS solves LPs with millions of variables in seconds. When your problem has linear constraints and a linear objective with continuous variables, model it and dispatch. Do not search the solution space yourself.

Mistake four: implication constraints look like SAT. When every constraint has the form "if X then Y" with two variables, you are in the 2-SAT category and the answer is linear time via strongly connected components on the implication graph. Do not encode in CNF and call a SAT solver for what petgraph solves in fifty lines.

Mistake five: cycles complicate everything. When your data is a DAG — build dependencies, workflow steps, version histories — many NP-hard problems collapse to polynomial dynamic programming on the topological order. Confirm the acyclicity, then do the DP.

Mistake six: greedy is a hack. When the underlying structure is a matroid — forests in a graph, bipartite transversals, linearly independent vectors — greedy is provably optimal. Sort, pick, verify the matroid property. No search needed. MST is the textbook example.

The common thread across all six mistakes is the same. The structural property of the problem determines the category, and the category determines the tool. Name the property and the tool declares itself. The crates are listed in the Part II pages.

This book exists to make this reflex automatic in planning meetings. Page 37 is the checklist for "is this in the cheap category." Page 38 is the lookalikes that fool experienced teams. This page is the mirror — what your team has probably been doing wrong, in case any of it sounds familiar.

Now do less.