Tree width of a particular graph

Question

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

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).

• David Eppstein: 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?
• Nicholas Mancuso: I apologize, that was in error. I have updated the picture now.
• Saeed: Your $V_1,V_2$ doesn't create complete bipartite graph?
• Nicholas Mancuso: 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]$.

Answer 1

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.

• Nicholas Mancuso: 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.