An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs

Our strategy goes as follows. We make a breadth-first search (BFS) from some arbitrary vertex $u_0$ in each connected component of the graph $G$. We reserve colors $1,2,3,4$ for the even-indexed BFS layer, and $5,6,7,8$ for the odd-indexed BFS layer. We thus need to 4-color each connected component $X$ of each subgraph induced by a single layer. Let $R$ be a string representation of the entire graph, and $R[X]$ its restriction to $X$. As any face in the arrangement $R[X]$ can be made the infinite face, we can assume that the string of $u_0$ lies on the infinite face of $R[X]$. Now $R[X]$ has a nice property: The minimal topological disk $D$ that contains it is such that each string of $R[X]$ intersects at least one string (in $R\setminus R[X]$) that itself crosses $\partial D$, the boundary of $D$. Indeed, such a string is given by a neighbor in the previous layer.

We now consider the string representation $R_H$ made by $X$ and at least one neighbor of the previous layer for each vertex of $X$, and intersect it by $D$. Each string of $X$ remains in one piece, whereas the strings of the previous layer are possibly split into several strings in $D$. Let $H$ be the intersection graph of $R_H$. We further layer $X$ with the distance in $H$ to a fixed vertex $w\in V(H)\setminus V(X)$. Let $X_k$ be the vertices of $H$ at distance exactly $k$ from $w$ in $H$.

We are left with proving that $H[X_k]$ is bipartite. For the sake of contradiction, we assume that there is an odd cycle $C$ in $H[X_k]$. Our goal is to show that this odd cycle is contained in a ball of small radius around some vertex, yielding a contradiction in the form of a short odd cycle. For that, we establish that there is another odd cycle $C^{\prime }$ (built from $C$) such that the string of $w$ is contained in a face $F$ made by few strings of $N_H[C^{\prime }]$, with most of the rest of $C^{\prime }$ not intersecting $F$. A string defining $F$ is then at a small distance of every string of $C^{\prime }$ since a (shortest) path from $w$ to a vertex of the rest of $C^{\prime }$ has to cross the boundary of $F$. After which, the path has only a constant number of steps to reach its target since vertices of $N_H[C^{\prime }]$ are at distance $k-1$, $k$, or $k+1$ from $w$. The short odd cycle in $H$ implies the existence of a short odd cycle in $G$, a contradiction.

The chromatic number of intersection graphs of a given girth has a long history. Erdős and Gyárfás asked if girth-4 (i.e., triangle-free) segment intersection graphs have bounded chromatic number [10]. Kostochka and Nešetřil [17] raised the same question for 1-string graphs.³³3The 1-strings are strings every pair of which intersects at most once; note that it is not a property of particular objects but rather their arrangement. Both questions were answered in the negative in [27]. It was further shown by Walczak [28] that there are triangle-free segment intersection graphs without independent sets of size linear in the number of vertices. Nevertheless, Kostochka and Nešetřil [18] proved that 1-string graphs of girth at least 8 are 3-colorable, and asked [18, Problem 3] whether 8 could be replaced by 5. This has been confirmed for outer 1-strings by Das, Mukherjee, and Sahoo [7].

More relevant to our Vertex Cover application, the chromatic number of (1-)string graphs of a given odd girth has also been considered. (Note indeed that, in the design of a $(2-\epsilon )$-approximation algorithm for Vertex Cover, whereas one can remove odd cycles up to any fixed size, the same trick does not apply to 4-vertex cycles.) McGuinness established that 1-string graphs of odd girth at least 7 have bounded chromatic number [24, 25]. Chudnovsky, Scott, and Seymour [6, Corollary from 12.4 and 12.5] further showed that string graphs of odd girth at least 9 are 80-colorable, and string graphs of odd girth at least 7 have bounded chromatic number. With proper adjustments, the former result can be turned into an algorithm that inputs a representation of any string graph $G$ of odd girth at least 9, and outputs an 80-coloring of $G$ in time polynomial in the representation. However, this would yield a significantly worse approximation factor for Vertex Cover.

The reason intersection graphs of 1-strings with girth at least 8 are 3-chromatic [18] is that they are 2-degenerate, i.e., (all their induced subgraphs) have a vertex of degree at most 2, which gives a recursive 3-coloring strategy. While string graphs of large odd girth are not $d$-degenerate for any $d$ (they contain arbitrarily large bipartite complete graphs), we conjecture that they are nevertheless 3-colorable.

A stronger form of Conjecture 3 is that it holds for $k=7$.

The following observation summarizes the trade-off between required odd girth and bound on the chromatic number, in how they impact the approximation ratio.

We apply Observation 4 on represented string graphs with $g=13$ and $c=8$. Showing a counterpart of Theorem 2 with $g=11$ and $c⩽10$ would improve the ratio to $9/5=1.8$, and with $g=9$ and $c⩽8$, to $7/4=1.75$. Past this point, our 8-coloring starts being the bottleneck. The last possible step of this method would be to get parameters $g=7$ and $c⩽6$, for a ratio of $5/3=1.666\mathrm{\dots }$ Indeed we recall that string graphs of odd girth at least 5 have unbounded chromatic number [27], and do not necessarily have linear-size independent sets [28]. On the complexity side, we do not expect that Vertex Cover is APX-hard (i.e., NP-hard to approximate within some constant ratio $r>1$) on represented string graphs as a quasipolynomial-time approximation scheme (QPTAS) exists [1, 11]. However, if a PTAS also exists, it will have to be found with a different approach than ours.

Let us emphasize that Theorem 2 is the only place where our algorithm actually requires a representation of the input to be given. Thus, an algorithm coloring string graphs with no short odd cycles, that works directly on the input graph $G$ (not its representation), would yield an approximation algorithm for Vertex Cover in string graphs whose complexity is polynomial in the number of vertices of $G$. However, if we are only interested in the decision variant of the problem, the existential statement in Theorem 2 is sufficient to get the following result.

Let us remark that the authors of [23] claim that their algorithm can actually return a 1.9999-approximate solution in time polynomial in the number of vertices of the input graph but this is, unfortunately, not true. Indeed, one of the crucial steps in their argument is the application of a result of Lee [22, Theorem 4.2], whose proof has recently been realized to be flawed⁴⁴4The inequality at the sixth line of the proof of Lemma 4.14 need not hold. [21, 3]. Seemingly the result [22, Theorem 4.2] can be reproven in a different way but only for region intersection graphs (a generalization of string graphs) [8], and the new approach requires that the representation is given (and still the final approximation ratio is much closer to 2 than the one given by Theorem 1). Similarly, it is claimed that the approach in [23] applies for all proper induced-minor-closed classes, but the problem lies in the same place: we are not aware of any way to fix the proof of Lee [22, Theorem 4.2] in such a general setting.

We leave as open questions if Vertex Cover admits, for some constant $\epsilon >0$, a $(2-\epsilon )$-approximation algorithm on string graphs given without representation (which is very likely to be the case), and on classes excluding a fixed graph $H$ as an induced minor.⁵⁵5i.e, $H$ cannot be obtained from graphs of the class by removing vertices and contracting edges

We denote by $V(G)$ and $E(G)$ the set of vertices and edges of a graph $G$, respectively. A graph $H$ is an induced subgraph (resp. subgraph) of a graph $G$ if $H$ can be obtained from $G$ by vertex deletions (resp. by vertex and edge deletions). For $S\subseteq V(G)$, the subgraph of $G$ induced by $S$, denoted $G[S]$, is obtained by removing from $G$ all the vertices that are not in $S$. Then $G-S$ is a short-hand for $G[V(G)\setminus S]$. A set $X\subseteq V(G)$ is connected (in $G$) if $G[X]$ has a single connected component.

If $C$ is a cycle, once a direction along the cycle is fixed, we may denote by $C[x\to y]$ the subpath of $C$ from $x\in V(C)$ to $y\in V(C)$, turning in this direction.

Let $v_1,\mathrm{\dots },v_h$ list the neighbors of $v$ on $C$, starting at an arbitrary vertex and turning in a fixed (arbitrary) direction. The cycles $C_1,\mathrm{\dots },C_h$, each with vertex set $\{v\}\cup C[v_i\to v_{i(modh)+1}]$ for $i\in [h]$, respectively, have a combined number of edges of $|V(C)|+2h$; an odd number since $|V(C)|$ is odd. Hence at least one of $C_1,\mathrm{\dots },C_h$ has odd length. $◀$

Let $G$ be a graph and $v\in V(G)$. We denote by $N_G(v)$ and $N_G[v]$, the open, respectively closed, neighborhood of $v$ in $G$. For a non-negative integer $r$, we denote by $N_G^{⩽r}(v)$ (resp. $N_G^{=r}(v)$) the set of vertices of $G$ at distance at most $r$ (resp. exactly $r$) from $v$. We may call $N_G^{⩽r}(v)$ the ball of radius $r$ around $v$ (in $G$). We will rely on the observation that if a possibly long odd cycle is contained in a ball of small radius, then there is also a short odd cycle (in this ball).

Perform a breadth-first search (BFS) starting at $v$ in $G[N_G^{⩽r}(v)]$. By definition, this breadth-first search has exactly $r+1$ layers $L_0,L_1,\mathrm{\dots },L_r$, with $L_i:=N_G^{=i}(v)$ for each $i\in [0,r]$. At least one $L_i$ is not an independent set, otherwise $G[N_G^{⩽r}(v)]$ would be bipartite, and would not contain any odd cycle. Say $x,y\in L_i$ are adjacent, and let $z\in L_{i^{\prime }}$ be their lowest common ancestor in the BFS tree (possibly $z=v$ and $i^{\prime }=0$). Then, there is a cycle of length $2(i-i^{\prime })+1⩽2r+1$ in $G[N_G^{⩽r}(v)]$, consisting of the edge $xy$ and the paths from $z$ to $x$ and from $z$ to $y$ in the BFS tree. Furthermore, if $N_G^{=r}(v)\cap V(C)$ is an independent set of $G$, then the odd cycle $C$ has at least one of its edges with both endpoints in some $L_i\ne L_r$, which makes an odd cycle of length at most $2r-1$. $◀$

A string is a subset of ${ℝ}^2$ homeomorphic to a closed segment. We may call a path-connected subset of a string $s$ a substring of $s$. If $R$ is a collection of strings in the plane, we denote their intersection graph by $G_R$, with one vertex per string, and an edge between every pair of intersecting strings. For any vertex $v\in V(G_R)$, we denote by $s_R(v)$ the string representing $v$ in $R$. Conversely, we may denote by $v_R(s)$ the vertex represented by the string $s$. We typically drop the subscript when $R$ is clear from the context. If $X$ is an induced subgraph of $G_R$, we may denote by $R[X]$ the subset of strings of $R$ corresponding to vertices of $X$.

A face of a geometric arrangement made by a collection $𝒮$ of strings, or more specifically of curves, in ${ℝ}^2$ is a connected component of ${ℝ}^2\setminus {\bigcup }_{s\in 𝒮}s$. A closed face is the topological closure of a face. If $D$ is a topological disk, and more generally a face, we denote by $\partial D$ its boundary. For instance, the curve $\partial D$ defines two faces, one of which is finite ($D\setminus \partial D$), and admits $D$ as a closed face. We may denote by $\overline{F}$ the closure of an (open) face $F$.

If $P$ is an induced path represented by strings $s_1,\mathrm{\dots },s_h$ (i.e., $s_i$ and $s_j$ intersect whenever $|i-j|=1$), $a\in s_1$ and $b\in s_h$, we denote by $s[a,P,b]$ a minimal path-connected subset of ${\bigcup }_{i\in [h]}{s}_i$ containing $a$ and $b$. In particular $s[a,P,b]$ is a string with endpoints $a$ and $b$, coinciding with each $s_i$ on a substring of positive length. Although $s[a,P,b]$ is not necessarily uniquely defined, every further claim will hold regardless of the actual choice for $s[a,P,b]$. It can thus be thought as a short-hand for: fix any minimal path-connected subset of ${\bigcup }_{i\in [h]}{s}_i$ containing $a$ and $b$, and denote it $s[a,P,b]$.

It will be convenient to extend the latter notation to induced cycles, that is, to allow $s_1$ and $s_h$ to be adjacent. If $P$ may be a cycle, then $s[a,P,b]$ is defined more specifically in the case when $s_1$ and $s_h$ indeed intersect. If there is a point $c\in s_1\cap s_h$ and two substrings $s_1^{\prime }\subseteq s_1,s_h^{\prime }\subseteq s_h$ with endpoints $a,c$ and $b,c$, respectively, such that $(s_1^{\prime }\cup s_h^{\prime })\cap {\bigcup }_{2⩽i⩽h-1}{s}_i=\mathrm{\varnothing }$, then $s[a,P,b]:=s_1^{\prime }\cup s_h^{\prime }$. If not, then there is a (non-self-intersecting) string that starts at $a$, follows non-empty substrings of $s_1,\mathrm{\dots },s_h$ in this order, and ends at $b$. We fix, as before, $s[a,P,b]$ to be any such string.

We will need the following lemma.

Let $t,t^{\prime }$ be two distinct strings of $W$, with $q\in t\cap \partial D$ and $q^{\prime }\in t^{\prime }\cap \partial D$. Let $P_1,P_2$ be the two paths from $v(t)$ to $v(t^{\prime })$ in $C$. We define the strings $t_1:=s[q,P_1,q^{\prime }]$ and $t_2:=s[q,P_2,q^{\prime }]$. We denote by $⟨q,q^{\prime }⟩$ and $⟨q^{\prime },q⟩$ the two minimal path-connected subsets of $\partial D$ containing $q$ and $q^{\prime }$. Let $F_1,F_1^{\prime }$ be the two finite (open) faces with boundary $⟨q,q^{\prime }⟩\cup t_1$ and $⟨q^{\prime },q⟩\cup t_1$, respectively. Similarly let $F_2,F_2^{\prime }$ be the two finite faces with boundary $⟨q,q^{\prime }⟩\cup t_2$ and $⟨q^{\prime },q⟩\cup t_2$, respectively.

As $C$ is an induced cycle, at most one of $\overline{F_1},\overline{F_1^{\prime }}$ intersects the string of some vertex in $V(C)\setminus N_C[P_1]$. Without loss of generality, suppose that $\overline{F_1}$ does not intersect any string of $V(C)\setminus N_C[P_1]$. As $s_p$ does not intersect $t_1$, it is contained in the closed face $\overline{F_1}$ or in the closed face $\overline{F_1^{\prime }}$. If $s_p$ is contained in $\overline{F_1}$, we set $P:=P_1-\{v(t),v(t^{\prime })\}$ and $F:=F_1$, and proceed to the next paragraph. Otherwise, we observe that $s_p$ is contained in $\overline{F_2^{\prime }}$, and $\overline{F_2^{\prime }}$ does not intersect any string of $V(C)\setminus N_C[P_2]$. In which case we set $P:=P_2-\{v(t),v(t^{\prime })\}$ and $F:=F_2^{\prime }$.

At this point, we have all the requirements of the lemma except that some strings of $P$ may be in $W$. Let $P$ be $v_1,\mathrm{\dots },v_{\mathrm{\ell }}$ with $v_1$ a neighbor of $v(t)$, and $v_{\mathrm{\ell }}$ a neighbor of $v(t^{\prime })$. While there is some string $t^{\prime \prime }\in W$ with $v(t^{\prime \prime })=v_i\in V(P)$, we let $q^{\prime \prime }\in t^{\prime \prime }\cap \partial D$ and distinguish two cases. If $q,p,q^{\prime \prime }$ turn along $\partial D$ in the same direction as $q,p,q^{\prime }$, we set $t^{\prime }:=t^{\prime \prime }$ and $P:=v_1,\mathrm{\dots },v_{i-1}$. Otherwise we set $t:=t^{\prime \prime }$ and $P:=v_{i+1},\mathrm{\dots },v_{\mathrm{\ell }}$. (Note that $|V(P)|$ decreases by at least one in each case.) When we exit the while loop, $s:=t,s^{\prime }:=t^{\prime }\in W$, and the subpath $P$ of $C$ (now only made of strings of $V$) satisfy the lemma statement. A visual recap is provided by Figure 2. $◀$

Let $R[X]$ be the string representation of $G[X]$ obtained by keeping the strings of $R$ corresponding to vertices of $X$. Let $D_0$ be the topological disk whose boundary is the boundary of the infinite face in the arrangement $R[X]$. If $s(u_0)$ is contained in $D_0$, we draw $R$ on a sphere, place any arbitrary free point (i.e., not occupied by a string of $R$) of the face containing $s(u_0)$ in $R[X]$ at its North pole, and consider the stereographic projection of this string representation. The latter is such that $s(u_0)$ is on the infinite face of the string arrangement $R[X]$. Thus we can in fact assume that $s(u_0)$ is not contained in $D_0$.

Note that every string of $R[X]$ is contained in $D_0$, and apart from those of $L_{i-1}\cup L_{i+1}\cup X$ no string of $R$ intersects $\partial D_0$. Let $D\supset D_0$ be a very slightly augmented topological disk such that $\partial D_0\subset D\setminus \partial D$, the property that no string outside $L_{i-1}\cup L_{i+1}\cup X$ intersects $\partial D$ is preserved, no intersection of two strings of $R$ lies on $\partial D$, and, for any point $q\in \partial D$, no string of $R$ intersects $\partial D$ at $q$ without crossing it at $q$. We observe that every string of $L_{i-1}$ with a neighbor in $V(X)$ intersects $\partial D$, and that every vertex of $X$ has a neighbor in $L_{i-1}$.

Let $R_H$ be the set of strings formed by $D\cap R[(L_{i-1}\cap N_G(V(X)))\cup V(X)]$, and $H$ its intersection graph. Every vertex of $X$ corresponds to a single vertex in $H$, whereas each vertex of $L_{i-1}\cap N_G(V(X))$ may split in several strings in $H$ as the corresponding string in $R$ may enter and exit $D$ several times. However, the strings of $R_H$ that correspond to the same vertex in $L_{i-1}\cap N_G(V(X))$ are pairwise non-intersecting and thus they form an independent set in $H$. Fix an arbitrary vertex $w\in L_{i-1}\cap N_G(V(X))$. Let $X_j$ be the subset of vertices of $X$ at distance exactly $j$ from $w$ in $H$. Again, $X_1,X_2,\mathrm{\dots }$ partition $X$. By the previous remarks, it is sufficient to show that that for any positive integer $k$, the graph $G[X_k]=H[X_k]$ is bipartite. We fix $k$, and show this fact in the next section.

Let $G$ be the input graph, given along with a representation. The algorithm has three phases.

We initialize $X=\mathrm{\varnothing }$. If $G$ contains an odd cycle of length at most 11, we include all its vertices into $X$ and remove them from the graph. We repeat this step exhaustively; clearly this can be done in polynomial time. Let $G^{\prime }$ be the graph obtained after the last iteration of the process.

We call the algorithm from Theorem 14 on the graph $G^{\prime }$ in order to obtain three sets $V_0,V_{1/2}$, and $V_1$. We denote $Y=V_1$ and $G^{\prime \prime }=G^{\prime }[V_{1/2}]$. Note that $G^{\prime \prime }$ is a string graph with odd girth larger than 11 and the representation of $G^{\prime \prime }$ can be easily obtained from the representation of $G$ by removing objects corresponding to vertices in $V(G)\setminus V(G^{\prime \prime })$.

We apply the algorithm from Theorem 2 to find a proper coloring of $G^{\prime \prime }$ with at most 8 colors. Let $c$ be the color that appears most frequently, and let $Z$ be set of vertices of $G^{\prime \prime }$ not colored $c$. Clearly $|Z|⩽\frac{7}{8}|V(G^{\prime \prime })|$, so $|V(G^{\prime \prime })|⩾\frac{8}{7}|Z|$. The algorithm returns $Q=X\cup Y\cup Z$.

First, let us argue that $Q$ is indeed a vertex cover. Since $X\subseteq Q$, it is enough to show that $Q\cap V(G^{\prime })=Y\cup Z$ is a vertex cover of $G^{\prime }$. Note that by the first property in Theorem 14 and since $V_1=Y$, all edges of $G^{\prime }$ not contained in $G^{\prime \prime }$ are covered by $Q$. So we are left with showing that $Q\cap V(G^{\prime \prime })=Z$ is a vertex cover of $G^{\prime \prime }$. This is clearly true, as the complement of $Z$ in $G^{\prime \prime }$ is an independent set (of color $c$).

Now let us analyze the approximation factor. Let $S$ be an optimum solution, i.e., a vertex cover of $G$ of size $\mathrm{𝗏𝖼}(G)$. Note that for each odd cycle $C$ removed in the first phase, $S\cap C$ must contain at least $\frac{|C|}{2}$ vertices in order to cover all the edges of $C$. As each removed cycle has at most 11 vertices, we conclude that $|S\cap X|⩾\frac{6}{11}|X|$.

Note that $S^{\prime }\setminus X$ is a vertex cover of $G^{\prime }$. By the third property in Theorem 14 we observe that $Y=V_1\subseteq S$, and so $S\setminus (X\cup Y)$ is a vertex cover of $G^{\prime \prime }$. By the second property in Theorem 14 we obtain that $|S\setminus (X\cup Y)|⩾\frac{1}{2}|V(G^{\prime \prime })|$.

Summing up, we obtain

which means that $|Q|⩽\frac{11}{6}|S|=\frac{11}{6}\mathrm{𝗏𝖼}(G)$. This completes the proof. $◀$

The proof above is easily adapted to show Theorem 5. The first two phases remain unchanged. Let $𝒞$ be the family of odd cycles found in phase one and let $Y$ be the set found in phase two. Once we reach phase three, we do not call the coloring algorithm on $G^{\prime \prime }$, as its running time might not be polynomial in $|V(G)|$. Instead, we check if ${\sum }_{C\in 𝒞}\lceil |V(C)|/2\rceil +|Y|+|V(G^{\prime \prime })|/2>k$ and, if so, we reject the instance. Note that the sum in the expression above is a lower bound on $\mathrm{𝗏𝖼}(G)$, so this step is correct. Otherwise, we accept the instance. The approximation guarantee is estimated as in the proof of Theorem 1.