Focused Practice for Maximum Flow and NP-Completeness
Format: Matches Quiz 5 structure exactly
Total Points: 100 points
Note: This practice quiz mirrors the actual Quiz 5 format. Questions focus on max flow residual graphs, Ford-Fulkerson vs Edmonds-Karp paths, reduction logic, bipartite graphs, and NP-completeness. Answers limited to 20 words for theory questions.
Consider the following flow network G. Vertices are labeled by single letters. Edges are labeled with flow/capacity notation.
Note: Edges are processed in alphabetical order. No algorithm will traverse the same edge twice.
Determine edge weights for the residual graph GR using the standard residual graph algorithm. Write your answers in the table below. The second row with R edges (saR, sbR, etc.) are for flow in the reverse direction. List only the flow (single integer), not capacity.
| sa | sb | ac | ad | bc | bd | ce | de | et |
|---|---|---|---|---|---|---|---|---|
| saR | sbR | acR | adR | bcR | bdR | ceR | deR | etR |
Using the residual graph GR from Question 1, evaluate each potential path and classify it:
Classification Options:
Remember: We're asking about augmenting paths in GR, not all possible paths in G!
| Path | A | B | C | D | E |
|---|---|---|---|---|---|
| s → a → c → e → t | ○ | ○ | ○ | ○ | ○ |
| s → b → d → e → t | ○ | ○ | ○ | ○ | ○ |
| s → a → d → e → t | ○ | ○ | ○ | ○ | ○ |
| s → b → c → e → t | ○ | ○ | ○ | ○ | ○ |
| s → a → c → eR → d → et | ○ | ○ | ○ | ○ | ○ |
| s → b → bdR → ac → ce → t | ○ | ○ | ○ | ○ | ○ |
| s → a → ad → de → et | ○ | ○ | ○ | ○ | ○ |
| s → sbR → sa → ac → ce → t | ○ | ○ | ○ | ○ | ○ |
| s → b → d → deR → ce → t | ○ | ○ | ○ | ○ | ○ |
| s → a → b → c → e → t | ○ | ○ | ○ | ○ | ○ |
| s → b → bc → ce → et | ○ | ○ | ○ | ○ | ○ |
Assume you can reduce problem A to problem B in polynomial time. Fill in the table with what you can infer from the property in the first column. If you can't infer anything, write "nothing".
| If this is true | Then you can infer: |
|---|---|
| We know A must be slow (hard) | |
| We know A is fast (easy) | |
| We know B must be slow (hard) | |
| We know B is fast (easy) |
Which of the following is an example of a bipartite graph?
Draw a diagram of an NFA (non-deterministic finite automata) that accepts strings containing at least one '0' followed eventually by at least one '1'. Your diagram should:
Word Limit: Each answer must be 20 words or fewer. Longer answers receive zero credit.
What does it mean if a problem X is in the complexity class P?
What does it mean if a problem X is in the complexity class NP?
Consider the complexity classes P and NP. Why is P ⊆ NP?
Explain, in English, what NP-complete means (or what an NP-complete problem is). This should be an explanation geared toward somebody with no computing or relevant mathematical experience. (20 words maximum)
What step(s) are typically done to show that a problem is NP-complete? Fill in all that apply. (This answer can be up to 30 words, but no more!)
Every answer includes complete step-by-step explanations with NO ambiguity.
| sa | sb | ac | ad | bc | bd | ce | de | et |
|---|---|---|---|---|---|---|---|---|
| 4 | 4 | 3 | 3 | 2 | 2 | 5 | 2 | 2 |
| saR | sbR | acR | adR | bcR | bdR | ceR | deR | etR |
|---|---|---|---|---|---|---|---|---|
| 4 | 6 | 3 | 1 | 1 | 5 | 4 | 6 | 10 |
Step-by-step calculation:
Total flow verification: Flow out of s = 4+6 = 10, Flow into t = 10 ✓
Key Insights:
Key principle: If A ≤p B, then solving B solves A. Therefore:
| If this is true | Then you can infer: |
|---|---|
| We know A must be slow (hard) | B must also be slow (hard) Reason: If B were fast, we could solve A in polynomial time (reduction + B's time), contradicting that A is slow. |
| We know A is fast (easy) | Nothing Reason: B could be either fast or slow. A being easy doesn't tell us anything about B's difficulty. |
| We know B must be slow (hard) | Nothing Reason: A could be either easy or hard. B being hard doesn't constrain A. |
| We know B is fast (easy) | A must also be fast (easy) Reason: We can solve A by reducing to B (polynomial time) then solving B (fast), so total time is fast. |
Memory aid: Information flows "upstream" against the reduction arrow direction. If you know something about A (the source), it tells you about B (the target) if A is hard. If you know about B, it tells you about A if B is easy.
Explanation: A bipartite graph has vertices that can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. No edges exist within the same set.
Why each answer is right/wrong:
Bipartite test: A graph is bipartite if and only if it contains no odd-length cycles.
0
┌───┐ 1 ┌───┐ 0,1 ┌───┐
→ │ S │────→ │ A │─────→ │ B │
└───┘ └───┘ └─┬─┘
↓ ↑ │
│ 0,1 │ 0,1 │
└──────────┘ │
← (accepting)
Legend:
→ : Start state
← or double circle: Accept state
State descriptions:
Grading criteria:
Test cases:
ANSWER: Problem X can be solved in polynomial time.
Alternative acceptable answers (≤20 words):
ANSWER: Problem X can be verified in polynomial time.
Alternative acceptable answers (≤20 words):
ANSWER: If you can solve a problem in polynomial time, you can verify solutions in polynomial time.
Alternative acceptable answers (≤20 words):
Detailed reasoning: To verify a proposed solution, just solve the problem yourself and compare. Since solving takes polynomial time (because it's in P), verification also takes polynomial time, so it's in NP.
Real-world analogies that would score well:
Grading deductions:
Incorrect answers (do NOT check):
Complete answer format (30 words max):
"Show X is in NP by demonstrating polynomial-time verification. Reduce a known NP-complete problem to X in polynomial time." (20 words)
The two key steps:
Total: 100 points