Representing repeated structure in graphs

Question

Apologies for not knowing exactly what I'm looking for, but I'd appreciate any general pointers to get me started.

I'm interested in efficient representations (graphical and otherwise) of finite graphs with repeated structure --- something like coding theory for graph structures. For example, an $N$ by $N$ grid graph where each non-boundary vertex has four neighbors (up, right, left, down) could be represented with far fewer than O($N^2$) parameters. A $N$ by $N$ grid where each non-boundary vertex has 8 neighbors (up left, up, up right, ...) should take more parameters to represent, but not many more. I'm imagining a notation or diagram that uses a base template, then defines a local connectivity pattern and a repetition structure.

I'd like to be able to ask (and start to answer) questions like:

1. What is the minimum number of parameters needed to describe a particular graph structure?
2. Are there some problems that become fixed-parameter tractable for graphs that can be described with $k$ parameters?

Is there a branch of graph theory that studies these types of questions? I'd be grateful for pointers to starting points or related work.

Answer 1

I am not sure what exactly is meant by a repeated structure but at least some covering graphs should qualify. Covering graphs may be quite large, however they admit concise description via voltage graphs. The edges of a small base graph or voltage graph are equipped with group elements, called voltages. For instance, an n x n tessellation of a torus can be described by a single vertex with two loops and group elements (0,1) and (1,0) taken from the group $Z_n \times Z_n$ assigned to the loops. Of course most graphs admit no compression in this way.

Answer 2

Once you have found the smallest description of a graph (in your favored scheme), then a philosophically minded person will say, Yes, but how about the smallest description-of-a-description of a graph? And how about the smallest description-of-a-description-of-a-description? Why stop?

These ideas will lead you to the concept of Kolmogorov complexity, where one measures the complexity or information content of a mathematical object by the smallest computational description of it, essentially the size of the smallest program that generates the object. The subject is a part of the emerging theory of computational concepts of randomness, an extremely active current area of research in computability theory. The theory is usually thought of as applied to strings: a string is incompressible if the shortest computational description of it has the same size as itself (thus, the most efficient way to describe it is by explicitly listing it out). Compressible strings, in constrast, have comparatively low information density, since they are describable by a much smaller object. Thus, the graphs you seek to describe are exactly the graphs that are compressible with respect to Kolmogorov complexity.

Thus, I propose that we measure the complexity of a graph on vertices $\{1,2,\ldots,n\}$ by the size of the smallest program able to compute the edge relation. (Let us fix for this purpose a notion of computability, such as Turing machines.) This would correspond to the Kolmogorov complexity, and it will be an extremely robust notion of the measure of the complexity of description of your graph. The class of graphs you have in mind are those that are compressible with respect to this measure, computed by a program that is strictly smaller than the program that simply stores the edge relation in state memory.

There is a small paradox in the subject of computational randomness, since ordinarily one might think of a random string as containing very little information, but in this subject, such strings are incompressible, as it is difficult to describe them exactly except by listing them out explicitly. In this sense, therefore, random strings contain a huge amount of information. Similarly, random graphs are hard to describe in any other way other than by listing the edge relation explicitly.

Because of these ideas, your question (perhaps in extreme form) may ultimately have more to do with logic than with graph theory. Almost any mathematical object can be coded into a graph (in a precise sense, every mathematical structure is interpretable inside a graph), and all such mathematical objects can be ultimately described by strings, to which the Kolmogorv ideas apply. You are asking about are the graphs that are compressible in the sense of Kolmogorov complexity. On cardinality grounds, of course, most graphs are not like this. In general, one should expect Turing noncomputability issues to arise, since the question of whether a given string is compressible is undecidable. Similarly, the question of whether a given finite graph is incompressible is undecidable.

Answer 3

There are some applications of the design theory to the efficient description of strongly regular graphs. (A strongly regular graph with parameteres ($n$, $k$, $l$, $m$) is a graph with $n$ vertices, in which the number of common neighbours of $x$ and $y$ is $k$, $l$ or $m$ according as $x$ and $y$ are equal, adjacent or non-adjacent.) The desigh theory deals with the questions about subsets of sets which exhibit a high degree of regularity.

Have a look at this book.

Answer 4

You can try representing graphical adjacencies in a propositional formula, and then squeeze out redundancies by using some species of canonical form.

I don't recall trying this for arbitrary graphs, but I do recall solving graph coloring problems this way. Here's one link I was able to find right away, an example from Wilf's Algorithms and Complexity (1986).

Graph Coloring Example

What you need to know is that a parenthetical form like $(x_1, \ldots, x_k)$ means that exactly one of the boolean variables $x_1, \ldots, x_k$ is false.

Here's a propositional constraint representation of the 5 queens problem, which may be more suggestive of a way to proceed with your square grid domain.

Five Queens Problem

And here's an exposition of the language and program that I was using to do these examples:

Zeroth Order Logic