4
$\begingroup$

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

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Laakeri Dec 16 '20 at 21:20
  • $\begingroup$ @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. $\endgroup$ – Cyriac Antony Dec 17 '20 at 5:40
  • 1
    $\begingroup$ 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$? $\endgroup$ – Christian Komusiewicz Dec 17 '20 at 14:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Laakeri Dec 17 '20 at 20:07
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Cyriac Antony Dec 29 '20 at 5:46
  • $\begingroup$ 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. $\endgroup$ – Laakeri Dec 29 '20 at 7:17
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.