7
$\begingroup$

An addition chain for $n \in \mathbb{N}$ is a sequence of natural numbers $$1 = a_0,\ldots,a_l =n$$ such that each $a_t$ is the sum of two previous elements in the sequence. The length of minimal addition chains for natural numbers has been studied intensely.

I wonder if "graph addition chains" have been studied, most probably under different names. For a graph $G$, a graph addition chain could be a sequence of graphs $$G_0,\ldots,G_l =G$$ such that $G_0$ is contained in some set $\mathcal{F}$ of elementary graphs, and each $G_t$ is some sum of two previous elements. Depending on $\mathcal{F}$ and the sum operation, one could ask about the length of minimal graph addition chains (if they exist).

As an example, set $\mathcal{F} = \{K_{k+1}\}$ and let the sum operation be the $k$-sum of graphs. Graph addition chains with these parameters produce partial $k$-trees, and we ask to construct partial $k$-trees using the minimal number of $k$-sums. For $k=1$, graph addition chains for path graphs correspond to addition chains for natural numbers, making this problem already $NP$-hard.

I would be thankful for any references to algorithmic and structural results about this or related concepts.

$\endgroup$
  • 1
    $\begingroup$ Not an answer, but note that the minimum length of an addition chain is nothing but the minimum size of circuits consisting of the constant-1 gate and the binary addition gate. So another way to state “graph addition chain” is a circuit where each gate has a graph as a value and each internal node performs a certain operation on graphs. $\endgroup$ – Tsuyoshi Ito Jul 13 '12 at 23:20
2
$\begingroup$

Sequences of colored graphs under the operations of disjoint union (a form of graph addition), recoloring, and adding edges between all vertices with some color combination form the basis for the definition of clique-width. However, the quantity of interest for measuring the complexity of such a sequence is not the number of operations needed, but the number of colors.

$\endgroup$
  • $\begingroup$ In particular any "tree like" decomposition of a graph can usually be translated into a way of writing the graph as a "sum" of "parts". So tree decompositions, split/modular decompositions, and the strucural decompositions for perfect/claw-free/etc. graphs can be thought of in this way. For different decompositions the correspondence is more or less strong. $\endgroup$ – daniello May 25 '17 at 13:04
1
$\begingroup$

1) Hajos calculus for non-$k$-colorability. Using the Hajos construction, one defines a notion of $k$-constructible graph as follows:

  • the complete graph $K_k$ is $k$-constructible

  • taking two $k$-constructible graphs and applying the yields a $k$-constructible graph

  • identifying two vertices preserves $k$-constructibility.

Every $k$-critical graph (requires $k$ colors but every subgraph needs at most $k-1$ colors) is $k$-constructible, and for all graphs $G$ $\chi(G) \geq k$ iff $G$ contains a $k$-constructible subgraph. This is a bit more complicated than what you asked for, since you'd also need to allow adding vertices, adding edges, and merging vertices, but it still feels like it's in the same spirit. The Hajos number of a $k$-colorable graph $G$ is the minimum number of steps needed to construct $G$ from $K_k$; there is no polynomial upper bound on the Hajos number unless NP=coNP.

2) Although not about graphs in particular, people have also studied circuits over sets of natural numbers. Here each input is a finite subset of $\mathbb{N}$, the gates are union, intersection, complement, + and times. So, in between (?) addition chains and graph addition chains, you might consider "subsets-of-$\mathbb{N}$" addition chains, by allowing only restricted inputs and a restricted gate set. As you can see from the Wikipedia table, several of the related problems are NP-complete, such as minimizing circuits with only $\cup, +$ gates (which might reasonably be considered "addition chains", esp. if you restrict the inputs to be all singletons, e.g.), or minimizing formulae with $\cup,\cap,+$ gates.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.