Graphs with No Long Claws: An Improved Bound for the Analog of the Gyárfás’ Path Argument

We address an open question from [23] that asked to eliminate the logarithmic factor in output 2 of Theorem 2. Indeed, it turns out that removing neighborhoods of a constant number of short paths is sufficient to obtain an extended strip decomposition with each particle of weight multiplicatively smaller than the total weight of the graph. Our main contribution is the following theorem.

Observe that removing some (unbounded) number of vertices is sometimes needed to get a nontrivial extended strip decomposition: adding to any $S_{t,t,t}$-free graph a large number of universal vertices keeps the graph $S_{t,t,t}$-free (for $t⩾2$), but destroys any useful extended strip decomposition of the graph. Hence, in other words, Theorem 3 improves one of the two pillars of the quasipolynomial algorithm for MWIS in $S_{t,t,t}$-free graphs of [15] to an arguably optimal bound of removing only a constant number of neighborhoods.

Similarly, as in [23], our starting point is the Gyárfás’ path, refining the selection of splitting vertices. If its length is within a small multiple of $t$, we even have a stronger result of components of half of the weight of $G$. Otherwise, we identify specific vertices of the Gyárfás’ path and query the three-in-a-tree theorem, originally developed by Chudnovsky and Seymour [12] with improved running time by Lai, Lu, and Thorup [21], on them. The output of the three-in-a-tree theorem is either an induced tree connecting the given vertices or an extended strip decomposition of $G$. By the choice of the vertices we make sure the second output applies, otherwise an induced copy of $S_{t,t,t}$ is found. The main difference from [23] lies in a more involved choice of the vertices with a better understanding of the structure of the extended strip decomposition. Among others, we use the obvious but powerful property of the last two vertices of the Gyárfás’ path. After removing the neighborhood of the Gyárfás’ path up to its second-to-last vertex, the largest connected component is still “big” (has weight larger than half of the weight of $G$). However, after removing the neighborhood of the last vertex, its weight suddenly drops below this threshold. This observation lets us look more closely at the interaction of the “big” particle and the “big” connected component.

Theorem 3 improves the quasi-polynomial running time bound of the algorithm for MWIS in $S_{t,t,t}$-free graphs of [15], but does not yield a polynomial-time algorithm. The running time bound of the algorithm of [15] is $n^{{𝒪}_t({\log }^{16}n)}$, where ${𝒪}_t$ hides factors depending on $t$. Few, but not all, of the $\log n$ factors in the exponent come from Theorem 2; using Theorem 3 instead removes them from the exponent. We refrain from re-doing here a detailed analysis of the branching algorithm of [15] to specify exactly what the improvement is; this analysis will appear in the journal version of [15].

In the specific case of sparse $S_{t,t,t}$-free graphs considered by [3], Theorem 3 significantly simplifies the situation. For the bounded degree case, the polynomial-time algorithm is now immediate: apply Theorem 3, exhaustively branch on $N[𝒮]$, and recurse on the particles of the extended strip decomposition. The algorithm for the more general case of excluding any fixed graph whose every component is a subdivided claw as an induced subgraph, and any fixed biclique as a subgraph can also be significantly simplified (but not to half a sentence as the previous case).

We remark that a very similar result to Theorem 3 has been independently obtained by Chudnovsky, Codsi, Milanič, Lokshtanov, and Sivashankar [9], via a slightly different proof.

All graphs are simple. Let $G$ be a graph. For $X\subseteq V(G)$, by $G[X]$ we denote the subgraph of $G$ induced by $X$, i.e., $(X,\{uv\in E(G):u,v\in X\})$. If the graph $G$ is clear from the context, we will often identify induced subgraphs with their vertex sets.

For a vertex $v$, by $N_G(v)$ we denote the set of neighbors of $v$, and by $N_G[v]$ we denote the set $N_G(v)\cup \{v\}$. For a set $X\subseteq V(G)$, we also define $N_G(X)≔{\bigcup }_{v\in X}{N}_G(v)-X$, and $N_G[X]=N_G(X)\cup X$. If it does not lead to confusion, we omit the subscript and write simply $N(\cdot )$ and $N[\cdot ]$. By $\left(\genfrac{}{}{0pt}{}{V(G)}{3}\right)$ we mean the set of all subsets of $V(G)$ of size 3. By $T(G)$, we denote the set of all triangles in $G$. Note that $T(G)\subseteq \left(\genfrac{}{}{0pt}{}{V(G)}{3}\right)$. Similarly to writing $xy\in E(G)$, we will write $xyz\in T(G)$ to indicate that $G[\{x,y,z\}]$ is a triangle. We say that two sets $X,Y\subseteq V(G)$ touch if $X\cap Y\ne \mathrm{\varnothing }$ or there is an edge with one end in $X$ and another in $Y$. For a family $𝒬$ of sets, by $\bigcup 𝒬$ we denote ${\bigcup }_{Q\in 𝒬}Q$. For a function $𝔴:V\to {\mathbb{Z}}_{⩾0}$ and subset $V^{\prime }\subseteq V$, we denote $𝔴(V^{\prime })≔{\sum }_{v\in V^{\prime }}𝔴(v)$.

A graph $G$ is said to be F-free for some graph $F$ if no induced subgraph of $G$ is isomorphic to $F$. For integers $t,a,b,c>0$, by $P_t$ we denote the path on $t$ vertices, and by $S_{a,b,c}$, we denote the tree with three leaves at respective distance $a$, $b$, and $c$ from the unique vertex of degree $3$ of the tree.

See [23, Figure 1] or [14, Figure 3] for an illustration of the definition below.

For an edge $xy\in E(H)$, the sets $\eta (xy,x)$ and $\eta (xy,y)$ are called the interfaces of the edge $xy$. An extended strip decomposition $(H,\eta )$ is rigid if (i) for every $xy\in E(H)$ it holds that $\eta (xy,x)\ne \mathrm{\varnothing }$, and (ii) for every $x\in V(H)$ such that $x$ is an isolated vertex it holds that $\eta (x)\ne \mathrm{\varnothing }$. Observe that if we restrict $\eta$ to $V^{\prime }\subset V(G)$, i.e. we keep in $\eta$ only vertices of $V^{\prime }$, then $(H,\eta )$ after the restriction remains an extended strip decomposition, but it might not be rigid anymore.

We say that a vertex $v\in V(G)$ is peripheral in $(H,\eta )$ if there is a degree-one vertex $x$ of $H$, such that $\eta (xy,x)=\{v\}$, where $y$ is the (unique) neighbor of $x$ in $H$. Note that we can also assume $\eta (x)=\mathrm{\varnothing }$, as otherwise all vertices from $\eta (x)$ can be moved to $\eta (xy)$. For a set $Z\subseteq V(G)$, we say that $(H,\eta )$ is an extended strip decomposition of $(G,Z)$ if $H$ has $|Z|$ degree-one vertices and each vertex of $Z$ is peripheral in $(H,\eta )$. The following theorem by Chudnovsky and Seymour [12] is a slight strengthening of their celebrated solution of the famous three-in-a-tree problem.

The running time was improved to $𝒪(m{\log }^{2}n)$ (where $m=|E|$) in [21].

A vertex particle $A_x$ is trivial if $x$ is an isolated vertex in $H$. Similarly, an extended strip decomposition $(H,\eta )$ is trivial if $H$ is an edgeless graph. Given a weight function $𝔴:V(G)\to \mathbb{N}$, we say that a particle is small if its weight is at most $\frac{𝔴(V(G))}{2}$, and an extended strip decomposition $(H,\eta )$ of $G$ is refined if all its particles are small.

Before the actual proof, we show several properties of extended strip decompositions. For the purposes of this overview, the most important is Lemma 11, which states that if $(H,\eta )$ is an extended strip decomposition of a graph $G$ then any induced path $P$ (in $G$) between peripheral vertices is entirely contained in edge particles. Moreover, in each edge particle, $P$ has at most one vertex in each interface.

Let us now describe the key ideas of the proof of Theorem 3. We start by considering a Gyárfás’ path $Q$ in $G$. If $Q$ is short, we can set $𝒮=V(Q)$ and return a trivial extended strip decomposition of $G-N[𝒮]$ satisfying the requirements of Theorem 3, so assume that $Q$ is long. First, we mark specific vertices of $Q$ on which we will query the three-in-a-tree theorem: The first vertex of $Q$ (call it $x$) and the vertices at distance $t+3$ (call it $y$) and $t+1$ (call it $z$) from the end of $Q$ other than $x$. Before querying the three-in-a-tree theorem, we remove the neighborhood outside $Q$ of three subpaths of $Q$: the subpaths of $Q$ starting at $x$ and $z$ and taking the next $t$ vertices in $Q$, respectively, and the subpath taking the $t$ vertices of $Q$ preceding $y$. We also remove the vertex of $Q$ between $y$ and $z$. See Figure 1 for an illustration. Observe that this selection ensures that the three-in-a-tree theorem either outputs an induced copy of $S_{t,t,t}$ (which is a desired output of  Theorem 3) or an extended strip decomposition of the graph minus the mentioned neighborhoods.

We take a closer look at the returned extended strip decomposition. If all its particles are small, we can simply return it, so assume it has a big particle $A$. Let us assume that $A$ is a full edge particle, i.e., $A=A_{pq}^{pq}$, the other cases being easy to handle. We distinguish two cases depending on whether the subpath $Q_1$ of $Q$ from $x$ to $y$ intersects $A$ or not. If $Q_1$ is disjoint from $A$, the only vertices of $Q_1$ that can have a neighbor in $A$ are vertices in an interface of a neighboring edge of $pq$ in $H$. Lemma 11 implies that there can be at most four of them. Finally, using that $Q$ is a Gyárfás’ path, we observe that after removing the neighborhoods of the three previously mentioned subpaths, of these four vertices and of four other well-chosen vertices, every remaining connected component has weight at most half of the total weight of $G$. If $Q_1$ intersects $A$, denote by $Q_2$ be the subpath of $Q$ from $z$ to the end of $Q$. The fact that $Q$ is induced and Lemma 11 together imply that $Q_2$ does not have any neighbor in $A$. From the property of Gyárfás’ path, letting $\mathrm{\ell }$ denote the last vertex of $Q$, we have that $G-N[V(Q)-\mathrm{\ell }]$ has a big connected component $C$ but $G-N[V(Q)]$ does not. Therefore, $\mathrm{\ell }$ has a neighbor in $V(C)$. Two big parts must intersect, so $V(C)$ and $A$ intersect. It then follows from Lemma 11 that $V(C)\subseteq A$. This contradicts the fact that $Q_2$ does not have any neighbor in $A$.

We start the proof of Theorem 3 with several properties of extended strip decompositions.

For convenience, we restate the Theorem 3 See 3