<p>Though we've chatted about this in person before, I'll add this in the hope that this will allow someone else to provide a complete answer.</p>
<p>In your process of adding vertices, define a partial function <span class="math-container">$f:V(G) \rightharpoonup V(G)$</span> from each vertex <span class="math-container">$v$</span> which gets used, to the vertex which was added when <span class="math-container">$v$</span> got used. Then it turns out that <span class="math-container">$f$</span> is a <a href="http://arxiv.org/abs/0906.4261" rel="noreferrer"><em>(causal) flow</em> function</a> (p. 39), which is a restricted version of a path cover. Indeed, your description of these graphs of &quot;complexity <em>k</em>&quot; (given a set of vertices which are to be the initially unused vertices, and the final unused vertices) is precisely the star decomposition of a &quot;geometry&quot; with a causal flow (p. 46 of the above article).</p>
<p>Although these &quot;causal flows&quot; have been studied mainly in the context of (measurement-based) quantum computation — where they are motivated by certain structures of unitary circuits — there are graph-theoretic results about them which are totally divorced from quantum computation:</p>
<blockquote>
<p><strong><a href="http://arxiv.org/abs/quant-ph/0611284" rel="noreferrer">Uniqueness modulo endpoints</a>:</strong> the graphs with &quot; complexity <span class="math-container">$k$</span> &quot; are precisely those for which there exist (possibly intersecting) sets <span class="math-container">$S,T \subseteq V(G)$</span>, both of size <span class="math-container">$k$</span>, such that <span class="math-container">$G$</span> has exactly one path cover of size <span class="math-container">$k$</span> whose paths start in <span class="math-container">$S$</span> and end in <span class="math-container">$T$</span>.<br><br></p>
<p><strong><a href="http://arxiv.org/abs/quant-ph/0611284" rel="noreferrer">Extremal graphs</a>:</strong> A graph on <span class="math-container">$n$</span> vertices which has &quot;complexity <span class="math-container">$k$</span>&quot; has at most <span class="math-container">$kn - \binom{k+1}{2}$</span> edges.</p>
</blockquote>
<p>Using these results, and given a candidate pair of sets <span class="math-container">$S,T$</span>, determining whether or not they &quot;subtend&quot; a unique path cover in this way can be determined in time <span class="math-container">$O(k^2 n)$</span>; but finding whether or not such sets of endpoints exist that is the apparent difficulty, and the extremal result above (which is only a necessary condition) seems to represent the state of the art in efficient criteria to determine whether such sets exist.</p>

CC BY-SA 3.0
2012-09-26T17:37:14.857Z
2012-09-27T17:54:38.917Z
2020-06-17T09:38:08.363Z
Niel de Beaudrap
<p>All graphs of complexity $k$ has path-width at most $k$.
At every step the set of unused nodes is a separator separating the used nodes from those already created. So at every step, when you add a vertex, you can create a bag containing that vertex plus all unused vertices and connect the bag at the end of the path decomposition.
This will be a valid path decomposition.</p>

<p>Because of the "which $v$ is connected" in point 3 and 2 the path-width can be much smaller than $k$.
I am not sure about deciding if $G$ is a complexity $k$, but as Niel says, there must be a path cover of size k, but not only a path cover, the paths have to be induced.
And inbetween the paths we can have this zig-zag pattern.
We can in $f(k) \cdot poly(n)$ time compute an optimal path decomposition, then we can use this decomposition to do dynamic programming while keeping track of the different segments of these $k$ paths, which path they belong to and the order of segments belonging to the same path. And for each pair of segments belonging to different paths we only need to know the first and last path of the zig-zag.</p>

<p>Therefore I think we can decide if a graph has complexity $k$ in $f(k) \cdot poly(n)$ time.</p>

CC BY-SA 3.0
2012-11-09T23:48:42.460Z
2012-11-09T23:48:42.460Z
Martin Vatshelle
<p>I am interested in graphs on $n$ vertices which can be produced via the following process.</p>

<ol>
<li>Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as <i>unused</i>.</li>
<li>Produce a new graph $G'$ by adding a new vertex $v$, which is connected to one or more  <i>unused</i> vertices in $G$, and is not connected to any <i>used</i> vertices in $G$. Label $v$ as <i>unused</i>.</li>
<li>Label one of the vertices in $G'$ to which $v$ is connected as <i>used</i>.</li>
<li>Set $G$ to $G'$ and repeat from step 2 until $G$ contains $n$ vertices.</li>
</ol>

<p>Call such graphs "graphs of complexity $k$" (apologies for the vague terminology). For example, if $G$ is a graph of complexity 1, $G$ is a path.</p>

<p>I would like to know if this process has been studied before. In particular, for arbitrary $k$, <b>is it NP-complete to determine whether a graph has complexity $k$?</b></p>

<p>This problem appears somewhat similar to the question of whether $G$ is a <a href="https://cstheory.stackexchange.com/questions/1532/what-is-the-correct-definition-of-k-tree">partial $k$-tree</a>, i.e. has <a href="http://en.wikipedia.org/wiki/Treewidth" rel="nofollow noreferrer">treewidth</a> $k$. It is known that determining whether $G$ has treewidth $k$ is NP-complete. However, some graphs (stars, for example) may have much smaller treewidth than the measure of complexity discussed here.</p>

<p>4th October 2012: Question <a href="https://mathoverflow.net/questions/108824/a-graph-parameter-possibly-related-to-treewidth">cross-posted</a> to MathOverflow after there was no conclusive answer after a week (though thanks for the info about causal flows).</p>

<ds.algorithms><graph-theory><treewidth>
A graph parameter possibly related to treewidth
Ashley Montanaro
# A graph parameter possibly related to treewidth

(Asked by: username_0 on 2012-09-26)

I am interested in graphs on $n$ vertices which can be produced via the following process.

1. Start with an arbitrary graph $G$ on $k\le n$ vertices. Label all the vertices in $G$ as *unused*.
2. Produce a new graph $G'$ by adding a new vertex $v$, which is connected to one or more *unused* vertices in $G$, and is not connected to any *used* vertices in $G$. Label $v$ as *unused*.
3. Label one of the vertices in $G'$ to which $v$ is connected as *used*.
4. Set $G$ to $G'$ and repeat from step 2 until $G$ contains $n$ vertices.

Call such graphs "graphs of complexity $k$" (apologies for the vague terminology). For example, if $G$ is a graph of complexity 1, $G$ is a path.

I would like to know if this process has been studied before. In particular, for arbitrary $k$, **is it NP-complete to determine whether a graph has complexity $k$?**

This problem appears somewhat similar to the question of whether $G$ is a [partial $k$-tree](https://cstheory.stackexchange.com/questions/1532/what-is-the-correct-definition-of-k-tree), i.e. has [treewidth](http://en.wikipedia.org/wiki/Treewidth) $k$. It is known that determining whether $G$ has treewidth $k$ is NP-complete. However, some graphs (stars, for example) may have much smaller treewidth than the measure of complexity discussed here.

4th October 2012: Question [cross-posted](https://mathoverflow.net/questions/108824/a-graph-parameter-possibly-related-to-treewidth) to MathOverflow after there was no conclusive answer after a week (though thanks for the info about causal flows).

**Tags:** ds.algorithms, graph-theory, treewidth


---

## 2 answers

### Answer by username_1 on 2012-09-26. Score: 8

Though we've chatted about this in person before, I'll add this in the hope that this will allow someone else to provide a complete answer.

In your process of adding vertices, define a partial function $f:V(G) \rightharpoonup V(G)$ from each vertex $v$ which gets used, to the vertex which was added when $v$ got used. Then it turns out that $f$ is a [*(causal) flow* function](http://arxiv.org/abs/0906.4261) (p. 39), which is a restricted version of a path cover. Indeed, your description of these graphs of "complexity *k*" (given a set of vertices which are to be the initially unused vertices, and the final unused vertices) is precisely the star decomposition of a "geometry" with a causal flow (p. 46 of the above article).

Although these "causal flows" have been studied mainly in the context of (measurement-based) quantum computation — where they are motivated by certain structures of unitary circuits — there are graph-theoretic results about them which are totally divorced from quantum computation:

> **[Uniqueness modulo endpoints](http://arxiv.org/abs/quant-ph/0611284):** the graphs with " complexity $k$ " are precisely those for which there exist (possibly intersecting) sets $S,T \subseteq V(G)$, both of size $k$, such that $G$ has exactly one path cover of size $k$ whose paths start in $S$ and end in $T$.
>
> **[Extremal graphs](http://arxiv.org/abs/quant-ph/0611284):** A graph on $n$ vertices which has "complexity $k$" has at most $kn - \binom{k+1}{2}$ edges.

Using these results, and given a candidate pair of sets $S,T$, determining whether or not they "subtend" a unique path cover in this way can be determined in time $O(k^2 n)$; but finding whether or not such sets of endpoints exist that is the apparent difficulty, and the extremal result above (which is only a necessary condition) seems to represent the state of the art in efficient criteria to determine whether such sets exist.


---

### Answer by username_2 on 2012-11-09. Score: 3

All graphs of complexity $k$ has path-width at most $k$.
At every step the set of unused nodes is a separator separating the used nodes from those already created. So at every step, when you add a vertex, you can create a bag containing that vertex plus all unused vertices and connect the bag at the end of the path decomposition.
This will be a valid path decomposition.

Because of the "which $v$ is connected" in point 3 and 2 the path-width can be much smaller than $k$.
I am not sure about deciding if $G$ is a complexity $k$, but as Niel says, there must be a path cover of size k, but not only a path cover, the paths have to be induced.
And inbetween the paths we can have this zig-zag pattern.
We can in $f(k) \cdot poly(n)$ time compute an optimal path decomposition, then we can use this decomposition to do dynamic programming while keeping track of the different segments of these $k$ paths, which path they belong to and the order of segments belonging to the same path. And for each pair of segments belonging to different paths we only need to know the first and last path of the zig-zag.

Therefore I think we can decide if a graph has complexity $k$ in $f(k) \cdot poly(n)$ time.


---

