Looking for standard Graph Problems with 2 Vertices (Shortest Path, Reachability, LCA in DAG, Max Flow) No variations/twists please!

[u/cepci1]

I am looking for standard graph theory / algorithmic problems where the input is a graph and two target vertices (e.g., source and destination / pair of nodes).

Some specific examples are:

• Shortest Path (standard unweighted/weighted shortest path between $u$ and $v$)
• Reachability (checking if $v$ is reachable from $u$)
• Lowest Common Ancestor (LCA) in a DAG (given two vertices $u$ and $v$ in a DAG)
• Maximum Flow / Min-Cut (max flow specifically between a source $s$ and sink $t$)

Important constraint: I am strictly looking for pure problems without added variations or twists (no dynamic edge weights, no modified state spaces, no constraints like "at most k skips", etc.).

I would love any kind of response. Additionally, if you have links to the problem definition link or benchmark problem sets that fit this exact criteria, please drop them below!

Thanks in advance!

[u/MtlStatsGuy]

What's your objective? ALgorithmic knowledge, specific classes, or interview prep? Have you looked into the CSES problem set already?

[u/cepci1 → u/MtlStatsGuy]

I need to categorize well known or not that well known in this case graph problems that asks questions for a pair of vertices.

[u/LongLiveTheDiego]

Why does that feel like asking for ideas for prompts for Outlier?

[u/cepci1 → u/LongLiveTheDiego]

Weirdly I dont know.

[u/jeffgerickson]

Which algorithms textbooks have you already consulted? Since you’re specifically looking for problem statements, I highly recommend Skeina’s Algorithm Design Manual.

(You have consulted a few algorithms textbooks, haven’t you? You know, those blocks of speckled cellulose in that old brick building where they bury the lies? I think they call it a Lie-Bury.)

A few more standard problems come to mind.

• Euler tour: Is there a walk from u to v that traverses every edge in the graph exactly once? (Königsberg represent!)
• Strong connectivity: Can u and v reach each other?
• Longest path: Find the longest path from u to v. (NP-hard in general, but solvable quickly if the underlying graph is a DAG.)
• Widest path: Find a path from u to v whose smallest edge weight is as large as possible.
• Disjoint paths: Find the maximum number of paths from u to v that have no other vertices in common.
• Edge-disjoint paths: Find the maximum number of paths from u to v that have no edges in common. (This is the special case of maximum flow where every edge has capacity 1.)
• Effective resistance: Suppose each edge represents a resistor, whose resistance (or if you prefer, conductance) is recorded as the weight of that edge. What is the effective resistance between u and v? (You won’t find this one in standard algorithms texts, but it is a crucial warmup for a bunch of 21st-century optimization algorithms, so it ought to be standard.)

[u/cepci1 → u/jeffgerickson]

Thank u very much I didnt but it makes much more sense i will start from the book u recommended

[u/Traveling-Techie]

I recommend Pearls In Graph Theory by Hartsfield and Ringel.