Running Time Depends on the Input
To ask whether a graph algorithm is fast, we need to say what counts as an input and how its length is measured. A procedure that takes time proportional to the number of vertices may be efficient on an explicitly listed graph, while the same vertex count could describe a much larger object if the graph were specified implicitly. Here we use explicit graph inputs and measure time against the number of symbols in their encoding.
A decision problem asks for a YES or NO answer. Formally, after choosing an encoding over a finite alphabet, its YES-instances form a language \(L\): the set of strings that should receive answer YES. An algorithm decides \(L\) if it halts on every input string and answers YES exactly on strings in \(L\). For a graph decision problem, an encoding describes the graph and the question being asked. Malformed encodings can be rejected.
The maximum in the bound matters: it makes the definition apply even to the empty string, whose length is zero. The exponent and constant may depend on the algorithm, but not on the input. A running-time bound is a worst-case guarantee: it must hold for every input of a given length, not just for typical inputs.
For an explicit graph encoding, the vertices and edges are listed, with separators and enough information to identify the vertices. Write \(n=|V|\) for the order and \(m=|E|\) for the size of a graph. In such an encoding, the input length \(N\) is at least \(n\) and at least \(m\), since the list must account for every vertex and edge. Consequently, a bound polynomial in \(n+m\) is also polynomial in \(N\). This implication relies on explicit listing; it should not be assumed for a compact or implicit description of a graph.
From Graph-Size Bounds to Input-Length Bounds
Proof. For an explicit encoding, \(n\le N\) and \(m\le N\), so \(n+m\le 2N\). Therefore the graph-processing part takes at most $$ C(n+m)^r\le C(2N)^r=C2^rN^r. $$ The right-hand side is a polynomial bound in \(N\). Adding a polynomial parsing bound still gives a polynomial: if parsing takes at most \(D\max\{1,N\}^s\), then the sum of the two bounds is at most a constant times \(\max\{1,N\}^{\max\{r,s\}}\). Thus the total time is polynomial in input length. \(\square\)
For example, a scan of adjacency lists takes \(O(n+m)\) elementary graph operations: each vertex is handled a bounded number of times, and each edge appears in one list for a directed graph or two lists for an undirected graph. When vertex labels and queue entries are represented by \(O(\log N)\)-bit indices, those operations can be implemented by ordinary deterministic computation with polynomial overhead. The exact exponent is less important here than the fact that the bound remains polynomial in \(N\).
Worked Example: Testing Connectedness Across Components
Worked Example: Testing Connectedness Across Components
Let \(G\) be the simple undirected graph with \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,45\}\). Decide whether \(G\) is connected. A graph is connected if every pair of vertices is joined by a path.
Use breadth-first search (BFS), which stores discovered vertices in a queue and explores their neighbors. To test the whole graph, start a new BFS whenever an unvisited vertex remains. In this graph, start at 1, then continue with the first unvisited vertex in the order \(1,2,\dots,6\). The table records the queue after processing the indicated vertex.
| Action | Queue afterward | Vertices discovered so far |
|---|---|---|
| Start at 1 | 1 | 1 |
| Process 1; discover 2 | 2 | 1, 2 |
| Process 2; discover 3 | 3 | 1, 2, 3 |
| Process 3; no new neighbor | empty | 1, 2, 3 |
| Start at 4 | 4 | 1, 2, 3, 4 |
| Process 4; discover 5 | 5 | 1, 2, 3, 4, 5 |
| Process 5; no new neighbor | empty | 1, 2, 3, 4, 5 |
| Start at 6 | 6 | 1, 2, 3, 4, 5, 6 |
| Process 6; no new neighbor | empty | 1, 2, 3, 4, 5, 6 |
The search finds three components: \(\{1,2,3\}\), \(\{4,5\}\), and \(\{6\}\). The output is NO: for instance, there is no path from 1 to 4. The input has \(n=6\) vertices and \(m=3\) edges, so scanning the vertex lists takes six vertex-handling steps and examines \(2m=2\cdot3=6\) adjacency-list entries. This is linear in \(n+m=6+3=9\).
Check: the edges \(12\) and \(23\) connect 1, 2 and 3; edge \(45\) connects 4 and 5; vertex 6 has no incident edge. No listed edge joins these three groups, so the component count agrees with the search.
The restart rule is essential. A search from vertex 1 alone visits only the component containing 1. Reporting that all vertices were reached would be wrong for a disconnected graph. The algorithm is complete because every vertex is either discovered during some search or, if still undiscovered after a search ends, becomes the start of the next one.
Worked Example: Testing Bipartiteness
Worked Example: Testing Bipartiteness
Let \(G\) have \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,41,45\}\). A graph is bipartite if its vertices can be assigned two colors so that every edge has endpoints of different colors. Run BFS in every component, giving each newly discovered neighbor the color opposite its current vertex.
Begin at vertex 1 and color it red. Process the queue as follows; when a vertex is processed, every neighbor is checked, including neighbors already colored.
| Processed vertex | Newly colored neighbors | Queue afterward |
|---|---|---|
| 1 (red) | 2 and 4 blue | 2, 4 |
| 2 (blue) | 3 red | 4, 3 |
| 4 (blue) | 5 red; 3 is already red | 3, 5 |
| 3 (red) | 2 and 4 are already blue | 5 |
| 5 (red) | 4 is already blue | empty |
Vertex 6 is still uncolored, so start a separate search there and color it red. It has no neighbors. The resulting color classes are \(\{1,3,5,6\}\) and \(\{2,4\}\). Checking the five edges gives \(12\) red–blue, \(23\) blue–red, \(34\) red–blue, \(41\) blue–red, and \(45\) blue–red. Every edge has differently colored endpoints, so the answer is YES.
Check: the first component has five edges, and each is in two undirected adjacency lists, so it contributes \(2\cdot5=10\) adjacency-list entries. The isolated vertex contributes zero more. The total is \(10\), as expected. The color classes also account for all six vertices: \(4+2=6\).
Proof. If the procedure returns YES, it has assigned one of two colors to every vertex and checked every edge. Since it returned YES, no edge has equally colored endpoints. The two color classes therefore form a bipartition.
Conversely, suppose the graph is bipartite, with parts \(X\) and \(Y\). In each component, the initial vertex lies in one part. Every edge joins different parts, so each newly discovered neighbor lies in the part opposite the vertex that discovers it. The procedure’s assigned colors therefore agree with the two parts, up to interchanging the color names within that component. Thus no edge can have equally colored endpoints, and the procedure returns YES. This argument applies separately to every component, including isolated vertices, which have no edge that could fail the check. \(\square\)
Worked Example: Directed Reachability
Worked Example: Directed Reachability
Let \(D\) be the directed graph with \(V=\{a,b,c,d,e\}\) and directed edge set \(E=\{(a,b),(a,c),(b,d),(c,d),(d,b)\}\). Decide whether there is a directed path from \(a\) to \(d\). Run BFS from \(a\), following edges in their stated direction, and stop once \(d\) is discovered.
| Action | Queue afterward | Discovered vertices |
|---|---|---|
| Start at \(a\) | \(a\) | \(a\) |
| Process \(a\); discover \(b,c\) | \(b,c\) | \(a,b,c\) |
| Process \(b\); discover \(d\) | \(c,d\) | \(a,b,c,d\) |
The procedure returns YES as soon as \(d\) is discovered. A directed path witnessing the answer is \(a,b,d\), since \((a,b)\in E\) and \((b,d)\in E\). In this trace it examines two outgoing edges from \(a\) and one from \(b\), for a total of \(2+1=3\) edge entries before stopping.
Check: the input has five listed directed edges. A full BFS would examine at most five outgoing edge entries, while this early-stopping run examines three. Both counts are at most \(m=5\), consistent with the \(O(n+m)\) upper bound.
For the full reachability test, BFS reports YES if it discovers the target and NO if the queue empties first. Every discovered vertex is reachable from the start: this holds initially for the start itself, and a newly discovered vertex is reached by extending the path to the vertex currently being processed by one directed edge. Conversely, if a vertex is reachable, following a path from the start shows successively that each vertex on the path is eventually discovered, unless the search has already found the target. Thus the test answers the reachability question correctly.
Polynomial Bounds and Exponential Bounds
A polynomial such as \(N^3\) grows differently from an exponential such as \(2^N\). To compare concrete values, at \(N=10\) the cubic expression is \(10^3=1000\), while the exponential is \(2^{10}=1024\). At \(N=20\), the cubic expression is \(20^3=8000\), while the exponential is \(2^{20}=1{,}048{,}576\). These evaluations do not by themselves prove an asymptotic claim, but they illustrate why an exponential search can become much more costly as input length grows.
Common pitfall: confusing \(n\) with \(N\). Since an explicit encoding has \(n\le N\), one might reason that a procedure taking \(2^n\) steps is polynomial. The inequality actually gives \(2^n\le2^N\), which is still an exponential upper bound, not a polynomial one. For instance, when \(n=20\), \(2^n=1{,}048{,}576\); the fact that the encoding contains at least 20 symbols does not turn this expression into \(N^k\) for a fixed exponent \(k\). The distinction between polynomial and exponential bounds concerns how the running time grows with input length, not just the value on one input.
Polynomial time is a precise asymptotic class, not a guarantee that every polynomial-time algorithm is fast in practice: a large constant or a high exponent can matter substantially. Conversely, a procedure may be quick on many instances without having a polynomial worst-case bound. For explicit graph inputs, the useful first step is to count the vertices and edge entries the procedure inspects, then relate that count to \(N\).
Check Your Understanding
Use the definitions and arguments above to answer these questions.
- Why does the polynomial-time definition use \(\max\{1,N\}\) rather than \(N\) alone?
- For an explicitly listed graph with \(n\) vertices and \(m\) edges, explain why \(n+m\le2N\).
- What error occurs if a connectedness test runs BFS from one vertex only and assumes every vertex has been visited?
- In the bipartiteness procedure, why must every edge be checked, including edges whose endpoints were both colored earlier?
- Explain why the implication \(n\le N\) does not establish that a running time of \(2^n\) is polynomial in \(N\).