Skip to main content

Graph Problem Recognition

What This Concept Is​

Modeling is a reduction, not a keyword match. Specify what each feasible original solution becomes in the graph and how to translate a graph answer back. Prove both feasibility and objective preservation. Similar-looking graphs can optimize different quantities: total connecting cost, root-to-target distance, maximum throughput, or the number of compatible assignments.

Why It Matters Here​

A perfectly implemented algorithm cannot repair a reduction that omitted a constraint. Basic maximum matching does not solve preference stability, weighted assignment or arbitrary workforce scheduling. An MST does not model redundancy requirements; its edges are all bridges within the tree.

Concrete Examples​

For build tasks, choose edge prerequisite→dependent. A topological order lists prerequisites first. If source data instead records dependent→prerequisite, reverse those records or reverse the interpretation consistently. A valid order does not determine minimum completion time when task durations and worker limits matter.

For unit-capacity worker/job assignment, vertices are workers and jobs, edges are allowed assignments, and a matching enforces at most one job per worker and one worker per job. If workers can take two jobs, the unit matching model no longer preserves feasible solutions; change capacities and extraction semantics.

Common Confusion / Misconceptions​

There is no universal list of seven graph problems that covers every problem. Recognition is a hypothesis to test. Reliability probabilities may multiply, latencies may depend on departure time, and capacities describe simultaneous throughput rather than additive route cost.

How To Use It​

Write a small example with a hand-checked answer and one changed assumption that breaks the proposed reduction. Identify graph-size growth: adding a state for each remaining fuel level can multiply V. Include construction and answer decoding costs in the overall analysis.

Check Yourself​

  1. Which two directions establish a reduction's correctness?
  2. Why is a feasible task order not a full scheduling solution?
  3. Which constraint changes when a worker may take two jobs?
  4. Why does an MST not guarantee fault tolerance?

Mini Drill or Application​

Model dependency validation, cheapest additive routing, lowest-cost connection, and unit worker/job assignment. For each, state one missing fact that would prevent selecting an algorithm. Do not force a reduction when the objective is underspecified. See P4 and the capstone.

Read This Only If Stuck​

Find graph modeling, reductions, and objective preservation in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.