<p>The problem is still NP-complete. Here's a reduction from the Treewidth problem on general graphs. Recall that for a graph G of treewidth at least two, the treewidth is not affected when subdividing an edge by a degree-2 vertex (i.e. replacing an edge $\{u,v\}$ by a new vertex $x$ and edges $\{u,x\}$, $\{x,v\}$ ).</p>

<p>Given an input graph $G$ on $n$ vertices, assume without loss of generality that it has treewidth at least two (otherwise we can solve the problem and output an equivalent constant-sized instance). Number the vertices of G from $1$ to $n$, in some arbitrary order. Now assign vertex $v_i$ to set $S_{2i}$, and observe that trivially, each set $S_i$ induces an independent set in the graph; we will maintain this during the following process. As long as the graph has an edge $\{u,v\}$ between two vertices which are not in adjacent sets, say an edge between a vertex in $S_i$ and one in $S_j$ for $i &lt; j$ and $j-i &gt; 1$, subdivide the edge, placing the newly created degree-2 vertex in set $S_{i+1}$. Since this subdivider vertex is placed between the endpoints of the subdivided edge, it decreases the difference between the indices of the sets that its neighbors are in, and therefore each edge of the original graph is subdivided no more than $n$ times. So  this process terminates after a polynomial number of steps. The resulting graph $G&#39;$ was made from G by repeatedly subdividing edges, so its treewidth equals that of G. Let us verify that the resulting sets satisfy that all connected components of $G&#39;[S_i \cup S_{i+1}]$ are bicliques. One of the indices $i, i+1$ is odd. By construction, the set for this odd index contains only degree-2 vertices which were added to subdivide an edge. Since the subdivider vertex was placed "in the gap between its two neighbors", each degree-2 vertex has one neighbor in the previous set, and one neighbor in the next set. So the set out of $S_i, s_{i+1}$ with odd index has only vertices which have degree one in the graph $G&#39;[S_i \cup S_{i+1}]$, which shows that the graph is a disjoint union of stars which are bicliques. So the graph G' has treewidth equal to G, size polynomial in that of G, and can be constructed in polynomial time. Since treewidth is NP-complete, so is the restriction to your special graph class.</p>

CC BY-SA 3.0
2012-01-18T16:45:07.947Z
Excellent reduction and proof! Thank you so very much. I am just learning of the concepts of treewidth (and other width-measures for that matter) and still dont have a solid grasp of them yet. This is extremely helpful.
Nicholas Mancuso
CC BY-SA 3.0
2012-01-18T09:52:09.573Z
2012-01-18T09:52:09.573Z
Bart Jansen
<p>What is the tree-width of the graph $G = (V_1 \cup V_2 \cup \dotsb V_n, E)$ where  the connected components of an induced subgraph of any neighboring set of vertices (i.e. $G[V_i \cup V_j], i = j - 1$) are complete bipartite graphs? Here is an example. </p>

<p><img src="https://i.sstatic.net/NyhhV.png" alt="example graph"></p>

<p>It is clear the entire graph $G$ is bipartite, and showing the tree-width of bipartite graphs is $\mathcal{NP}$-Hard in general, but I was curious if this added enough structure to the problem to make it tractable. For instance, we can easily find the largest bipartite clique just by finding a vertex with maximum degree, then finding its neighbors (and their predecessors).</p>

CC BY-SA 3.0
2012-01-17T21:04:55.367Z
Your example has an edge from $V_2$ to $V_4$, and is not bipartite (that edge is part of a 7-cycle). Is that what you want?
David Eppstein
CC BY-SA 3.0
2012-01-17T21:12:18.290Z
I apologize, that was in error. I have updated the picture now.
Nicholas Mancuso
CC BY-SA 3.0
2012-01-17T21:45:27.703Z
Your $V_1,V_2$ doesn't create complete bipartite graph?
Saeed
CC BY-SA 3.0
2012-01-17T21:51:32.187Z
Each connected component is a biclique--not the entire subgraph itself. $K_{2,2}$ and $K_{1,1}$ are the connected components of the induced subgraph $G[V_1 \cup V_2]$.
Nicholas Mancuso
<graph-theory><optimization><treewidth>
Tree width of a particular graph
Nicholas Mancuso
# Tree width of a particular graph

(Asked by: username_0 on 2012-01-17)

What is the tree-width of the graph $G = (V\_1 \cup V\_2 \cup \dotsb V\_n, E)$ where the connected components of an induced subgraph of any neighboring set of vertices (i.e. $G[V\_i \cup V\_j], i = j - 1$) are complete bipartite graphs? Here is an example.

![example graph](https://i.sstatic.net/NyhhV.png)

It is clear the entire graph $G$ is bipartite, and showing the tree-width of bipartite graphs is $\mathcal{NP}$-Hard in general, but I was curious if this added enough structure to the problem to make it tractable. For instance, we can easily find the largest bipartite clique just by finding a vertex with maximum degree, then finding its neighbors (and their predecessors).

**Tags:** graph-theory, optimization, treewidth

> **Comments:**
> **username_1**: Your example has an edge from $V_2$ to $V_4$, and is not bipartite (that edge is part of a 7-cycle). Is that what you want?  
> **username_0**: I apologize, that was in error. I have updated the picture now.  
> **username_2**: Your $V_1,V_2$ doesn't create complete bipartite graph?  
> **username_0**: Each connected component is a biclique--not the entire subgraph itself. $K_{2,2}$ and $K_{1,1}$ are the connected components of the induced subgraph $G[V_1 \cup V_2]$.  

---

## 1 answers

### Answer by username_3 on 2012-01-18. Score: 10 | Accepted answer

The problem is still NP-complete. Here's a reduction from the Treewidth problem on general graphs. Recall that for a graph G of treewidth at least two, the treewidth is not affected when subdividing an edge by a degree-2 vertex (i.e. replacing an edge $\{u,v\}$ by a new vertex $x$ and edges $\{u,x\}$, $\{x,v\}$ ).

Given an input graph $G$ on $n$ vertices, assume without loss of generality that it has treewidth at least two (otherwise we can solve the problem and output an equivalent constant-sized instance). Number the vertices of G from $1$ to $n$, in some arbitrary order. Now assign vertex $v\_i$ to set $S\_{2i}$, and observe that trivially, each set $S\_i$ induces an independent set in the graph; we will maintain this during the following process. As long as the graph has an edge $\{u,v\}$ between two vertices which are not in adjacent sets, say an edge between a vertex in $S\_i$ and one in $S\_j$ for $i < j$ and $j-i > 1$, subdivide the edge, placing the newly created degree-2 vertex in set $S\_{i+1}$. Since this subdivider vertex is placed between the endpoints of the subdivided edge, it decreases the difference between the indices of the sets that its neighbors are in, and therefore each edge of the original graph is subdivided no more than $n$ times. So this process terminates after a polynomial number of steps. The resulting graph $G'$ was made from G by repeatedly subdividing edges, so its treewidth equals that of G. Let us verify that the resulting sets satisfy that all connected components of $G'[S\_i \cup S\_{i+1}]$ are bicliques. One of the indices $i, i+1$ is odd. By construction, the set for this odd index contains only degree-2 vertices which were added to subdivide an edge. Since the subdivider vertex was placed "in the gap between its two neighbors", each degree-2 vertex has one neighbor in the previous set, and one neighbor in the next set. So the set out of $S\_i, s\_{i+1}$ with odd index has only vertices which have degree one in the graph $G'[S\_i \cup S\_{i+1}]$, which shows that the graph is a disjoint union of stars which are bicliques. So the graph G' has treewidth equal to G, size polynomial in that of G, and can be constructed in polynomial time. Since treewidth is NP-complete, so is the restriction to your special graph class.

> **Comments:**
> **username_0**: Excellent reduction and proof! Thank you so very much. I am just learning of the concepts of treewidth (and other width-measures for that matter) and still dont have a solid grasp of them yet. This is extremely helpful.  

---

