Decision Problems and Input Encodings

From Graph Questions to Decision Problems

A graph question becomes a computational problem only after its input and required answer are specified. For a decision problem, the answer is one of two possibilities: yes or no. For example, the connectedness problem asks whether a given graph is connected; the bipartiteness problem asks whether it is bipartite. In each case, an algorithm must receive a finite representation of the graph, not an abstract graph with no specified encoding.

For example, an instance of the connectedness problem is a graph \(G\), and it is a yes-instance exactly when \(G\) is connected. The graph itself is the mathematical object; a computer receives a string that encodes it. An encoding rule specifies which strings represent which graphs. The input length is the number of symbols in the encoded input. When symbols are bits, it is the number of bits.

To make length calculations precise, use the following two encodings for finite simple undirected graphs. Their vertex set is \(\{1,\ldots,n\}\), where \(n\) may be zero. Both begin with the header \(1^n0\): \(n\) consecutive 1s followed by a 0. The header has length \(n+1\), and tells the decoder how many vertices to expect. Put \(w=\max(1,\lceil\log_2(n+1)\rceil)\), so each vertex label and each degree field uses exactly \(w\) bits.

These are explicit conventions for counting bits, not the only possible encodings. For \(n=0\), both encodings consist just of the header 0. If \(m=|E(G)|\), the lengths of the two encodings are

The list has \(n\) degree fields and \(2m\) neighbor labels. The matrix has \(n^2\) entries, including the diagonal entries, which are zero for a simple graph. These counts already show why \(m\) alone is not enough to describe input length: the encoding must also represent the vertices, including any isolated vertices.

Worked Length Calculations

Invalid Strings and the Decision Language

An encoding also specifies what happens when a string does not represent a valid graph. One convenient convention is to treat invalid strings as no-instances. Then a graph decision problem can be viewed as a set of binary strings: it contains exactly the valid encodings whose graphs satisfy the property. This convention makes the answer defined for every input string. Another setting may promise that inputs are valid; either way, the format must be stated.

Why Measure Running Time by Input Length?

An algorithm’s running time is a count of the computation it performs on its input representation. Therefore a complexity bound must be expressed in terms of the encoded input length, not merely the number of edges or vertices viewed in isolation. For a fixed encoding, the length accounts for all the information the algorithm must read: vertex data, edge data, and any format fields.

For example, an edgeless graph has \(m=0\), whether it has one vertex or a thousand. Those are not equally long inputs: the encoding must still specify the vertex set. With \(n=1000\), \(w=\lceil\log_2(1001)\rceil=10\). The list encoding of the edgeless graph has length

Its matrix encoding has length \(1000+1+1000^2=1001+1000000=1001001\) bits. Thus “the input has zero edges” does not mean “the input has length zero.” The encoding, not just a graph parameter, determines the input length.

Proof. Write \(L_{\mathrm{list}}\) and \(L_{\mathrm{matrix}}\) for the two lengths. If \(n=0\), both lengths are 1, so each is at most the square of the other. Now suppose \(n\ge1\). Since the graph is simple, \(2m\le n(n-1)\), and hence \(n+2m\le n^2\). Also \(w\le n\): for \(n\ge1\), \(2^n\ge n+1\), so \(\lceil\log_2(n+1)\rceil\le n\). Therefore \(L_{\mathrm{list}}=n+1+(n+2m)w\le n+1+n^3\le L_{\mathrm{matrix}}^2\). For the other direction, \(L_{\mathrm{list}}\ge n+1\), while \(L_{\mathrm{matrix}}=n+1+n^2\le(n+1)^2\le L_{\mathrm{list}}^2\). Thus each length is bounded by the square of the other, including the \(n=0\) case. \(\square\)

This result says the lengths cannot differ by more than a polynomial factor under these conventions. It does not say the lengths are equal, or that an algorithm takes the same number of steps on both formats.

Proof. For a matrix input, scan its \(n^2\) entries. For each 1 in the upper triangle, write the corresponding neighbor label into each endpoint’s list; the symmetry and zero diagonal conditions ensure this records every edge exactly once in each endpoint list. The scan takes \(n^2\) entry checks, and writing the lists takes at most the length of the output plus the work needed to read the input. Since the input matrix length is at least \(n^2\), both costs are polynomial in that length.

For a list input, initialize an \(n\) by \(n\) matrix of zeros and, for every neighbor label \(v\) in the list of \(u\), set the entries for \(uv\) and \(vu\) to 1. The list gives at most \(2m\) labels, and initializing and writing the matrix takes \(n^2\) entries. The input length is at least \(n+1\), so \(n^2\) and the work of processing the list are polynomial in that length. The case \(n=0\) requires only copying the one-bit header. Hence both conversions have polynomial bit cost. \(\square\)

Common Pitfall: Substituting a Graph Parameter for Input Length

A tempting but incorrect calculation is to say that an edgeless graph has input size \(m=0\), and therefore an algorithm taking \(O(n+m)\) steps takes constant time on it. The conclusion does not follow: \(n\) may be large even when \(m=0\), and the encoding must contain information about those vertices. For the 1000-vertex example, \(n+m=1000+0=1000\), not zero; the list has 11001 bits and the matrix has 1001001 bits.

There is a second related mistake: to state a runtime in terms of \(n\) or \(m\) without saying which representation the algorithm reads. A matrix algorithm may scan all \(n^2\) entries, whereas a list algorithm can visit the listed neighbors directly. Runtime claims must identify the encoding and compare the number of operations with its length. Once that convention is fixed, a polynomial bound means that the number of bit operations is bounded by some polynomial in the encoded input length. The focus here is this input-size measure; the formal study of polynomial-time algorithms follows next.