<p>Let <span class="math-container">$G$</span> be a complete graph with <span class="math-container">$n$</span> vertices and <span class="math-container">$H$</span> be a complete graph with <span class="math-container">$n-1$</span> vertices, all marked. We replace each vertex of <span class="math-container">$G$</span> with <span class="math-container">$H$</span> to produce a graph <span class="math-container">$G^*$</span> with <span class="math-container">$n(n-1)$</span> vertices that is <span class="math-container">$n$</span>-regular. We claim that the treewidth of <span class="math-container">$G^*$</span> is at least <span class="math-container">$n (n-1)/12$</span>, which falsifies the conjecture. Proof:</p>
<p>Suppose that the treewidth of <span class="math-container">$G^*$</span> is less than <span class="math-container">$n(n-1)/12$</span>. Therefore by standard results [1] its vertices can be partitioned to sets <span class="math-container">$A$</span>, <span class="math-container">$S$</span>, <span class="math-container">$B$</span> such that there are no edges between <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, and <span class="math-container">$|S| = n(n-1)/12$</span>, <span class="math-container">$|A| \ge n(n-1)/4$</span>, <span class="math-container">$|B| \ge n(n-1)/4$</span>, and <span class="math-container">$|A| + |B| = n(n-1)11/12$</span>.</p>
<p>We call the cliques <span class="math-container">$H$</span> in <span class="math-container">$G^*$</span> corresponding to vertices of <span class="math-container">$G$</span> clusters. The graph <span class="math-container">$G^*$</span> has <span class="math-container">$n$</span> clusters. Note that each cluster has vertices from at most one of <span class="math-container">$A$</span> or <span class="math-container">$B$</span>. Let <span class="math-container">$A_f$</span> be the fraction such that <span class="math-container">$n A_f$</span> clusters contain vertices from <span class="math-container">$A$</span> and <span class="math-container">$B_f$</span> the fraction such that <span class="math-container">$n B_f$</span> clusters contain vertices from <span class="math-container">$B$</span>.
Now, <span class="math-container">$A_f \ge 1/4$</span>, <span class="math-container">$B_f \ge 1/4$</span>, and <span class="math-container">$A_f + B_f \ge 11/12$</span>.</p>
<p>Notice that if there is a cluster <span class="math-container">$v$</span> that contains vertices from <span class="math-container">$A$</span> and a cluster <span class="math-container">$u$</span> that contains vertices from <span class="math-container">$B$</span> then these clusters are connected by an edge <span class="math-container">$\{v_i, u_j\}$</span>, both vertices in it unique to that pair of clusters, and at least one of <span class="math-container">$v_i$</span> and <span class="math-container">$u_j$</span> should be in <span class="math-container">$S$</span>.
Therefore we get that <span class="math-container">$|S| \ge n^2 A_f B_f$</span>, which we can solve with our constraints to a minimum value <span class="math-container">$|S| \ge n^2 A_f B_f \ge n^2 8/12 \cdot 1/4 = n^2 1/6$</span>, which is a contradiction to the assumed size of <span class="math-container">$S$</span>.</p>
<p>[1] <a href="http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf" rel="nofollow noreferrer">http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf</a></p>

CC BY-SA 4.0
2020-12-29T05:46:50.567Z
I could understand till the point $|S|\geq n^2 A_f B_f$. *How can we say that $A_f B_f\geq 8/12 \cdot 1/4$ ?* (I couldn't see how minimization come into the picture and how we get the inequality). Also, I am unable to find the cited result in Cygan et al.; Could you please give chapter and section numbers? Thank you.
Cyriac Antony
CC BY-SA 4.0
2020-12-29T07:17:37.327Z
The inequality follows from the facts that $A_f \ge 1/4$, $B_f \ge 1/4$, and $A_f + B_f \ge 11/12$. The minimum possible value that $A_f B_f$ can have with these constraints is $8/12 \cdot 1/4$. The cited result is an application of Lemma 7.20 in that book.
Laakeri
CC BY-SA 4.0
2020-12-17T13:33:39.323Z
2020-12-17T13:33:39.323Z
Laakeri
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-04-15T02:07:44.750Z
2021-04-15T02:07:44.750Z
Chris
<p>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 <span class="math-container">$G$</span> is regular. It seems to me that the game theoretic definition of treewidth is more useful here (See Section 2 of [2]).</p>
<p>Let <span class="math-container">$G$</span> be a regular graph with maximum degree <span class="math-container">$\Delta$</span>. Let <span class="math-container">$H$</span> be a graph with <span class="math-container">$\Delta$</span> marked vertices. Let <span class="math-container">$G^*$</span> be the graph obtained from <span class="math-container">$G$</span> by replacing each vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span> by a copy of <span class="math-container">$H$</span> (say, each marked vertex of <span class="math-container">$H$</span> takes one neighbor of <span class="math-container">$v$</span> each).</p>
<p><strong>Can we say that treewidth of <span class="math-container">$G^*$</span> is at most <span class="math-container">$\max\{tw(G)+\Delta,tw(H)+\Delta\}?$</span></strong><br />
(Let's use <span class="math-container">$tw(J)$</span> to denote the treewidth of a graph <span class="math-container">$J$</span>.<br />
For the special case <span class="math-container">$tw(H)\leq tw(G)$</span>, we get the question in the title).</p>
<p>In [1], they consider the case when <span class="math-container">$H$</span> is sunlet<span class="math-container">$_6$</span> (i.e., <span class="math-container">$C_6$</span> plus a leaf attached to each vertex). In that paper, it is claimed that <span class="math-container">$tw(G^*)\leq tw(G)+2$</span>. <strong>Is this claim correct?</strong><br />
(Disclaimer: it is possible that their claim is correct, but my idea of the generalization given as the first question is wrong).</p>
<p>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.</p>
<h2>Similar Situations</h2>
<p>We <strong>can</strong> say the following.</p>
<ol>
<li>If one vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span> alone is replaced by a copy of <span class="math-container">$H$</span>, then the treewidth of the resultant graph is at most <span class="math-container">$\max\{tw(G)+\Delta,tw(H)+\Delta\}$</span>.</li>
</ol>
<p>Idea (in terms of cops and robber game): In an optimal cop strategy of <span class="math-container">$G$</span>, whenever there is a cop at <span class="math-container">$v$</span>, place <span class="math-container">$\Delta$</span> cops at marked vertices of <span class="math-container">$H$</span>. Also, choose one of those points, make a new branch there which raids <span class="math-container">$H$</span>. This forms a cops strategy for the resultant graph.</p>
<p>(Idea in terms of tree-decomposition: In the tree-decomposition of <span class="math-container">$G$</span>, in each bag containing <span class="math-container">$v$</span>, replace <span class="math-container">$v$</span> by marked vertices of <span class="math-container">$H$</span>. Also, choose one such bag <span class="math-container">$B$</span> and append a new branch there that 'raids' <span class="math-container">$H$</span>; in other words, take the tree-decomposition of <span class="math-container">$H$</span>, add marked vertices of <span class="math-container">$H$</span> to each bag, and append this as a branch to the vertex associated with the bag <span class="math-container">$B$</span>.)</p>
<ol start="2">
<li>Let <span class="math-container">$K$</span> be a graph with two marked vertices. Let <span class="math-container">$G'$</span> be the graph obtained from <span class="math-container">$G$</span> by replacing each edge <span class="math-container">$e$</span> of <span class="math-container">$G$</span> by a copy of <span class="math-container">$K$</span> (say, each marked vertex of <span class="math-container">$K$</span> takes one incident vertex of <span class="math-container">$e$</span> each). Then, the treewidth of <span class="math-container">$G'$</span> is at most <span class="math-container">$\max\{tw(G)+\Delta,tw(K)+\Delta\}$</span>.</li>
</ol>
<p>Idea (in terms of cops and robber game): Consider an optimal cops search strategy. For each edge <span class="math-container">$e=uv$</span> of <span class="math-container">$G$</span>, choose a point in the strategy when edge <span class="math-container">$e$</span> is searched (i.e., there is a cop at <span class="math-container">$u$</span> and a cop at <span class="math-container">$v$</span>) and raid <span class="math-container">$H$</span> at that point. This forms a cops strategy for <span class="math-container">$G'$</span>.</p>
<p>Thank you.</p>
<h2>References</h2>
<p>[1] <em>Lauri, Juho; Mitillos, Christodoulos</em>, <a href="http://dx.doi.org/10.1007/978-3-030-25005-8_29" rel="nofollow noreferrer"><strong>Complexity of fall coloring for restricted graph classes</strong></a>,  <a href="https://zbmath.org/?q=an:07173544" rel="nofollow noreferrer">ZBL07173544</a>.</p>
<p>[2] <em>Langer, Alexander; Reidl, Felix; Rossmanith, Peter; Sikdar, Somnath</em>, <a href="http://dx.doi.org/10.1016/j.cosrev.2014.08.001" rel="nofollow noreferrer"><strong>Practical algorithms for MSO model-checking on tree-decomposable graphs</strong></a>, Comput. Sci. Rev. 13-14, 39-74 (2014). <a href="https://zbmath.org/?q=an:1302.68184" rel="nofollow noreferrer">ZBL1302.68184</a>.</p>

CC BY-SA 4.0
2020-12-16T21:20:07.327Z
Can you explain the transformation in more detail? I understand what happens when a single vertex is transformed, but what about all vertices simultaneously? Have you considered what happens when $G$ and $H$ are both complete graphs? To my understanding of the transformation this should break the conjecture.
Laakeri
CC BY-SA 4.0
2020-12-17T05:40:59.440Z
@Laakeri Let $1,2,\dots,\Delta$ be the marked vertices of $H$. Suppose we get $G^*$ be replacing every vertex of $G$ by a copy of $H$ (simultaneously). When a vertex $v$ is replaced by a copy of $H$, let us rename the marked vertices of that copy of $H$ as $v_1,v_2,\dots,v_\Delta$. So, $G^*$ is made of $|V(G)|$ copies of $H$, and for each edge $uv$ of $G$, there exist $i,j$ such that there is an edge $u_iv_j$ in $G^*$. You are saying that the conjecture is false when both $G$ and $H$ are complete graphs. Very interesting; please post your idea as an answer.
Cyriac Antony
CC BY-SA 4.0
2020-12-17T14:12:17.103Z
Is it even known that the treewidth is bounded roughly by the product of the old treewidth and $\Delta$, say by $(tw(G)+tw(H))\cdot \Delta$?
Christian Komusiewicz
CC BY-SA 4.0
2020-12-17T20:07:38.440Z
I think we can get a tree decomposition of width $\max(tw(G) \cdot \Delta, tw(H) + \Delta)$ by expanding all bags of the decomposition of $G$ and connecting the decompositions of $H$ appropriately.
Laakeri
<graph-theory><treewidth>
Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?
Cyriac Antony
# Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

(Asked by: username_0 on 2020-12-16)

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**](http://dx.doi.org/10.1007/978-3-030-25005-8_29), [ZBL07173544](https://zbmath.org/?q=an:07173544).

[2] *Langer, Alexander; Reidl, Felix; Rossmanith, Peter; Sikdar, Somnath*, [**Practical algorithms for MSO model-checking on tree-decomposable graphs**](http://dx.doi.org/10.1016/j.cosrev.2014.08.001), Comput. Sci. Rev. 13-14, 39-74 (2014). [ZBL1302.68184](https://zbmath.org/?q=an:1302.68184).

**Tags:** graph-theory, treewidth
> **Comments:**
> **username_1**: Can you explain the transformation in more detail? I understand what happens when a single vertex is transformed, but what about all vertices simultaneously? Have you considered what happens when $G$ and $H$ are both complete graphs? To my understanding of the transformation this should break the conjecture.  
> **username_0**: @Laakeri Let $1,2,\dots,\Delta$ be the marked vertices of $H$. Suppose we get $G^*$ be replacing every vertex of $G$ by a copy of $H$ (simultaneously). When a vertex $v$ is replaced by a copy of $H$, let us rename the marked vertices of that copy of $H$ as $v_1,v_2,\dots,v_\Delta$. So, $G^*$ is made of $|V(G)|$ copies of $H$, and for each edge $uv$ of $G$, there exist $i,j$ such that there is an edge $u_iv_j$ in $G^*$. You are saying that the conjecture is false when both $G$ and $H$ are complete graphs. Very interesting; please post your idea as an answer.  
> **username_2**: Is it even known that the treewidth is bounded roughly by the product of the old treewidth and $\Delta$, say by $(tw(G)+tw(H))\cdot \Delta$?  
> **username_1**: I think we can get a tree decomposition of width $\max(tw(G) \cdot \Delta, tw(H) + \Delta)$ by expanding all bags of the decomposition of $G$ and connecting the decompositions of $H$ appropriately.  

---

## 2 answers

### Answer by username_1 on 2020-12-17. Score: 4 | Accepted answer

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>

> **Comments:**
> **username_0**: I could understand till the point $|S|\geq n^2 A_f B_f$. *How can we say that $A_f B_f\geq 8/12 \cdot 1/4$ ?* (I couldn't see how minimization come into the picture and how we get the inequality). Also, I am unable to find the cited result in Cygan et al.; Could you please give chapter and section numbers? Thank you.  
> **username_1**: The inequality follows from the facts that $A_f \ge 1/4$, $B_f \ge 1/4$, and $A_f + B_f \ge 11/12$. The minimum possible value that $A_f B_f$ can have with these constraints is $8/12 \cdot 1/4$. The cited result is an application of Lemma 7.20 in that book.  

---

### Answer by username_3 on 2021-04-15. Score: 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.


---

