Gaétan Berthe

Marin Bougeret

Daniel Gonçalves

Jean-Florent Raymond

Subexponential parameterized algorithms for cycle-hitting problems in contact and intersection graphs of segments

Keywords: 2012 ACM Subject Classification Mathematics of computing → Graph algorithms; Theory of computation → Fixed parameter tractability intersection graph of segments, subexponential FPT algorithms, cycle-hitting problems, bidimensionality, neighborhood complexity Digital Object Identifier 10.4230/LIPIcs

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In this paper we consider three fundamental NP-hard cycle-hitting problems, namely Triangle Hitting (TH), Feedback Vertex Set (FVS), and Odd Cycle Transversal (OCT) where, given a graph G and an integer k, the goal is to decide whether G has a set of at most k vertices hitting all its triangles (resp. cycles for FVS, and odd cycles for OCT). We consider these problems from the perspective of parameterized complexity, where the

Subexponential parameterized algorithms in sparse graphs

Let us start with the bidimensionality theory, which gives an explanation on the so-called square root phenomenon arising for planar and H-minor free graphs [START_REF] Erik D Demaine | Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs[END_REF] for bidimensional 1problems, where a lot of graph problems admit ETH-tight 2 O( √ k) n O (1) algorithms. What we call a graph parameter here is a function p mapping any (simple) graph to a natural number and that is invariant under isomorphism. The classical win-win strategy to decide if p(G) ≤ k for a minor-bidimensional2 parameter (like p = fvs, the size of a minimum feedback vertex set of G) is to first reduce to the case where ⊞(G) = O( √ k) (where ⊞(G) denotes the maximum k such that the (k, k)-grid is contained as a minor in G), and then use an inequality of the form tw(G) ≤ f (⊞(G)) to bound the treewidth obtained through the following property.

▶ Definition 1 ([2]). Given c < 2, a graph class G has the subquadratic grid minor property for c ( SQGM for short), denoted G ∈ SQGM (c), if tw(G) = O(⊞(G) c ) for all G ∈ G. We write G ∈ SQGM if there exists c < 2 such that G ∈ SQGM (c).

While in general every graph G satisfies the inequality tw(G) ≤ ⊞(G) c for some c < 10 [START_REF] Chuzhoy | Towards tight (er) bounds for the excluded grid theorem[END_REF], the SQGM property additionally require that c < 2. Thus, for any G ∈ SQGM (c) and G ∈ G such that ⊞(G) = O( √ k), we get tw(G) ≤ ⊞(G) c = O k c/2 = o(k). For instance planar graphs and more generally H-minor free graph [START_REF] Erik | Linearity of grid minors in treewidth with applications through bidimensionality[END_REF] are known to have a treewidth linearly bounded from above by the size of their largest grid minor. In other words, these classes belong to SQGM [START_REF] Bafna | A 2-approximation algorithm for the undirected feedback vertex set problem[END_REF].

The conclusion is that the SQGM property allows subexponential parameterized algorithms for minor-bidimensional problems (if the considered problem has a 2 O(tw(G)) n O(1)time algorithm) on sparse graph classes. Notice that these techniques have been extended to contraction-bidimensional problems [START_REF] Baste | Contraction bidimensionality of geometric intersection graphs[END_REF].

Extending the results to geometric graphs

Consider now a geometric graph class G, meaning that any G ∈ G represents the interactions of some specified geometric objects. We consider here (Unit) Disk Graphs which correspond to intersection of (unit) disks in the plane, d-DIR graphs (where the vertices correspond to segments with d possible slopes in R 2 ), and contact segment (where each vertex corresponds to a segment in R 2 , and any intersection point between two segments must be an endpoint of one of them). We refer to Section 2.2 for formal definitions. Classes of geometric graphs represented in the plane form an appealing source of candidates to obtain subexponential parameterized algorithms as there is an underlying planarity in the representation. However these graphs are no longer sparse as they may contain large cliques, and thus cannot have the SQGM property. Indeed, if G is a clique of size a, then tw(G) = a-1 but ⊞(G) ≤ |G| = √ a. To overcome this, let us introduce the following notion.

▶ Definition 2. Given a graph parameter p and a real c < 2, a graph class G has the almost subquadratic grid minor property for p and c (G ∈ ASQGM (c)/p) if there exists a function f such that tw(G) = O(f (p(G)) ⊞(G) c ). We say that G ∈ ASQGM/p if there exists c < 2 such that G ∈ ASQGM (c)/p. This notion was used implicitly in earlier work (e.g., [START_REF] Grigoriev | Bidimensionality of geometric intersection graphs[END_REF]) but we chose to define it explicitly in order to highlight the contribution f of the parameter p to the treewidth, which is particularly relevant when it can be shown to be small (typically, polynomial). Let us now explain how ASQGM can be used to obtain subexponential parameterized algorithms on geometric graphs.

It was shown in [START_REF] Fedorr V Fomin | Excluded grid minors and efficient polynomial-time approximation schemes[END_REF] that FVS can be solved in time 2 O(k 3/4 log k) n O (1) in map graphs, a superclass of planar graphs where arbitrary large cliques are possible, as follows. Let ω(G) denote the order of the largest clique in a graph G. The first ingredient is to prove that map graphs are ASQGM/ω, and more precisely that tw(G) = O(ω(G) ⊞(G)). Then, if ω(G) ≥ k ϵ for some ϵ, the presence of such large clique allows to have subexponential branchings (as a solution of FVS must take almost all vertices of a clique). When ω(G) < k ϵ , then the ASQGM property gives that tw(G) ≤ k ϵ ⊞(G) ≤ k 1 2 +ϵ (as before we can immediately answer no if ⊞(G) > O( √ k)). By carefully choosing ϵ they obtain the mentioned running time. The same approach also applies to unit disk graphs and has since been improved to 2 √ k log k n O (1) in [START_REF] Fedor V Fomin | Finding, hitting and packing cycles in subexponential time on unit disk graphs[END_REF]

using a different technique.

There is also a line of work aiming at establishing ASQGM property for different classes of graphs and parameters, with for example [START_REF] Grigoriev | Bidimensionality of geometric intersection graphs[END_REF] proving that [START_REF] Bafna | A 2-approximation algorithm for the undirected feedback vertex set problem[END_REF] string graphs are ASQGM when the parameter p is the number of times a string is intersected (assuming at most two strings intersect at the same point), and that (2) intersection graphs of "fat" and convex objects are ASQGM when the parameter p(G) is the minimal order of a graph H not subgraph of G (generalizing the degree when H is a star).

Extending the results for TH and FVS to geometric graphs classes not ASQGM/ω.

A natural next step for FVS and TH is to consider classes that are not ASQGM/ω. Observe (see Figure 1) that neither disk graphs, 2-DIR or contact 2-DIR graphs are in ASQGM/ω, and thus constitute natural candidates. New ideas allowed the authors of [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF] to obtain subexponential parameterized algorithms on disk graphs for, in particular, TH, FVS and OCT. The first idea is a preprocessing step (working on general graphs) which given an input (G, k) first reduces to the case where we are given a set M such that |M | = O(k 1+ϵ ), G -M is a forest, and for any v ∈ M , N (v) \ M is an independent set (see Corollary 16).

The second idea is related to neighborhood complexity which, informally, measures the number of ways the vertices of G -X connect to the vertices of X for every vertex set X (see Definition 34 for a formal definition). The following theorem is formulated using clique number instead of ply (the maximum number of disks containing a fixed point), but it is known [START_REF] Bonamy | Eptas for max clique on disks and unit balls[END_REF] that these two values are linearly related in disk graphs. It holds that: From left to right, a disk graph, a 2-DIR graph, and a contact 2-DIR graph. In these graphs (where the left one is from [START_REF] Fedorr V Fomin | Excluded grid minors and efficient polynomial-time approximation schemes[END_REF]), ω(G) is constant, tw(G) ≥ t (where t = 3 here) as it contains Kt,t as a minor, ⊞(G) = O( √ t) as they have a feedback vertex set of size at most t.

▶ Theorem 3 (Theorem 1.1 in [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF]). Disk graphs with bounded clique number have linear neighborhood complexity.

For TH, these two ideas are sufficient to obtain a subexponential parameterized algorithm. For FVS, [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF] provide the following corollary.

▶ Corollary 4 (Corollary 1.1 in [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF] restricted to FVS). Let G be a disk graph with a (nonnecessarily minimal) feedback vertex set M ⊆ V (G) such that for all v ∈ M , N (v) \ M is an independent set, and such that for

all v ∈ V (G) \ M , N (v) \ M is non-empty. Then, the treewidth of G is O( |M |ω(G) 2.5 ).
As they use this corollary after a branching process reducing the clique number to k ϵ and as their (approximated) feedback vertex set M has size |M | = k 1+ϵ ′ , they obtain a sublinear treewidth and thus a subexponential parameterized algorithm for FVS (and several variants of FVS) running in time 2 O(k 13/14 log k) n O (1) .

Subexponential parameterized algorithms via kernels

Let us finally point out that another approach to obtain 2 o(k) n O (1) algorithms is to obtain small kernels (meaning computing in polynomial time an equivalent instance (G ′ , k ′ ) with |G ′ | typically in O(k)), and then use a 2 o(n) time algorithm. For FVS such a 2 o(n) -time algorithm is known in string graphs from [START_REF] Bonnet | Optimality program in segment and string graphs[END_REF] or [START_REF] Novotná | Subexponential-time algorithms for finding large induced sparse subgraphs[END_REF], but as far as we are aware, the existence of a linear kernel in this graph class is currently open.

Our contribution

Our objective is to study the existence of subexponential parameterized algorithms for TH and FVS mainly in 2-DIR, K t,t -free d-DIR (for t and d constants), and contact segment.

Negative results.

The first interesting difference between disk graphs and d-DIR graphs is that Theorem 3 (about the linear neighborhood complexity) no longer holds for d-DIR graphs, because of the presence of large bicliques. Thus, it seems that K t,t is an important subgraph differentiating the two settings and this fact is confirmed by our first results (recall that TH admits subexponential parameterized algorithms in disk graphs).

▶ Theorem 5. Assuming the ETH, there is no algorithm solving TH, and OCT in time 2 o(n) on n-vertex 2-DIR graphs.

This result was already proved for OCT in [START_REF] Okrasa | Subexponential algorithms for variants of the homomorphism problem in string graphs[END_REF] where the authors also provide algorithmic lower bounds for homomorphisms problems in string graphs.

Our second negative result is the following, whose 2 o( √ n) lower-bound matches those known for the same problems in planar graphs [START_REF] Cai | On the existence of subexponential parameterized algorithms[END_REF].

▶ Theorem 6. Under the Exponential Time Hypothesis, the problems TH, OCT, and FVS cannot be solved in time

2 o( √ n) on n-vertex K 2,2 -free contact 2-DIR graphs.
Positive results for FVS.

Notice first that Corollary 4 does not hold in 2-DIR, for example in the second graph of Figure 1, where M is the set of vertical segments. Thus, there is no hope to directly apply the approach of [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF] to obtain subexponential parameterized algorithm for FVS in 2-DIR.

Whether such algorithms exist is a natural open question. As a first step toward it, we consider the case of contact segment graphs. The motivation behind this class is that contact segment with axis parallel segments is a special case of 2-DIR, and that our technique can even handle contact segment (with arbitrary segments, which is incomparable with 2-DIR). Moreover, observe that the techniques of Section 1.2 do not apply here as contact segment does not belong to ASQGM/ω (Figure 1). This motivates our first approach of Section 3.1, where we first prove that contact segment belongs to ASQGM/(ω•d ∆ ) (where d ∆ is a suitable graph parameter that we introduce). Then, instead of following the classical approach which would be to branch to decrease ω and d ∆ , we use the preprocessing phase of [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF] (Corollary 16) to reduce to a graph with treewidth o(k). This leads to the following result. 1) in contact segment graphs, even when no representation is given.

▶ Theorem 7. FVS can be solved in time 2 O(k 7/8 •log k) n O(
Then, we develop in Section 3.2 another approach (which also uses, as a first step, Corollary 16 from [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF]) to improve the running time of the previous theorem. Informally, we reduce the instance to a K t,t -free graph H with |H| ≤ k 1+ϵ for t = k ϵ ′ . This allows us to use a result of [START_REF] Lee | Separators in Region Intersection Graphs[END_REF] on the treewidth of K t,t -free string graphs, and obtain again a treewidth in o(k). This approach leads to the following. 1) in contact segment graphs, assuming a representation is given as input.

▶ Theorem 8. FVS can be solved in time 2 O(k 3/4 •log k) n O(
Notice that Corollary 4 might hold for contact segment graphs however it is not clear that this would lead to an improvement in the time complexity above. We point out that the existence of a 2 o(k) n O (1) algorithm for FVS on 2-DIR graph is left open.

Positive results for TH.

In Section 4.2 we observe that, for any hereditary graph class with sublinear treewidth, the branching step in Corollary 16 directly leads to a subexponential parameterized algorithm for TH. This implies the following statement for K t,t -free string graphs.

▶ Theorem 9. For every integer t there is a constant c t > 0 such that the following holds. There is an algorithm for TH in string graphs that runs on n-vertex instances with parameter k in time

2 ctk 2/3 log k n O(1) ,
where t is the minimum integer such that G is K t,t -free, even when neither t nor a string representation are given as input.

To provide bounds on the constant c t in the case of d-DIR graphs, we prove the following statement on the neighborhood complexity that may be of independent interest. ▶ Lemma 10. For every integer t > 0, the class of K t,t -free d-DIR graphs has linear neighborhood complexity with ratio O(d • t 3 • log t).

▶ Lemma 11. The class of contact segment graphs has linear neighborhood complexity.

This leads to the the following improved running time for TH in K t,t -free d-DIR and contact segment.

▶ Corollary 12.

There is an algorithm that solves TH in time 1) in contact segment even when no representation is given.

2 O(k 2/3 log k•t 2 log t• √ d) n O(1) in K t,t -free d-DIR graphs, 2 O(k 7/9 log 3/2 k) n O(

Preliminaries

Basics

In this paper logarithms are binary and all graphs are simple, loopless and undirected. Unless otherwise specified we use standard graph theory terminology, as in [START_REF] Diestel | Graph theory 3rd ed[END_REF] for instance. Given a graph G, we denote by ω(G) the maximum order of a clique in G, and given

X ⊆ V (G), by G[X] the subgraph induced by X, and by G -X the graph G[V (G) \ X]. We denote by d G (v) the degree of v ∈ V (G), or simply d(v) when G is clear from the context.
We denote by ⊞(G) the maximum k such that the (k, k)-grid is contained as a minor in G. We consider the following three problems denoted Triangle Hitting (TH), Feedback Vertex Set (FVS), and Odd Cycle Transversal (OCT), where given as input a graph G and an integer k, we have to decide if there exists a set X ⊆ V (G) with |X| ≤ k such that G -X has no triangle, no cycle, or no odd cycle, respectively. We denote by tw(G) the treewidth of G, and say that a graph class G has sublinear treewidth if for some δ ∈ [0, 1) there is a function f (n) = O(n δ ) such that every graph G ∈ G satisfies tw(G) ≤ f (|G|). A prominent class of graphs that has sublinear treewidth is that of planar graphs. A graph class is said hereditary if for any graph G in the class, all its induced subgraphs are also part of the class.

Graph classes

In this article, we are mainly concerned with geometric graphs described by the intersection or contact of objects in the Euclidean plane. We focus our attention in particular on non-fat objects in the plane, like strings (a.k.a. Jordan arcs) or segments. The class of intersection graphs of strings (resp. segments) is called string graphs (resp. segment graphs). d-DIR graphs is a subset of segment graphs where the segments have at most d different slopes; in particular, for 2-DIR graphs we assume the segments to be axis-parallel. These graph classes admit subclasses, called contact, where the representations should not contain crossings. In these representations, two strings either intersect tangentially, or they intersect at a string endpoint. In a segment contact representation, any point belonging to two segments must be an endpoint of at least one of these segments. If a point belongs to several strings or segments, the above property must hold for any pair of them.

Preliminary branching steps

This section describes the preprocessing routines used by our algorithms. We first consider the branching step allowing to reduce cliques larger than a chosen size p (where typically p = k ϵ ). Informally, for any algorithmic problem where a solution S must intersect all triangles (such as the three problems we consider), finding a clique K of size at least p (assuming we can do it in polynomial time) and branching to guess the at most 2 vertices of K that S avoids leads to a recursion of the type

f (k) = p 2 f (k -(p -2)), implying that f (k) = 2 O( k p log p)
. This folklore preliminary step is formalized in the following lemma, originally formulated in [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF] for disk graphs and re-stated here for any graph class where the maximum clique can be approximated in polynomial time, as it remains trivially true in any such graph class.

▶
1. For any (G ′ , k ′ ) ∈ C, G ′ is an induced subgraph of G, ω(G ′ ) ≤ p, and k ′ ≤ k.

(G, k) is a yes-instance if and only if there exists

(G ′ , k ′ ) ∈ C which is a yes-instance.
Proof. The proof is immediate from Lemma 13 by associating to any (D, U, K) ∈ Y a pair

G ′ = G -D, k ′ = k -|D|. ◀
Our algorithms rely on the following routine previously used in the context of disk graphs [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF].

▶ Lemma 15 ([23, Lemma 6.5]). There is a 2 O( k λ log k) • n O(1) -time algorithm that, given a n-vertex graph G, λ, k ∈ N, and a set X ⊆ V (G) such that G -X is triangle-free, returns a collection Z ⊆ {(D, U, Z) : D, U ⊆ X, D ∩ U = ∅, and Z ⊆ V (G) \ X} of size 2 O( k λ log k)
and such that:

1. for every (D, U, Z) ∈ Z, |Z| ≤ 2(k + λ|X \ D|) and for every v ∈ V (G) \ D, N (v) \ (X ∪ Z)
is an independent set; 2. for every S ⊆ V (G) of size at most k such that G -S is triangle-free, there exists a unique (D, U, Z) ⊆ Z such that D ⊆ S and S ∩ U = ∅.

▶ Corollary 16. Let Π be FVS or TH. There exists a 2 O( k λ log k) n O(1) -time algorithm that, given an instance (G, k) of Π and an integer λ, returns a collection

C of size 2 O( k λ log k) of tuples (G ′ , M, k ′ ) such that: 1. For any (G ′ , M, k ′ ) ∈ C, (G ′ , k ′ ) is an instance of Π where G ′ is an induced subgraph of G, and k ′ ≤ k. 2. |M | ≤ 11λk, G -M is triangle-free (when Π =TH)
or is a forest (when Π =FVS), and for any v ∈ M , N (v) \ M is an independent set.

(G, k) is a yes-instance if and only if there exists

(G ′ , M, k ′ ) ∈ C such that (G ′ , k ′ ) is a yes-instance.
Proof. Let (G, k) be an instance of Π and an let λ ∈ N. As both FVS and TH admit polynomial 3-approximation [START_REF] Bafna | A 2-approximation algorithm for the undirected feedback vertex set problem[END_REF][START_REF] Becker | Optimization of pearl's method of conditioning and greedylike approximation algorithms for the vertex feedback set problem[END_REF], compute first in polynomial time a 3-approximation X.

If |X| > 3k then we can define C as a singleton containing a dummy no-instance, and thus we now assume that |X| ≤ 3k. Observe that for both problems, G -X is triangle-free, and thus we can use Lemma 15 to obtain the claimed collection Z. We define C as follows. For any (D,

U, Z) ∈ Z, define G ′ = G -D, k ′ = k -|D|, M = (X \ D) ∪ Z.
First and third property are straightforward. Let us consider the second property. As X was a solution to Π and X ⊆ M , we get that G -M is triangle free (when Π =TH) or is a forest (when Π =FVS), and

|M | ≤ |X| + |Z| ≤ 3k + 2(k + 3λk) ≤ 11λk. Item 1 of Lemma 15 implies that for any v ∈ M , N (v) \ M is an independent set. ◀ 3
Positive results for Feedback Vertex Set 3.1 A subexponential FPT algorithm for contact segment graphs via ASQGM

Proving ASQGM

The distance bewtween two vertices of a graph is the minimum length (in number of edges) of a path linking them and the diameter of a graph is the maximum distance between two of its vertices. In order to show ASQGM we use the framework of [START_REF] Baste | Contraction bidimensionality of geometric intersection graphs[END_REF] that we recall now.

▶ Definition 17 (Contractions [START_REF] Baste | Contraction bidimensionality of geometric intersection graphs[END_REF]). Given a non-negative integer c, two graphs H and G, and a surjection σ : V (G) → V (H) we write H ≤ c σ G if for every x ∈ V (H), the graph G[σ -1 (x)] has diameter at most c and for every x, y ∈ V (H), xy ∈ E(H) ⇐⇒ G[σ -1 (x) ∪ σ -1 (y)] is connected. We say that H is a c-diameter contraction of G if there is a surjection σ such that H ≤ c σ G and we write this H ≤ c G. Moreover, if σ is such that for every x ∈ V (H), |σ -1 (x)| ≤ c ′ , then we say that H is a c ′ -size contraction of G, and we write H ≤ (c ′ ) G. If there exists an integer c such that H ≤ c G, then we say that H is a contraction of G.

▶ Definition 18 ((c 1 , c 2 )-extension [START_REF] Baste | Contraction bidimensionality of geometric intersection graphs[END_REF]). Given a class of graph G and two non-negative integers c 1 and c 2 , we define the (c 1 , c 2 )-extension of G, denoted by G (c1,c2) , as the class containing every graph H such that there exist a graph G ∈ G and a graph J that satisfy G ≤ (c1) J and H ≤ c2 J.

See Figure 2 for an illustration of the above definitions.

J G ∈ G H ∈ G (c1,c2) c 1 -size contraction c 2 -diameter contraction v Figure 2
Left: a graphical representation of the definition of G (c 1 ,c 2 ) , adapted from [START_REF] Baste | Contraction bidimensionality of geometric intersection graphs[END_REF]. Right: a representation B where the non-trivial contact points of v, the red horizontal segment, are circled in blue, and d B ∆ (v) = 3. Vertices of N B ∆ (v) are depicted in green.

XX:9

Our proofs will rely on the following result, that appears implicitly in the proof of Theorem 15 of [START_REF] Baste | Contraction bidimensionality of geometric intersection graphs[END_REF].

▶ Lemma 19 ([2]). For every integers c 1 , c 2 and G ∈ P (c1,c2) , with P the class of planar graphs, we have tw

(G) = O(c 1 • c 2 ⊞(G)).
We will show that contact segment graphs have the ASQGM property involving a parameter that we define now.

▶ Definition 20 (non-trivial contact points, d ∆ , End, N ∆ ). For a contact segment graph G with representation B and a vertex v ∈ V (G), we call non-trivial contact point of the segment of v any point of that segment that is not an endpoint and where at least two other segments intersect. 3We denote by d B ∆ (v) the number of non-trivial contact points of v, and

d B ∆ (G) = max v∈V (G) d B ∆ (v). Moreover we define d ∆ (G) = min B d B ∆ (G)
, the minimum being taken over all contact segment representation B of G. Given point p of the plane, we denote by End B (p) the set of vertices whose segments end in p. For a vertex v,

N B ∆ (v) = p End B (p)
, where the union is on all the non-trivial contact points p of v. When B is clear from context we drop the superscript in the notation.

See Figure 2 for an illustration of these definitions on an example. Notice that for any non-trivial contact point p of v, | End(p)| ≥ 2 and End(p) ∪ {v} induces a complete graph. We use Lemma 19 to prove the following result.

▶ Theorem 21. For every contact segment graph G we have tw

(G) = O(ω(G) • (d ∆ (G) + 1) • ⊞(G)).
Proof. Let G be a contact segment graph. We will prove that

G ∈ P (ω(G),2•d ∆ (G)+2) . Let B be a contact segment representation of G such that d B ∆ (G) = d ∆ (G).
From this representation, we define a planar graph J (see Figure 3) whose vertex set is partitioned into three sets V E , V ∆ , and V s as we describe now. For each segment v in B, we create: one vertex in V E for each of the two endpoints of v, one vertex in V ∆ for each non-trivial contact point of v, one vertex in V s for each maximal subsegment of v without non-trivial contact points.

Let us now define the edges of J. We start by adding, for each segment v of B, a path starting at an endpoint of v and then (following their order along v) alternating with the vertices of V s and the vertices of V ∆ associated to v, until reaching the other endpoint of v. We say that this path in J is associated to the segment v. Then, for every pair s 1 , s 2 of segments in contact, we distinguish 3 cases:

1. if the two segments are in contact with their endpoints, then we add an edge between the vertices associated to these endpoints; 2. if an endpoint of s 1 is in contact with an inner point of s 2 , and it is the only segment with this contact point, then we add an edge between the vertex associated to this endpoint of s 1 and the vertex corresponding to the subsegment of s 2 where the contact point is;

Figure 3 A contact segment representation of a graph (top left), the constructed graph J (top right) for the proof of Theorem 21 and the associated planar graph H (bottom). Vertices of J are depicted in black for VE, red for V ∆ , and green for Vs. Edges of J depicted in black are the edges added first to obtain an induced path between vertices associated to the same segment. Edges depicted in blue correspond to edges added in Case 2. For readability we did not draw the edges of the black and red-back cliques but instead represented them with black (resp. red) curves around their vertices.

3.

if an endpoint of s 1 is in contact with a non-trivial contact point of s 2 , then we add an edge between the vertex associated to this endpoint of s 1 and the vertex corresponding to the non-trivial contact point in s 2 .

This completes the definition of J. Observe that for any ℓ-clique K in J with ℓ ≥ 3, either K ⊆ V E , which we call a black clique (corresponding to the case where ℓ segments share the same endpoint), or |K ∩ V E | = ℓ -1 and |K ∩ V ∆ | = 1, which we call a red-black clique (corresponding to a non-trivial contact point, where ℓ -1 segments share the same endpoint, which is in the interior of the last segment of the clique).

Let us now show how we can contract vertices in J to either obtain G or a planar graph. First, if we contract in J the paths associated to each segment, we obtain the contact graph G. Let us now bound the diameter of this contraction. As we contract paths, we only need to compute the size of each contracted path. Observe that the path associated to each v ∈ G has 2 • d ∆ (v) + 3 vertices, as there are always two vertices in V E and one in V s , and then each inner non-trivial contact point of a segment creates one vertex in V ∆ and one in V s . This implies that this is a (2

• d ∆ (G) + 2)-diameter contraction.
If we now contract in J all black and red-black cliques, we obtain a graph H which is planar, as we can get a planar drawing of H from B. Contracted sets have size ω(G), so we get that G ∈ P (ω(G),2•d ∆ (G)+2) . Then, by Lemma 19, we obtain the claimed bound on tw(G). ◀

We point out that Theorem 21 cannot be improved in the sense that contact segment graphs are neither ASQGM/ω (see Figure 1) nor ASQGM/d ∆ (when for example G is a

XX:11

clique where all segments share a common point).

From the ASQGM property to subexponential FPT algorithms

In this section, we show how the ASQGM property of Theorem 21 can be used to deduce a subexponential parameterized algorithm for FVS in contact segment graphs.

We point out that the classical method to use an ASQGM property (typically of the form tw

(G) = O(ω(G) ⊞(G))) is to branch first to reduce to ω(G) = O(k ϵ ), implying then that tw(G) ≤ O(k 1/2+ϵ
), as for bidimensional problems we only need to consider the case where

⊞(G) = O( √ k). In our case where tw(G) = O(ω(G) • d ∆ (G) • ⊞(G))
, we can still branch to reduce ω(G), but branching to reduce d ∆ (G) seems difficult in subexponential time. Indeed, consider v with d ∆ (v) ≥ k ϵ . A typical branching step would be to either take v in the solution, or to take | End(p)| -1 segments among those in End(p), for any non-trivial contact point p of v. However, if now v is such that | End(p)| = 2 for any non-trivial contact point p of v, such branching does not lead to subexponential parameterized time. Thus, we rather rely on the following lemma.

▶ Lemma 22. Consider a contact segment graph G with a set M ⊆ V (G) such that G-M is a forest, and such that for any vertex v ∈ M , the graph G[N (v)]-M is edgeless. Then for every positive integer τ , there exists a set B ⊆ V (G) of size O(|M |/τ ) such that d ∆ (G -B) ≤ τ .
Proof. Observe first that for a clique of size at least 3 in G, all but at most one of its vertices are in M as M is a feedback vertex set, and for any

v ∈ M , G[N (v)] -M is edgeless. Now, take v ∈ V (G) having a non-trivial contact point p. By the previous observation, | End(p) ∩ M | ≥ | End(p)| -1 ≥ 1 2 | End(p)| as | End(p)| ≥ 2. By summing over all non-trivial contact points of v we get | N ∆ (v) ∩ M | ≥ 1 2 | N ∆ (v)|. Let τ be a positive integer, we define B = {v ∈ V (G) : d ∆ (v) ≥ τ } the set of vertices with "big" d ∆ in G. By definition of non-trivial contact points we have | N ∆ (v)| ≥ 2d ∆ (v), and thus |B|τ ≤ v∈B d ∆ (v) ≤ v∈B | N ∆ (v)| 2 ≤ v∈B | N ∆ (v) ∩ M |.
Moreover, as for any v ∈ V (G) there are at most 2 vertices

u such that v ∈ N ∆ (u) (one for each endpoint of v), we get v∈B | N ∆ (v) ∩ M | ≤ 2|M
| by the pigeonhole principle (if the inequality was false, then there would exists v ∈ M with |{u 1) in contact segment graphs, even when no representation is given.

: v ∈ N ∆ (u)}| ≥ 3). This leads to |B| = O(|M |/τ ). ◀ ▶ Theorem 7. FVS can be solved in time 2 O(k 7/8 •log k) n O(
Proof. Given an instance (G, k) of FVS in contact segment, by pipelining Corollary 14 and Corollary 16 with p and k which will be chosen later, we generate 2

O(kp -1 log k)+O(kλ -1 log k) triples (G ′ , M, k ′ ) where (G ′ , k ′ ) is an instance of FVS in contact segment that we have to solve, with k ′ ≤ k. ▷ Claim 23. There is a polynomial time algorithm that, given (G ′ , k ′ ), correctly concludes either that ⊞(G ′ ) = O( √ k) or that (G ′ , k ′ ) is a no-instance.
Proof. Recall that we can compute a 2-approximation S for the FVS problem in polynomial time [START_REF] Bafna | A 2-approximation algorithm for the undirected feedback vertex set problem[END_REF], and if |S| > 2k ′ then we have a no-instance. So we can assume |S| ≤ 2k ′ . As a grid minor of

G ′ have size at most O( |S|), which gives ⊞(G ′ ) = O( √ k ′ ) = O( √ k). ⌟ So we can assume ⊞(G ′ ) = O( √ k). Let τ ≥ 1 to be chosen later. ▷ Claim 24. We have tw(G ′ ) = O max λτ -1 k, pτ √ k .
Proof. By Lemma 22 there exists a set B such that d ∆ (G-B) ≤ τ . By denoting G ′′ = G ′ -B and by Theorem 21 we have tw( 1) algorithm (see [START_REF] Cygan | Parameterized Algorithms[END_REF]), and by putting p = k ϵ1 , λ = k ϵ2 and τ = k ϵ3 , we get an overall complexity of 2 x n O (1) where

G ′′ ) = O(p • τ • ⊞(G ′′ )). Observe that ⊞(G ′′ ) ≤ ⊞(G ′ ) because G ′′ is a subgraph of G ′ . This gives tw(G ′′ ) = O(p • τ • √ k).
G ′ ) = O max λτ -1 k, pτ √ k . ⌟ Solving the FVS instance (G ′ , k ′ ) using a 2 O(tw(G ′ )) n O(
x = O(k 1-ϵ1 log k) + O(k 1-ϵ2 log k) + O(max k 1+ϵ2-ϵ3 , k 1/2+ϵ1+ϵ3 ). Taking ϵ 1 = ϵ 2 = 1 8
and ϵ 3 = 1 4 , we get the claimed complexity. ◀

A subexponential parameterized algorithm for contact segment via a reduction to string graphs

In this section we improve the running time of Theorem 7 using another approach where we first use Corollary 16, and then use the following lemma to reduce to a contact graph of strings which have small treewidth as we will see later.

▶ Definition 25. Given a contact segment representation, a Helly point is a point of the plane that is contained in at least 3 segments.

▶ Lemma 26. There is a polynomial time algorithm that, given an instance (G, k) of FVS, a representation of G as contact segment, and a set M ⊆ V (G) such that G -M is a forest, and such that for

any vertex v ∈ M the graph G[N (v)] -M is edgeless, returns an equivalent instance (G ′ , k ′ ) such that: G ′ is a contact graph of strings, k ′ ≤ k and |G ′ | = O(|M |), and ω(G ′ ) ≤ ω(G) + 2.
Proof. The equivalent instance will be defined using reduction rules. Before describing these rules, we define the set M ′ by adding to M every segment containing a Helly point (see Figure 4).

By construction: (a) For every v ∈ V (G) \ M ′ , the segment v does not contain a Helly point. We show that the set M ′ has similar properties as M :

▷ Claim 27. (b) |M ′ | ≤ 3|M |; and (c) G -M ′ is a forest.
Proof. We start with item (b). Clearly a Helly point corresponds to a clique of order 3 or more in G. By definition of M , the graph G[N (v)] -M is edgeless for every v ∈ M , so every such clique has all but at most one vertices in M . Besides, the Helly point is not an endpoint for at most one segment of the clique (otherwise G would not be contact segment). Therefore every Helly point is an endpoint of some segment in M . Each segment has at most two endpoints, so there are at most 2|M | Helly points in total. Since, at every such point there is at most one segment not in M (as already observed above), at most 2|M | segments are added to M when constructing

M ′ . Regarding item (c), since G -M ′ is a subgraph of G -M , it is also a forest. ⌟
Let us describe informally how we will reduce the instance. We do so by keeping M ′ and by reducing or fully deleting each connected component of G -M ′ , those being trees. In particular we have to shrink, through kernelization rules defined below, the size of connected component T of V (G) -M ′ (as they can be arbitrarily large, like the top part of T 2 in Figure 4 which is only attached to v ∈ M ). Then, on one side, we will bound the total size of connected components T of V (G) -M ′ such that |N (T ) ∩ M ′ | ≥ 3 (like T 2 ) by a planarity argument. One the other side, as there could be arbitrarily many components T such that 4), we need that kernelization rules also remove some of them.

|N (T ) ∩ M ′ | ≤ 2 (like T a 1 , T b 1 and T c 1 in Figure
Let us consider the following kernelization rules for FVS. Those are applied prioritizing the first rules. We omit the proofs of the first two folklore rules. (R1) Delete every vertex v with degree at most one, and maintain the parameter k. (R2) If there is an induced P 3 = uvw with d(v) = 2 and u, v / ∈ M ′ , delete v, add an edge uw, and maintain the parameter k. Rule (R2) is such that no multiple edge can be created, as u and w are non-adjacent. From now on, this rule implies that every vertex of degree two is either in M ′ , has both neighbors in M ′ , or is contained in a triangle.

(R3) If there are two vertices u, v with same neighborhood, N (u) = N (v), and such that this neighborhood consists of two adjacent vertices, delete v and maintain the parameter k.

Proof. (Safeness of R3) A minimal feedback vertex set can avoid any degree-two vertex x that is adjacent to a vertex of degree at least three. Indeed, every cycle passing through x also goes through this neighbor. So, before and after deleting v, we can assume that a minimal feedback vertex set contains at least one neighbor of N (u), and this neighbor is sufficient also to hit all the cycles going through v. So it is safe to delete v. ⌟ Proof.

P ℓ = x 1 . . . x ℓ in G -M ′ , with ℓ ≥ 4, such that d G-M ′ (x i ) ≤ 2 and N (x i ) ∩ M ′ ⊆ {v}, for all 1 ≤ i ≤ ℓ,
P ℓ = x 1 . . . x ℓ in G -M ′ , with ℓ ≥ 16, such that d G-M ′ (x i ) ≤ 2 and N (x i ) ∩ M ′ ⊆ {u, v}, for all 1 ≤ i ≤ ℓ,
(Safeness of R6) Let X = {u, v, x 1 , . . . , x ℓ }. Note that for any cycle C such that C ∩ X ̸ = ∅, either C ∩ {u, v} ̸ = ∅, or P ℓ ⊆ C.
So any feedback vertex set intersecting X on at least three vertices can be safely modified to include u and v. We consider from now on a feedback vertex set S intersecting X on at most 2 vertices.

By (R2) every vertex of P ℓ is adjacent to u or v. Thus, one of these two vertices has at least 8 neighbors in P ℓ . Assume it is v. As X contains four cycles intersecting only at v, a feedback vertex set avoiding v would intersect X on at least four vertices, a contradiction. Thus, v ∈ S.

By (R5) u has at least 4 neighbors in P ℓ so X \ {v} contains two cycles intersecting only on u. Thus, a feedback vertex set avoiding u would intersect X on at least three vertices (on v and on each of the cycles). Thus, we obtain u ∈ S. ⌟

The following rules deal with the connected components of G -M ′ . This subgraph being acyclic, these connected components are trees. Note that the leaves in these trees have degree at least two in G (by rule (R1)), so they are necessarily adjacent to vertices in M ′ .

(R7) If there is a vertex v ∈ M ′ and a connected component T in G -M ′ such that N (u) ∩ M ′ ⊆ {v} for every u ∈ V (T ), delete v and decrease the parameter k by one.

Proof. (Safeness of R7) As noted above, T is a tree. The rule (R1) does not apply on T , so T has at least two leaves and each are adjacent to v; in particular there is a cycle in

G[V (T ) ∪ {v}].
We can thus force v in the feedback vertex set. ⌟

The rule (R7) ensures that every connected component

T of G -M ′ is such that |N (T ) ∩ M ′ | ≥ 2, where N (T ) = (∪ v∈V (T ) N (v)) \ V (T ). Given two vertices u, v ∈ M ′ , let F u,v
be the subforest of G -M ′ obtained by keeping the connected components T such that N (T ) = {u, v}. A tree T in F u,v is said trivial if there is only one edge between T and u, and only one edge between T and v. Note that by the previous rules such trivial tree is just a single vertex. From now on, we have that for every u, v ∈ M ′ , the forest F u,v has at most 3 connected components. Let us now refer to the obtained graph and parameter as G ′ and k ′ , and note by construction that k ′ ≤ k. As all rules are safe, we know that (G ′ , k ′ ) is equivalent to (G, k), and thus it remains to decide (G ′ , k ′ ).

(R8) If there are vertices u, v ∈ M ′ , such that G[V (F u,v ) ∪ {u,
The graph G ′ is a contact graph of strings because in every rule, except (R2), we only delete vertices, while for (R2), one can draw a new string for u in the space left by the old strings of u and v. One should also notice that this operation does neither create a Helly point. This implies that G ′ and M ′ verify property (a). Note that (b) and (c) also hold for G ′ . Note also that ω(G ′ ) ≤ ω(G) + 2, as a clique in G ′ has at most two vertices not in M ′ , G -M ′ being acyclic, and as

G ′ [M ′ ] ⊆ G[M ′ ]. Let us now prove that V (G ′ ) has bounded size.
Notice that in the contact string representation of G ′ in hand, every string corresponding to a vertex in M ′ is actually a segment. Let us denote G * the contact graph obtained from this representation of G ′ by slightly shortening every end of a segment u ∈ M ′ that is in contact with another segment of M ′ . This results exactly in deleting all the edges inside M ′ , so G * [M ′ ] is edgeless. Note also that G * is a contact graph of strings with ply two (i.e. any point belongs to at most two strings), so it is planar.

To bound the size of

V (G ′ ) = V (G * ) the main difficulty is to establish that |T | ≤ 534 • |N (T ) ∩ M ′ |, for each connected component T of G -M ′ .
This is proved below as Lemma 28. Once this is established one has to consider the graph G * 2 with vertex set M ′ and such that uv is an edge if and only if there exists a non-empty forest F u,v in G ′ . Note that this graph being a minor of G * it is planar, and hence contains at most 3|M ′ | edges. One has also to consider G * >2 , the graph obtained from G * by contracting every connected component T of G -M ′ into a single vertex, and by then deleting every degree two vertex not in M ′ . Note that this graph is planar and bipartite, with vertex sets M ′ and X, and it is such that

deg G * >2 (v T ) ≥ 3, for each v T ∈ X. In such case we have that v T ∈X deg G * >2 (v T ) ≤ 6|M ′ |.
Indeed, this sum is at most twice the number of edges in the plane graph with vertex set M ′ and with an edge uv if G * >2 has an uv-facial walk of length two, the twice coming from the fact that an edge in this graph may appear because of at most two facial walks. Now, since

V (G ′ ) = M ′ ∪ (∪ u,v∈M ′ V (F u,v ) ∪ (∪ T V (T ))
, where the union on T is on all connected components of G ′ -M ′ such that |N (T ) ∩ M ′ | ≥ 3, we can bound V (G ′ ) as follows.

|G ′ | = |M ′ | + u,v∈M ′ |F u,v | + T ∈G-M with |N (T )∩M ′ |≥3 |T | ≤ |M ′ | + 3|M ′ | • max u,v∈M ′ |F u,v | + 534 • T ∈G-M with |N (T )∩M ′ |≥3 |N (T ) ∩ M ′ | ≤ |M ′ | + 3|M ′ | • (3 • 2 • 534) + 534 • 6|M ′ | ◀ ▶ Lemma 28.
With the notation of the proof of Lemma 26, for every connected component

T of G -M ′ we have |T | ≤ 534 • |N (T ) ∩ M ′ |.

Proof. Consider an arbitrary connected component

T of G -M ′ and let N (T ) ∩ M ′ = {v 1 , . . . , v d }, for some d ≥ 2.
Then, root T at an arbitrary vertex r. For any vertex v ∈ V (T ) denote by T v the rooted subtree of T rooted at v and let us denote by N T (v) the set

N (T v ) ∩ M ′ . Note that N T (v) ⊆ {v 1 , . . . , v d }. Two vertices u, v of T are said incomparable if u / ∈ T v and v / ∈ T u .
The graph G * being planar we have the following two properties. ▷ Claim 29. For any triple of incomparable vertices u, v, w of T , there is no pair i, j ∈ {1, . . . , d} such that {v i , v j } ⊆ N T (u), {v i , v j } ⊆ N T (v), and {v i , v j } ⊆ N T (w).

Proof. Indeed, otherwise contracting T u , T v , T w , and the rest of T on u, v, w, and r, respectively, these four vertices and the vertices v i and v j would form a K 3,3 minor in G * . ⌟ ▷ Claim 30. There are at most 3d incomparable vertices in T such that each of these vertices v has a distinct pair c v ∈ {1, . . . , d} 2 with c v ⊆ N T (v).

Proof. Indeed, otherwise one could construct a minor of G * , with vertex set {v 1 , . . . , v d } and more than 3d edges, which is impossible for a planar graph. ⌟ To bound the number of vertices of degree two (in T [I]), let us now cut each long path into order-16 subpaths whenever possible, and let us refer to these paths as the short paths. Each long path leading to at most one short path of order smaller than 16, these short paths contribute in total for at most 6d × 15 vertices in T [I]. Let us now bound the number of short paths of order exactly 16. By (R6), for every such short path P we have that |N (P ) ∩ M ′ | ≥ 3. This implies that the minor of G * obtained by contracting these short paths and keeping the vertices in {v 1 , . . . , v d } has at most 2d contracted vertices. Indeed, we have seen above that a bipartite plane graph with d vertices in one part and minimum degree 3 on the other part has at most 6d edges. Thus there are at most 2d vertices in the second part, and so there are at most 2d short paths of length 16. So in total the size of I is bounded by 6d + 6d + (6d × 15) + (2d

× 16) = 134d. ⌟ ▷ Claim 32. For every vertex v ∈ V (T ) \ I, we have that G ′ [N [v]
] is a triangle with one vertex in each of V (T ) \ I, I, and M ′ .

Proof. Consider a vertex v ∈ V (T ) \ I, and toward a contradiction suppose T v has more than one vertex. Note that every vertex of T v belongs to V (T ) \ I too. Let u be a leaf of

T v furthest from v. As |N T (v)| < 2, (R1) implies that |N T (u)| = 1.
Let us denote u ′ and w the neighbors of u in M ′ and in V (T ), respectively. Possibly w = v. By (R2) the vertices u ′ and w are adjacent. As w ∈ V (T ) \ I we have that N T (x) = {u ′ } for every vertex x ∈ V (T w ). If w has another son y ̸ = u, then this should also be a leaf in T (u being a furthest leaf), and N (y) = {u ′ , w} (for the same reasons as u). This is impossible by (R3), so u is the unique son of w and thus deg(w) = 3. Now (R4) leads to a contradiction, we thus have that v is a leaf of T . Furthermore, the same arguments as above (for u) imply that v has two neighbors, one neighbor in M ′ and one in I, and that these neighbors are adjacent.

⌟

We are now ready to complete the proof of the lemma. By Claim 31, the set I has size at most 134d, and thus the graph G * [I ∪ {v 1 , . . . , v d }] has at most 400d edges (this graph being planar). On the other hand, by Claim 32, every connected component of T -I is an isolated vertex whose neighborhood (in G * ) is isomorphic to K 2 (i.e., it has two neighbors that are adjacent). By (R3), there are at most one vertex in T -I per edge of G * [I ∪ {v [START_REF] Deniz | On contact graphs of paths on a grid[END_REF]), so in particular K 3,3 is not a contact graph of string. Therefore there is no induced K 3,3 in H, which implies that α A ≤ 2 or α B ≤ 2. In the following we assume that α A = 2 and α B ≥ 2. Let b 1 , b 2 ∈ B be non-adjacent.

We consider a maximal subset A ′ ⊆ A whose strings touch b 1 on the same side, and touch b 2 on the same side. This set has size at least 2ω, as there are at most 4ω strings in A touching b 1 or b 2 on their endpoints, and as the other strings can be partitioned into four sets according to the sides of b 1 and b 2 they reach these strings. If a string of A touches b 1 at several places and on distinct sides, consider an arbitrary side for the partition.

The segments in A ′ can be ordered a ′ 1 , . . . , a ′ 2ω , . . . so that a ′ i and a ′ j , with i < j do not intersect if j -i ≥ ω -1 (otherwise, all the segments in-between and b 1 would intersect and form a (ω + 1)-clique). Thus a ′ 1 , a ′ ω , and a ′ 2ω form an independent set, a contradiction to α A = 2. ◀

XX:18 Subexp. param. algo. for cycle-hitting problems in segments graphs

Preliminary branching steps and the previous reduction algorithm imply the following result.

▶ Theorem 8. FVS can be solved in time 2 O(k 3/4 •log k) n O (1) in contact segment graphs, assuming a representation is given as input.

Proof. Given an instance (G, k) of FVS in contact segment, by pipelining Corollary 14 with p = k ϵ1 and Corollary 16 with λ = k ϵ2 (for ϵ 1 , ϵ 2 which will be chosen later), we generate 2 O(k 1-ϵ 1 log k)+O(k 1-ϵ 2 log k) instances of FVS in contact segment graphs that we have to solve. For each such instance, by Lemma 26 we can reduce in polynomial time to an instance (G ′ , k ′ ) such that G ′ is a contact string graph with ω(G ′ ) ≤ k ϵ1 + 2 and |G ′ | ≤ O(k 1+ϵ2 ), where G ′ is K t,t -free for t = 12k ϵ1 + 24 by Lemma 33. By Corollary 43, we have that tw(G ′ ) ≤ O k 1+ϵ1+ϵ2 log k . Solving FVS using a 2 O(tw(G ′ )) n O(1) algorithm (see [START_REF] Cygan | Parameterized Algorithms[END_REF]), we get a running time in 2 x n O (1) where

x = O(k 1-ϵ1 log k) + O(k 1-ϵ2 log k) + O(k (1+ϵ1+ϵ2)/2 log 1/2 k).
Taking ϵ 1 = ϵ 2 = 1 4 , we get the claimed complexity. ◀

Notice in the proof of Theorem 8 that we could also chose ϵ 1 = 1, use Lemma 26 to reduce to |G ′ | ≤ O(k 1+ϵ2 ), and the algorithm in 2 O(n 2/3 log 3/2 (n)) of [START_REF] Bonnet | Optimality program in segment and string graphs[END_REF] for FVS on n vertex string graphs, but this would result in a worse running time.

Positive results for Triangle Hitting 4.1 A subexponential FPT algorithm in classes with sublinear separators

In this section we provide a subexponential parameterized algorithm for TH in graph classes with strongly sublinear separators (Theorem 39). For a graph G and a set X ⊆ V (G) we are interested in the number of ways the vertices of G -X connect to the vertices of X.

▶ Definition 34. If for a graph class G there is a constant c such that for every G ∈ G and every X ⊆ V (G), |{N (v) ∩ X : v ∈ V (G)}| ≤ c|X|, then we say that G has linear neighborhood complexity with ratio c.

▶ Definition 35 ([15]). We say that a hereditary graph class G has strongly sublinear separators if there is a function f : N → R with f (n) = O(n δ ) for some δ ∈ [0, 1) such that every G ∈ G has a balanced separator of order at most f (|G|).

Strongly sublinear separators and neighborhood complexity are linked by the following results. To avoid definitions that are otherwise irrelevant to this paper, we skip the definitions of polynomial and bounded expansion used in the next two results.

▶ Theorem 36 ([15]). Every graph class with strongly sublinear separators has polynomial expansion.

▶ Lemma 37 ([26]). If a graph class has bounded expansion, then it has linear neighborhood complexity.

We will also need the following connection to treewidth.

▶ Theorem 38 ([16]). If a hereditary graph class C has strongly sublinear separators with function f (n) = βn δ , then the treewidth of any n-vertex graph in G is at most 15βn δ .

The proof of the following result follows the same steps as the proof in [START_REF] Lokshtanov | Subexponential parameterized algorithms on disk graphs (extended abstract)[END_REF] for disk graphs, but as our statement is more general, we prefer to include it. ▶ Theorem 39. If G is a hereditary graph class that has strongly sublinear separators, then there is a subexponential time algorithm for TH. More precisely, if the size of the separators in G is f (n) = βn δ for some δ < 1, β > 0 and the ratio of neighborhood complexity is c, then the algorithm runs on n-vertex instances with parameter k in time (1) .

2 O(βγ δ c δ k 2δ/(1+δ) log k) n O
for some universal constant γ.

Notice that by Theorem 36 and Lemma 37, the ratio c as in the above statement is always defined for graph classes with strongly sublinear separators.

Proof of Theorem 39. Let α = 1-δ 1+δ . We first use Corollary 16 with λ = k α , and thus in 2 O(k 1-α log k) n O(1) time we generate the 2 O(k 1-α log k) instances (G ′ , M, k ′ ) as described in Corollary 16. Let us now describe how we solve these instances.

By definition of c the vertices of G ′ -M can be partitioned into at most c|M | classes V 1 , . . . , V r such that two vertices in the same class have the same neighborhood in M . For every i ∈ {1, . . . , r} we delete all but one vertex of V i , that we call v i . Let G ′′ be the obtained graph. In order to keep track of the deleted vertices we define a weight function

w : V (G ′′ ) → N as w(v i ) = |V i | for every i ∈ {1, . . . , r} and w(v) = 1 for every v ∈ M . The produced instance is (G ′′ , w, k ′ ); we call it a translation of the instance (G ′ , M, k ′ ).
Observe that it can be computed in polynomial time, and that it is an instance of Weighted Triangle Hitting.

▷ Claim 40. (G ′ , k ′ ) is a yes-instance or TH ⇔ (G ′′ , w, k ′ ) is a yes-instance of Weighted TH.
Proof. Observe first the property (P 1) that, as for any v ∈ M , N (v) \ M is an independent set, and M is a triangle hitting, any triangle ∆ of G ′ (or

G ′′ ) has |∆ ∩ M | ≥ 2.
Direction "⇐". Let S ′′ be a solution of (G ′′ , w, k ′ ). Observe that every vertex of S ′′ either belongs to M or is of the form v i for some i ∈ {1, . . . , r} (using the same notation as above). Let I ⊆ {1, . . . , r} be the set of integers such that S ′′ \ M = {v i : i ∈ I}. We define S ′ = (S ′′ ∩ M ) ∪ i∈I V i . By the definition of k ′ and w, we have |S ′ | ≤ k ′ . In order to show that S ′ is a triangle hitting set of G ′ , we assume toward a contradiction that G ′ -S ′ has a triangle ∆. If |∆ ∩ M | = 3 then ∆ would be a triangle in G ′′ -S ′′ , a contradiction, so by property (P 1) we have |∆ ∩ M | = 2, and thus let v i be the representative in G ′′ of the vertex in ∆ \ M . By construction of S ′ , this implies that v i / ∈ S ′′ , and even that ∆ ∩ S ′′ = ∅, a contradiction.

Direction "⇒". Let S ′ be a subset-minimal solution of (G ′ , k ′ ). Observe that for every i ∈ {1, . . . , r}, either andby property (P 1) it has its two other vertices in M . By definition of V i , every u ∈ V i is neighbor of these two vertices. So, as S ′ is a triangle hitting set, u ∈ S ′ . Let I = {i ∈ {1, . . . , r} : In remains now to solve such an instance (G ′′ , w, k ′ ) of Weighted Triangle Hitting. Let t = tw(G ′′ ). We first compute in 2 O(t) |G ′ | steps a tree decomposition of width O(t) (for instance using the approximation algorithm of Korhonen [START_REF] Korhonen | A single-exponential time 2-approximation algorithm for treewidth[END_REF]). We then solve the problem in 2 O(t) |G ′ | O (1) steps via a standard dynamic programming algorithm on the tree decomposition by observing that every triangle lies in some clique (as observed by Cygan et al. [START_REF] Cygan | Hitting forbidden subgraphs in graphs of bounded treewidth[END_REF] for the general problem of hitting cliques).

V i ⊆ S ′ or V i ∩ S ′ = ∅. Indeed, if v ∈ V i belongs to S ′ , by minimality of this set there is a triangle ∆ containing v in G ′ -(S ′ \ {v}),
S ∩ V i ̸ = ∅}. Let S ′′ = (S ′ ∩ M ) ∪ {v i : i ∈ I},
According to Corollary 16, |M | ≤ 11k 1+α so |G ′′ | ≤ 11(c + 1)k 1+α . Recall that G is hereditary and G ′′ is an induced subgraph of G ′ that is an induced subgraph of G, so G ′′ ∈ G. As G has strongly sublinear separators with bound f , by Theorem 38 the treewidth t of G ′′ is at most 15β|G ′′ | δ , so t ≤ 15βγ δ c δ • k (1+α)δ for some constant γ > 0. The number of instances generated by Corollary 16 is at most 2 O(k 1-α log k) so overall the running time is

2 O(βγ δ c δ •k (1+α)δ +k 1-α log k) • n O(1) ≤ 2 O(βγ δ c δ k 2δ/(1+δ) log k) • n O(1) , as claimed. ◀

Application to K t,t -free d-DIR, K t,t -free string graphs and contact segment

Theorem 39 from the previous section can be directly applied to K t,t -free string graphs. Indeed a straighforward consequence of the following results of Lee is that such graphs have strongly sublinear separators.

▶ Theorem 41 ([21]). m-edge string graphs have balanced separators of size O( √ m).

▶ Theorem 42 ([21]

). There is a constant c such that for every integer t > 0, every K Corollary 43 and Theorem 39 applied with δ = 1/2, β = O( √ t log t) and for c any bound on the neighborhood complexity (that is bounded from above by a function δ, according to Theorem 36 and Lemma 37) lead to the following result.

▶ Theorem 9. For every integer t there is a constant c t > 0 such that the following holds. There is an algorithm for TH in string graphs that runs on n-vertex instances with parameter k in time

2 ctk 2/3 log k n O(1) ,
where t is the minimum integer such that G is K t,t -free, even when neither t nor a string representation are given as input.

In K t,t -free d-DIR graphs we are able to provide a polynomial upper-bound on the constant c t of Theorem 9, that we explain now.

▶ Lemma 10. For every integer t > 0, the class of K t,t -free d-DIR graphs has linear neighborhood complexity with ratio O(d • t 3 • log t).

Proof. Let G be a K t,t -free d-DIR graph, and fix

M ⊆ V (G). Observe that |{N (v) ∩ M : v ∈ V (G)}| ≤ |M | + |{N (v) ∩ M : v ∈ V (G) \ M }|
, and thus we only have to prove that

|{N (v) ∩ M : v ∈ V (G) \ M }| = O(d • t 3 • log t|M |).

XX:21

Whenever two vertices of G -M have the same neighborhood in M , we delete one of them. For simplicity we also delete all vertices with no neighbors in M and call G ′ the obtained graph. We now focus on bounding the order of G ′ ; observe that this would straightforwardly translate to a bound on the number of neighborhoods in M of vertices of G -M .

For a d-DIR representation of G ′ , we consider that one of its direction is the horizontal. So in the following we say that a vertex of G ′ is horizontal if its segment in the representation is. For convenience the vertices with 0-length segments are considered as horizontal vertices.

Let M H denote the horizontal vertices of M and M C = M \ M H . Moreover we set A = V (G ′ ) \ M and define in the same way A H . As the horizontal direction was chosen arbitrarily, a bound of the size of A H multiplied by d would be a bound to the size of A. Towards this goal we further partition A H into two subsets: A H1 and A H2 with

A H1 = {v ∈ A H : N (v) ∩ M H ̸ = ∅} and A H2 = A H \ A H1 . ▷ Claim 44. |A H1 | = O(t 2 • log t • |M |).
Proof of Claim 44. We will bound |A H1 | by using special points of the plane contained in the horizontal segments of M . Let P H be the set of the endpoints of the M H segments and the points of intersection of a M H segment with a M C segment.

We denote by m M the number of edges of the graph

G ′ [M ]. The size of P H is at most 2|M H | + m M as intersections between segments correspond to edges in G ′ [M ], whose number is bounded by O(t • log t • |M |) in Theorem 42.
There are at most |P H | segments of A H1 which does not intersect any point of P H : those are the ones strictly included in a subsection of the horizontal segments of M split at the P H points. For the remaining points, which each intersect at least one point of P H , there cannot be more than 2t|P H | of them as otherwise by the pigeonhole principle there would be a point of P H contained in at least 2t segments. But then K 2t would be a subgraph of G, and so K t,t , contradicting our hypothesis. So overall we get

|A H1 | ≤ (2t + 1)|P H | ≤ (2t + 1)(2|M H | + m M ) = O(t 2 • log t • |M |).
⌟

We now want to bound the size of A H2 , the horizontal vertices of G -M which do not intersect a horizontal segment of M .

▷ Claim 45. |A H2 | = O(t 3 • log t • |M |).
Proof of Claim 45. Let us first remark that we can safely ignore the horizontal vertices of M as they have no neighbors in A H2 . To simplify the proof, we add a perturbation to the segments of the representation of G ′ , keeping the property that this is a d-DIR representation of G ′ but such that an intersection involves at most 2 different directions, and such that all the endpoints and the intersections between segments of M C have distinct ordinate. For achieving such perturbation, we extend the length of every segment of the representation of G ′ by a small amount. Moreover for each line that supports at least one segment, we move slightly the whole line to a near parallel line (ensuring the associated intersection graph remains the same). Once this perturbation done, we define a set of special points in the plane, P C , which are the endpoints of the M C segments and theirs intersections points with each other. The perturbation ensure that the P C points have distinct ordinates. Let denote p 1 , . . . , p k the points of P C ordered from top to bottom, and for 1 ≤ i ≤ k we denote L i the horizontal line containing the point p i . We now partition A H2 according to their position relatively to the (L i ) i lines: for 1 ≤ i ≤ k we denote by Z i the set of segments of A H2 whose neighborhood in M can be achieved by an horizontal segment above L i+1 but not by a segment on or above the line L i . (see Figure 5) Observe that:

L i-1 L i L i+1 p i-1 p i p i+1
Figure 5 Example for the construction of the family (Zi)i in the proof of Claim 45. The green segment would be part of the set Zi.

(Z i ) i is a partition of A H2 , as a segment that can be represented on one line L i will have a direction, either up or down, where it can be moved by a small amount without changing its neighborhood. In the zone between lines L i and L i+1 , there would be no endpoints of segments of M C , and segments of M C do not cross each other, which means they will have a constant left to right order. We will denote S i = {s 1 , . . . , s l } those segments enumerated from left to right . For a segment of Z i , its neighborhood is an interval in the sequence (s i ) i .

We now want to prove that there exist two segments in S i such that every segment in Z i intersects at least one of them. We differentiate three cases depending of the point p i : if p i is an intersection of segments of different direction, the perturbation ensure that at most two directions are involved. So there is two segments in S i , each containing the point p i and one from each involved direction, such that a segment in Z i cross exactly one of those two segments, as otherwise a representation of this segment with this neighborhood in M could be raised above the line L i . if p i is a top endpoint of a segment s, then each segment z of Z i would intersect this segment s as otherwise the representation of z below L i could be raised up above L i . if p i is a bottom endpoint of a segment s, if this endpoint was at the left of each segment in S then all the segment that could be done below L i could still be represented with the same neighborhood above L i and so Z i = ∅, the same is true if the endpoint is on the right of each segment of S i . So we can assume that the endpoint is between two segments of S. Then a segment of Z i will necessarily intersect these two segments as otherwise the representation of z below L i could be raised up above L i . Now than we have this property, let s j be the segment of S i that is crossed by at least half of Z i . There are at most t 2 segments that do not cross the segment s j-t , nor s j+t as this is the number of intervals in [j -t, . . . , j, . . . , j + t] that contain j. There are at most t -1 segments intersecting s j-t (if it exists), as otherwise, there would be a K t,t . Similarly there are at most t -1 segments intersecting s j+t . So

|Z i | ≤ 2(t 2 + 2t -2) = O(t 2 ).
As the (Z i ) i was a partition of A H2 , and the number of special points

|P C | is at most 2|M C | + m M = O(t • log t • |M |), we obtain |A H2 | = O(t 3 • log t • |M |). ⌟ To conclude, |{N (v) ∩ M : v ∈ V (G) \ M }| ≤ 1 + d(|A H1 | + |A H2 |) = O(d • t 3 log t • |M |). ◀ Figure 6
Example of the construction used in the proof of Claim 46. The contact segment representation of G ′ is on the left, with the segments of M in black, and the segments of A2 in red. On the right is the the constructed planar graph H, with the red edges being the representation of the segments of A2.

▶ Lemma 11. The class of contact segment graphs has linear neighborhood complexity.

Proof. Let G be a contact segment graph, and fix M ⊆ V (G). As in the previous lemma, let us only prove that

|{N (v) ∩ M : v ∈ V (G) \ M }| = O(|M |).
Whenever two vertices of G -M have the same neighborhood in M , we delete one of them. We also delete all vertices whose neighborhood in M can be obtained with a zero-length segment: this kind of neighborhood either contains at most one vertex of M (there are |M | + 1 such neighborhoods) or is a set of segments in contact on the same point. This point has to be an endpoint of at least one segment of M , so there are at most 2|M | such neighborhoods. We call G ′ the graph obtained after deleting those vertices. We split the set A = V (G ′ ) \ M in two parts such that A 1 is the set of segments of A whose interior is in contact with an endpoint of a segment of M , and A 2 = A \ A 1 . Observe that an endpoint of a segment can be in contact with only one interior of segments without creating a crossing, so we have

|A 1 | ≤ 2|M |. Now it remains to bound A 2 . ▷ Claim 46. |A 2 | ≤ 24|M |.
Proof. Let us define an embedding in the plane of a planar graph H such that |H| ≤ 8|M | and |E(H)| ≥ |A 2 |. The embedding is defined from a contact segment representation of G ′ -A 2 , as depicted in Figure 6. Firstly we add one vertex on every position of the endpoints of the segments of M , and denote V 1 this set of vertices, where |V 1 | ≤ 2|M |. Then, we add edges between vertices of V 1 as follows: for each segment v of M , we add a path starting at an endpoint of v and then (following their order along v) all the endpoints of segments of M on segment v, until reaching the other endpoint of v. We draw the edges of this path following the segment representation of v. We denote this set of edges by E 1 . Observe that at this step the graph is planar, implying that |E 1 | ≤ 6|M | by the Euler's formula.

The next step of the construction is to subdivide every edge e ∈ E 1 by adding a vertex v e on the center e. We denote V 2 this set of vertices. Informally, we associated a vertex of H to every section of segment between endpoints of M . Observe that

|V 1 | + |V 2 | ≤ 8|M |.
Let us now associate to each v ∈ A 2 a new edge e(v) in H, and also explain how we can draw these new edges without crossings. Let v ∈ A 2 . Observe that as v is not in contact with M in its interior, its neighborhood in M is entirely decided by its two endpoints, and both of them are part of a segment of M as otherwise the neighborhood in M of v could be achieved with a zero-length segment, and so v / ∈ V (G ′ ). Let s be the segment representing v and {p 1 (s), p 2 (s)} be the endpoints of s. Let slightly shortening s to obtain s, and for i ∈ {1, 2} let p i (s) be the endpoint of s corresponding to p i (s). We now associate a vertex v i ∈ V (H) to each p i (s) and we will define e(v) = {v 1 , v 2 }. Moreover, to draw e(v), we will also define three segments s 1 (v), s 2 (v) and s 3 (v), and draw e(v) as s 1 (v) ∪ s 2 (v) ∪ s 3 (v). Firstly, we define s 3 (v) = s. Then, let us distinguish two cases: 1. If p i (s) is also an endpoint p of a segment of M , then v i is the vertex of H corresponding to the endpoint of this segment in M , and s i (v) = {p, p i (s)} 2. Otherwise, p i (s) is in the interior of exactly one segment s of M , and more precisely inside an edge e ∈ E 1 . Then, we define ⌟

v i = v e .
In total, |{N (v) ∩ M : v ∈ V (G) \ M }| ≤ 1 + |M | + |A 1 | + |A 2 | = O(|M |). ◀ ▶ Corollary 12.
There is an algorithm that solves TH in time 1) in contact segment even when no representation is given. 1) for each of these 2 O(k 1-ϵ log k) instances. Choosing ϵ = 2 9 , we get the claimed running time. ◀

2 O(k 2/3 log k•t 2 log t• √ d) n O(1) in K t,t -free d-DIR graphs, 2 O(k 7/9 log 3/2 k) n O(

Negative results

Let us first start with the following result on TH.

▶ Theorem 47. Under the Exponential Time Hypothesis, TH cannot be solved in time 2 o(n) on n-vertex 2-DIR graphs.

Before proceeding to the proof of Theorem 47 we need to introduce some definitions about the gadgets used in our reduction.

▶ Definition 48. For k ≥ 2, a k-polygon P is a 2-DIR graph composed of 4k axis-parallel segments in the plane such that V (P ) = H ∪ V ∪ C with : 1. H is a set of k disjoint horizontal segments of non-zero length; 2. V is a set of k disjoint vertical segments of non-zero length; 3. every segment of H intersects exactly two segments of V , and vice-versa; 4. C consists of zero-length segments located at each intersection point between a segment of H and a segment of V ; and 5. the intersection graph of the segments in P is connected. Notice that in the definition above, |C| = 2k. See Figure 7 for a depiction of a 3-polygon. ▶ Lemma 49. Let P be a k-polygon. Then P does not have any triangle hitting set of size k -1, and has exactly two triangle hitting sets of size k: the non-zero horizontal segments and the non-zero vertical segments.

Proof. Let P be a k-polygon, and let {H, V, C} be the partition of V (P ) named as in the definition of k-polygon. Notice that every vertex of C together with its two neighbors (one vertical, one horizontal, by definition) forms a triangle, and that every triangle P has this form. So P contains 2k triangles. As every segment is part of at most two triangles, any triangle hitting set has size at least k, which shows the first part of the statement. Suppose now that X is a triangle hitting set of size k. In order to intersect the 2k triangles of P , each of the k segments in X have to take part in two triangles, so X ∩ C = ∅, and no triangle can be hit twice, so S is an independent set. The induced subgraph over V ∪ H is a cycle of size 2k, whose independent sets of size k are H and V . So X = V or X = H, as claimed. ◀

Proof or Theorem 47. The proof is a reduction from 3-SAT.

Let φ be a 3-SAT instance with n variables x 1 , . . . , x n and m clauses C 1 , . . . , C m . Without loss of generality we may assume that each variable appears in some clause and that φ has no clause with only one literal (otherwise it could be easily simplified). For our reduction we also want to avoid clauses with 3 literals all positive or all negative. To do so, for any clause of the form x a ∨ x b ∨ x c we define an additional variable y i and we replace the clause by the equivalent clauses x a ∨ x b ∨ y i and x c ∨ y i , and similarly for clauses containing only negative literals. Notice that after performing these operations the number of clauses and variables increased by O(m).

Let us now construct a 2-DIR graph G from the formula φ. In this graph each variable x i is represented by a k i -polygon with k i to be specified later. (We only describe the non-zero segments, as the position of the zero-length segments is uniquely determined by those, by definition.) To every clause C, we associate a point of the plane z C . We construct the variable polygons such that, for every clause C and variable x, each of the following is satisfied: 1. if the literal x (respectively x) appears in C, then some vertical (respectively horizontal) segment of the polygon of the variable x ends at z C ; 2. if C contains only two literals, then a new vertex with zero-length segment is added at position z C ; 3. if x does not appear in C, then z C does not belongs to any segment of the polygon of x; and

x 2 ∨ x 4 ∨ x 3 x 1 ∨ x 3 ∨ x 4 x 2 ∨ x 4
Figure 8 The construction for the formula (x2

∨ x4 ∨ x3) ∧ (x1 ∨ x3 ∨ x4) ∧ (x2 ∨ x4
). The zero-length segments at each corner of the k-polygons are not represented, while that added for the clause with two variables is depicted with a black dot.

x 1 ∨ x 2 x 1 ∨ x 2 Figure 9
The two remaining possibilities for the clause gadget. The length 0 segments at each corner of the k-polygons are not represented. The black dots represent the length 0 segments we add for clauses with 2 literals.

if two horizontal (respectively vertical) segments intersect, their intersection consists in a

unique point of the form z C ′ for some clause C ′ .

Also, we want the number of segments in each polygon and its number of intersections with each other polygon to be linearly bounded from above by the number of clauses the corresponding variable appear in. Such a configuration can for instance be obtained by initially drawing the polygons of the variables as concentric rectangles and then, for every clause C, picking a point z C outside of the outermost triangle and connecting corresponding the polygons to it. See Figure 8 for an illustrative example and Figure 9 for a depiction of the connection to the z C 's.

For 1 ≤ i ≤ n we define k i such that the variable gadget for the variable x i constructed as defined above is a k i -polygon. Let k = n i=1 k i . We define a good triangle hitting set as a triangle hitting set of size k. ▷ Claim 50. If a good triangle hitting set exists, it is a minimum triangle hitting set, it only contains non-zero length segments, and all the segments from a same polygon it contains have the same orientation.

Proof. Let S be a good triangle hitting set of G. By Lemma 49, for each variable x i , its corresponding k i -polygon needs k i segments in order to hit all its triangles. As k = n i=1 k i and no segment is part of two distinct polygons, we can conclude that exactly k i segments of the considered polygon are in S, and S is a minimum triangle hitting set. Again by Lemma 49 we get that those k i segments have non-zero length and either consist of all vertical segments of the polygon, or of all its horizontal segments. Moreover, this implies that S does not contains the zero length segments added for clauses with two literals. ⌟ ▷ Claim 51. G has a good triangle hitting set if and only φ is satisfiable.

Proof. Direction "⇒". Let S be a good triangle hitting set of G. We define a truth assignment for the variables by setting the variable x i at false if the segments of the corresponding polygon being in S are the horizontal segments, and true if they are the vertical ones. For a clause C of φ, let ∆ C denote the set of the 3 vertices containing z C (which trivially induce a triangle). Because S is a hitting set and by Claim 50, we have S ∩ ∆ C ̸ = ∅. Let x i be a variable such that its k i -polygon contains a segment in S ∩ ∆ C . Suppose this segment is vertical, this means that the variable x i appears in C in a positive literal, and that in the constructed assignment x i is true, and the clause C is verified. We can obtain the same conclusion is the case of a vertical segment, so each clause is verified with the defined truth assignment, and so φ is satisfiable. Direction "⇐". For an assignment of the variables x i such that φ is verified, we construct a set S of size k with the same encoding than before: S contains the vertical segments of the k i -polygon for the variables x i assigned to true, and the horizontal ones otherwise. Let us now show that S is a hitting set.

All the triangles contained in the polygons encoding the variables are hit, as they always contain an horizontal segment and a vertical segment of the same polygon. The remaining triangles are the one formed by each clause C on the point z C . As φ is verified by the considered truth assignment, there is a literal which evaluate to true. Let x i be the variable contained in this literal. If the literal is positive, then x i was assigned to true, so all the horizontal segments of its polygon are in S; and the segment in contact with z C is horizontal. So the triangle at the point z C is hit by S. The case of a negative literal have the same conclusion. So all triangles of G are hit by S. ⌟ ▷ Claim 52. |G| = O(m).

Proof. As argued above for every variable, the number of segments of its polygon is linearly bounded by the number of clauses it appears in. Each clause contains at most 3 variables and there are at most m extra vertices (for clauses of size 2) so the total number of segments is O(m). ⌟

We described the construction of a graph G and integer k from φ such that (G, k) is a positive instance of TH if and only if φ is satisfiable. Besides, the construction can clearly be done in time polynomial in n + m and the graph has n ′ = O(m) vertices. Therefore any algorithm solving TH in time 2 o(n ′ ) for input graphs of size n ′ could be used to solve 3-SAT in time 2 o(m) on formulae with m clauses, which would refute the ETH. ◀

We observe that the instances constructed as in Figure 8 contain large complete bicliques. We now provide a construction that is K 2,2 -free, where segments do not cross (i.e., that is a contact 2-DIR graph) and that applies also to FVS and OCT, to the price of a worse lower bound.

▶ Theorem 6. Under the Exponential Time Hypothesis, the problems TH, OCT, and FVS cannot be solved in time 2 o( √ n) on n-vertex K 2,2 -free contact 2-DIR graphs.

The incidence graph of a 3-SAT formula is the (bipartite) graph whose vertices are clauses and variables and where edges connect variables to the clauses they appear in. The restriction of the 3-SAT problem to formulae with a planar incidence graph is called Planar-3-SAT.

▶ Theorem 53 ([22]

). There is no algorithm that solves Planar-3-SAT on a formula with n variables and m clauses in time 2 o( √ n+m) , unless the ETH fails.

▶ Lemma 54. There is an algorithm that, given a planar bipartite graph G, returns in polynomial time a representation of G as a contact graph of rectangles, where two intersecting rectangles intersect on a non-zero length segment.

Proof. Let G be a planar bipartite graph. In linear time it can be represented as a contact 2-DIR graph according to [START_REF] Czyzowicz | A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments[END_REF], with the contact occurring only between segments of different directions. We will now transform this representation to obtain a representation of G as a contact graph of rectangles. To do this, we first prevent the contact of endpoints of two segments, by slightly extending one if such a contact point exists. This transformation done, we then shorten all the segments by a small ϵ, and thicken them at both side by the same amount. The segments are now interior disjoint rectangles, and two segments that were in contact are now two rectangles sharing an ϵ-length segment on their border. ◀

In order to avoid all-positive or all-negative clauses as in the proof of Theorem 47, we show below that those (if any) can be replaced without destroying planarity. Each replacement decreases the number of all-positive or all-negative clauses so after m replacement steps at most the obtained formula is free of such clauses (and equivalent to the initial one). Finding a clause to replace and doing so can be performed in polynomial time, hence so does the replacement of all all-positive and all-negative clauses, as claimed. ◀

Proof of Theorem 6. In this proof we adapt our construction from Theorem 47 so that the polygons intersect each other only at points of the form z C , for C a clause. toward this goal we consider an instance φ of the problem Planar-3-SAT; by Lemma 55 we may assume that φ has no all-positive or all-negative clause; also we can easily simplify clauses of size one.

The incidence graph G φ of φ is a bipartite planar graph, so using Lemma 54 it can be represented as a contact graph of rectangles. Let us now describe how this representation is used to construct a 2-DIR instance of the cycle-hitting problems we consider. Initially, for each variable we create a 2-polygon that follows the associated rectangle (in the contact representation) and for each clause C we choose a point z C of the plane located at the center of its rectangle. For each clause, we want to add a few sides to the polygons of its (2 or 3) variables so that these polygons intersect in z C only. As they do not intersect elsewhere, this ensures that the obtained graph is a contact 2-DIR. We describe the construction for clauses with 3 variables; that for two variables is a simpler version of it. Recall that for a clause C, the rectangles of its variables are in contact with the rectangle of C and do not intersect mutually. For each variable in C, we add a non-zero length segment with one endpoint being z c , vertical if the literal containing the variable is positive, horizontal otherwise. As the clause does not contain all-positive or all-negative literals, it is always possible to do so with the three segments intersecting in z C only. The choices of the sides of z c on which we put the segments is made so that the circular order of the segments around z C is the same as the circular order of the rectangles of the variables around that of C. We claim that extending the polygons of the variables in order to connect each with the newly created segment without crossings can be done by adding a constant number of segments to each, as depicted in Figure 10. In order to finish the construction of the graph G, for each non-zero length segment, which is then a side of one of the polygons, we add in the portion of segment between the two intersections with the two adjacent sides of the concerned polygon a crenellation, which is the simple gadget depicted in Figure 11. We make this crenellation small enough so that it does not for not intersect other segments. This corresponds to subdividing 4 times each edge of the cycles corresponding to polygons. ▷ Claim 56. A cycle in G which is not a triangle contains 5 consecutive sides of a same polygon. And so G is K 2,2 free.

Proof. Let Q a cycle of size at least 4. A z C point is contained in only 3 segments and the segments containing a z ′ C point with C ′ ̸ = C are at distance at least 4 because of the crenellation. This ensures there is in Q a segment s which does not contain a z C point, so which is a part of a polygon and more precisely of a crenellation. But if a cycle hits a segment from a crenellation that does not contain a z C point, all the paths that the cycle can follow over the crenellation go from one of its side to another, crossing the 5 adjacent non-zero length segments of the crenellation. Observe that K 2,2 is a cycle of size 4, and we just proved that a cycle that is a subgraph of G is either of size 3 or at least 5, so G is K 2,2 free. ⌟

Observe that the graph G obtained by the above construction satisfies the same properties as the graph constructed in the proof of Theorem 47. Additionally, 1. G is a contact 2-DIR (as argued above); 2. G is K 2,2 -free, as proved in Claim 56.

3. the polygons corresponding to two variables intersect only in a point of the form z C , for C a clause where they both appear. Now that the graph is defined, let us show how it relates to the cycle-hitting problems. As in the previous proof, we denote k i the number such that the variable gadget for the variable x i is a k i -polygon and k = n i=1 k i .

▷ Claim 57. For a set S ⊆ V (G) of size at most k, the three following properties are equivalent: 1. S is a feedback vertex set, 2. S is a odd cycle transversal, 3. S is a triangle hitting set.

Proof. We trivially have (1)⇒(2)⇒(3) so it is enough to prove (3)⇒(1). Let S be a triangle hitting set of G of size at most k. Hitting all the triangles of the polygons of G requires already k vertices, so S has size exactly k and so is a good triangle hitting set as defined in the proof of Theorem 47. Claim 56 assures that any cycle of length greater than 3 contains two adjacent non-zero length segments from a same polygon, and so with different directions. But because S is a good triangle hitting set, we know that one of those two segments will be part of S. This proves that S not only hits all the triangles, but it is a set hitting every cycle of G. ⌟

Because our construction still verifies the properties of the construction done in the Theorem 47, the Claim 51 is still verified. So an algorithm solving FVS, TH or OCT in time 2 o( √ n) would also solve Planar-3-SAT with the same complexity, which according to Theorem 53 contradicts the ETH. ◀

Figure 1

 1 Figure 1Three intersection graphs. From left to right, a disk graph, a 2-DIR graph, and a contact 2-DIR graph. In these graphs (where the left one is from[START_REF] Fedorr V Fomin | Excluded grid minors and efficient polynomial-time approximation schemes[END_REF]), ω(G) is constant, tw(G) ≥ t (where t = 3 here) as it contains Kt,t as a minor, ⊞(G) = O( √ t) as they have a feedback vertex set of size at most t.

  Removing a vertex decreases the treewidth by at most 1, so tw(G ′ ) ≤ |B| + tw(G ′′ ). By Corollary 16 |M | ≤ 11λk so by Lemma 22 we get |B| = O(λτ -1 k) and obtain the wanted result tw(

1 Figure 4

 14 Figure 4 Vertices of M are depicted in black, and M ′ = M ∪ {u1, u2}.

  delete u and v and decrease the parameter k by two.

Let▷

  I ⊆ V (T ) (I for inner vertices) be the set of vertices v such that|N T (v)| ≥ 2. Claim 31. |I| ≤ 134d. Proof. Observe that if v ∈ I and u ∈ V (T ) is an ancestor of v (i.e., v ∈ T u ), then u ∈ I. Also, as d ≥ 2, r ∈ I. So T [I] isconnected and the leaves of T [I] form a set of incomparable vertices. By Claim 29 and Claim 30, we deduce that T [I] has at most 6d leaves. This implies that the number of vertices of T [I] with degree at least three (in T [I]) is also bounded by 6d. The same bound of 6d holds on the number of connected components in the subgraph of T [I] induced by the vertices having degree two in T [I]. In the following let us refer to these connected component as long paths.

  and notice that this set has weight |S ′ | ≤ k ′ . So it remains to show that S ′′ is a triangle hitting set of G ′′ . Suppose toward a contradiction that G ′′ -S ′′ has a triangle ∆. As previously, if |∆ ∩ M | = 3 we have a contradiction and thus |∆ ∩ M | = 2, and let v i be the vertex in ∆ \ M . By definition of S ′′ , v i / ∈ S ′ and thus ∆ is a triangle of G ′ -S ′ , a contradiction. ⌟

Proof.

  For the first result, Corollary 43, together with Theorem 39 with δ = 1/2, β = √ t log t, c = O(d • t 3 log t) (Lemma 10), implies the claimed running time. For the second result, given (G, k), we first use Corollary 14 with p = k ϵ . This leads to 2 O(k 1-ϵ log k) instances (G ′ , k ′ ) to solve, where each G ′ has ω(G ′ ) ≤ k ϵ , and thus is K t,t -free for t = O(k ϵ ) according to Lemma 33. Thus, Corollary 43, together with Theorem 39 with δ = 1/2, β = O( √ t log t), c the constant of Lemma 11, implies a running time in 2 O( √ k ϵ log kk 2/3 log k n O(

Figure 7

 7 Figure[START_REF] Chuzhoy | Towards tight (er) bounds for the excluded grid theorem[END_REF] An example of a 3-polygon, where the segments in H are blue, the ones in V are red, and the length 0 segments in C are represented by black dots.

▶ Lemma 55 .

 55 There is an algorithm that, given a planar 3-SAT formula with n variables and m clauses, returns in time polynomial in n + m an equivalent planar 3-SAT formula with n + m variables and 2m clauses where in addition no clause contains 3 positive literals or 3 negative literals.Proof. Let ϕ be the input formula with n variables and m clauses and let G be its planar incidence graph. For a variable or clause z of φ, we denote by v(z) the corresponding vertex in G. If there is a clause C of the form x a ∨ x b ∨ x c then we replace it by the two clauses C 1 = x a ∨ x b ∨ ȳ and C 2 = y ∨ x c , where y is a fresh variable. Clearly the obtained formula φ ′ is equivalent and has n + 1 variables and m + 1 clauses. Also, the incidence graph G ′ of φ ′ can be obtained from G by renaming v(C) into v(C 1 ) (for the clause C 1 ) and replacing the edge v(x c )v(C 1 ) by the path v(C 1 )v(y)v(C 2 )v(x c ), where v(C 2 ) and v(y) are new vertices representing C 2 and y. As a subdivision of a planar graph, G ′ is planar. A symmetric replacement can be done for clauses where all literals are negative.

Figure 10

 10 Figure[START_REF] Czyzowicz | A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments[END_REF] An example of extensions of three polygons toward a point ZC in order to encode a clause as described in the proof of Theorem 6.

Figure 11

 11 Figure 11Portion of a polygon before and after the adding of the crenellation on each side of the polygon.

  R4) If there is a triangle uvw such that deg(u) = 2 and deg(w) = 3, delete v and decrease the parameter k by one. Proof. (Safeness of R4) Any feedback vertex set should intersect {u, v, w}, and any cycle intersecting this set goes through vertex v. So it is safe to force v in the solution.

⌟ (R5) If there is a vertex v ∈ M ′ and a path

  delete v and decrease the parameter k by one.Proof. (Safeness of R5) By (R2), v is adjacent to every vertex in P ℓ . The correctness of (R5) relies on the fact that a feedback vertex set avoiding v should contain at least 2 vertices of P ℓ , but in that case such set could be modified by replacing one of the vertices by v. So it is safe to force v in the solution.

⌟ (R6) If there are vertices u, v ∈ M ′ and a path

  Proof. (Safeness of R8) Indeed, every feedback vertex set should intersect G[V (F u,v ) ∪ {u, v}] on at least two vertices, and removing u and v destroys every cycle intersecting V (F u,v )∪{u, v}. We can thus force u and v in the feedback vertex set. ⌟Note that from now on, there are no pair of disjoint cycles inG[V (F u,v ) ∪ {u, v}]. If there are vertices u, v ∈ M ′ , such that G[V (F u,v ) ∪ {u, v}] has two cycles intersecting only at v, delete v and decrease the parameter k by one.Proof. (Safeness of R9) Indeed, every feedback vertex set avoiding v should intersect G[V (F u,v ) ∪ {u, v}] on at least two vertices, but removing u and v destroys every cycle intersecting V (F u,v ) ∪ {u, v}. We can thus force v in the feedback vertex set. ⌟Note that from now on, for every u, v ∈ M ′ , the forest F u,v has at most 2 connected components, or all its components are trivial.

	(R9)

v}] has no feedback vertex set S with |S| < 2, delete u and v and decrease the parameter k by two. (R10) If there are vertices u, v ∈ M ′ , such that F u,v has ℓ ≥ 3 trivial connected components, delete ℓ -3 of these connected components and maintain the parameter k. Proof. (Safeness of R10) Let G ′ be the obtained graph, and S a feedback vertex set of G ′ with |S| ≤ k. Every minimum feedback vertex set S of G ′ has to intersect V (F u,v ) ∪ {u, v}] on one or two vertices. If this intersection has size two, then the set (S \ F u,v ) ∪ {u, v} has same size and it is a feedback vertex set of G. If the intersection has size one, it is on u or v, and this set S is already a feedback vertex set of G. So in both cases the size of a minimum feedback vertex set of G ′ is the same as for G. ⌟

  Let p(v e ) be the point associated to v e . We define s i (v) = {p(v e ), p i (s)}. This concludes the definition of H. As required, we get that H is planar, |H| ≤ 8|M |, |E(H)| ≥ |A 2 |. This last property gives |E(H)| ≤ 3|H| by the Euler's formula, and so |A 2 | ≤ 24|M |, which is the wanted result.

Informally, a problem is bidimensional if positive instances are minor-closed and a solution on the (r, r)-grid has size Ω(r

).[START_REF] Baste | Contraction bidimensionality of geometric intersection graphs[END_REF] See definition in[START_REF] Grigoriev | Bidimensionality of geometric intersection graphs[END_REF].

Note that these two or more other segments intersect on their endpoints, as we are dealing with contact graphs.

Felix Reidl, Fernando Sánchez Villaamil, and Konstantinos Stavropoulos. Characterising bounded expansion by neighbourhood complexity. European Journal of Combinatorics, 75:152-168, 2019.

Funding Gaétan Berthe: Supported by the ANR project ELIT (ANR-20-CE48-000801). Jean-Florent Raymond: Supported by the ANR project GRALMECO (ANR-21-CE48-0004).