Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

Question

I am asking this question from the context of parameter preserving reductions which has implications for kernelization (See Theorem 18 of [1] for an example). For simplicity, here I am assuming that the host graph $G$ is regular. It seems to me that the game theoretic definition of treewidth is more useful here (See Section 2 of [2]).

Let $G$ be a regular graph with maximum degree $\Delta$. Let $H$ be a graph with $\Delta$ marked vertices. Let $G^*$ be the graph obtained from $G$ by replacing each vertex $v$ of $G$ by a copy of $H$ (say, each marked vertex of $H$ takes one neighbor of $v$ each).

Can we say that treewidth of $G^*$ is at most $\max\{tw(G)+\Delta,tw(H)+\Delta\}?$
(Let's use $tw(J)$ to denote the treewidth of a graph $J$.
For the special case $tw(H)\leq tw(G)$, we get the question in the title).

In [1], they consider the case when $H$ is sunlet$_6$ (i.e., $C_6$ plus a leaf attached to each vertex). In that paper, it is claimed that $tw(G^*)\leq tw(G)+2$. Is this claim correct?
(Disclaimer: it is possible that their claim is correct, but my idea of the generalization given as the first question is wrong).

The presentation in [1] gave me the feeling that the answer to the first question is yes. But, I couldn't find a reasonable explanation. I would like to know whether I am overlooking something well-known here.

Similar Situations

We can say the following.

1. If one vertex $v$ of $G$ alone is replaced by a copy of $H$, then the treewidth of the resultant graph is at most $\max\{tw(G)+\Delta,tw(H)+\Delta\}$.

Idea (in terms of cops and robber game): In an optimal cop strategy of $G$, whenever there is a cop at $v$, place $\Delta$ cops at marked vertices of $H$. Also, choose one of those points, make a new branch there which raids $H$. This forms a cops strategy for the resultant graph.

(Idea in terms of tree-decomposition: In the tree-decomposition of $G$, in each bag containing $v$, replace $v$ by marked vertices of $H$. Also, choose one such bag $B$ and append a new branch there that 'raids' $H$; in other words, take the tree-decomposition of $H$, add marked vertices of $H$ to each bag, and append this as a branch to the vertex associated with the bag $B$.)

2. Let $K$ be a graph with two marked vertices. Let $G'$ be the graph obtained from $G$ by replacing each edge $e$ of $G$ by a copy of $K$ (say, each marked vertex of $K$ takes one incident vertex of $e$ each). Then, the treewidth of $G'$ is at most $\max\{tw(G)+\Delta,tw(K)+\Delta\}$.

Idea (in terms of cops and robber game): Consider an optimal cops search strategy. For each edge $e=uv$ of $G$, choose a point in the strategy when edge $e$ is searched (i.e., there is a cop at $u$ and a cop at $v$) and raid $H$ at that point. This forms a cops strategy for $G'$.

Thank you.

References

[1] Lauri, Juho; Mitillos, Christodoulos, Complexity of fall coloring for restricted graph classes, ZBL07173544.

[2] Langer, Alexander; Reidl, Felix; Rossmanith, Peter; Sikdar, Somnath, Practical algorithms for MSO model-checking on tree-decomposable graphs, Comput. Sci. Rev. 13-14, 39-74 (2014). ZBL1302.68184.

Answer 1

Let $G$ be a complete graph with $n$ vertices and $H$ be a complete graph with $n-1$ vertices, all marked. We replace each vertex of $G$ with $H$ to produce a graph $G^*$ with $n(n-1)$ vertices that is $n$-regular. We claim that the treewidth of $G^*$ is at least $n (n-1)/12$, which falsifies the conjecture. Proof:

Suppose that the treewidth of $G^*$ is less than $n(n-1)/12$. Therefore by standard results [1] its vertices can be partitioned to sets $A$, $S$, $B$ such that there are no edges between $A$ and $B$, and $|S| = n(n-1)/12$, $|A| \ge n(n-1)/4$, $|B| \ge n(n-1)/4$, and $|A| + |B| = n(n-1)11/12$.

We call the cliques $H$ in $G^*$ corresponding to vertices of $G$ clusters. The graph $G^*$ has $n$ clusters. Note that each cluster has vertices from at most one of $A$ or $B$. Let $A_f$ be the fraction such that $n A_f$ clusters contain vertices from $A$ and $B_f$ the fraction such that $n B_f$ clusters contain vertices from $B$. Now, $A_f \ge 1/4$, $B_f \ge 1/4$, and $A_f + B_f \ge 11/12$.

Notice that if there is a cluster $v$ that contains vertices from $A$ and a cluster $u$ that contains vertices from $B$ then these clusters are connected by an edge $\{v_i, u_j\}$, both vertices in it unique to that pair of clusters, and at least one of $v_i$ and $u_j$ should be in $S$. Therefore we get that $|S| \ge n^2 A_f B_f$, which we can solve with our constraints to a minimum value $|S| \ge n^2 A_f B_f \ge n^2 8/12 \cdot 1/4 = n^2 1/6$, which is a contradiction to the assumed size of $S$.

[1] http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf

Answer 2

To clarify something: [1] does not use sunlet6, but C6. More specifically, the construction is as follows: Take G, subdivide every edge once, then make each old vertex additionally be part of its own new 6-cycle. In other words, if G has n vertices and m edges, G' has 6n + m vertices and 6n + 2m edges. The description you give isn't quite the same as this.

The treewidth inequality should follow easily from either the chordal completion formulation or the bramble formulation of treewidth. (Note that the new 6-cycles are blocks whose only connection to the rest of the graph is through a cut-vertex - the vertex they were identified with.) For example, if we use the chordal formulation, each 6-cycle can be given an additional 3 edges in a chordal completion, creating cliques of order 3. Then, the subdivided edges can be restored, which will allow a chordal completion of G to be used as a chordal completion of G'. Normally the treewidth will not change, but it can increase by at most 2, if, for instance, G was a single edge.