Decomposition of map graphs with applications

Fedor V. Fomin

University of Bergen, Norway [email protected]

Daniel Lokshtanov

University of California, Santa Barbara, USA [email protected]

Fahad Panolan

University of Bergen, Norway [email protected]

Saket Saurabh

The Institute of Mathematical Sciences, HBNI, Chennai, India [email protected]

Meirav Zehavi

Ben-Gurion University of the Negev, Beer-Sheva, Israel [email protected]

Abstract

Bidimensionality is the most common technique to design subexponential-time parameterized algorithms on special classes of graphs, particularly planar graphs. The core engine behind it is a combinatorial lemma of Robertson, Seymour and Thomas that states that every planar graph either has a√

k×√

k-grid as a minor, or its treewidth isO(√

k). However, bidimensionality theory cannot be extended directly to several well-known classes of geometric graphs like unit disk or map graphs. This is mainly due to the presence of large cliques in these classes of graphs. Nevertheless, a relaxation of this lemma has been proven useful for unit disk graphs. Inspired by this, we prove a new decomposition lemma for map graphs, the intersection graphs of finitely many simply-connected and interior-disjoint regions of the Euclidean plane. Informally, our lemma states the following. For any map graphG, there exists a collection (U1, . . . , Ut) of cliques ofGwith the following property:

Geither contains a√ k×√

k-grid as a minor, or it admits a tree decomposition where every bag is the union ofO(√

k) cliques in the above collection.

The new lemma appears to be a handy tool in the design of subexponential parameterized algorithms on map graphs. We demonstrate its usability by designing algorithms on map graphs with running time 2^O(

√

klogk)·n^O(1) forConnected PlanarF-Deletion(that encompasses problems such as Feedback Vertex Set and Vertex Cover). Obtaining subexponential algorithms forLongest Cycle/PathandCycle Packingis more challenging. We have to construct tree decompositions with more powerful properties and to prove sublinear bounds on the number of ways an optimum solution could “cross” bags in these decompositions.

ForLongest Cycle/Path, these are the first subexponential-time parameterized algorithm on map graphs. For Feedback Vertex Set and Cycle Packing, we improve upon known 2^O(k0.75logk)·n^O(1)-time algorithms on map graphs.

2012 ACM Subject Classification Theory of computation→Parameterized complexity and exact algorithms; Theory of computation→Computational geometry

Keywords and phrases Longest Cycle, Cycle Packing, Feedback Vertex Set, Map Graphs, FPT Digital Object Identifier 10.4230/LIPIcs.ICALP.2019.60

Category Track A: Algorithms, Complexity and Games

Related Version A full version of the paper is available athttp://arxiv.org/abs/1903.01291.

Acknowledgements This work is supported by the European Research Council (ERC) via grant LOPPRE, reference 819416, the Norwegian Research Council via project MULTIVAL, and Israel Science Foundation individual research grant no. 1176/18.

EATCS

© Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi;

licensed under Creative Commons License CC-BY

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019).

1 Introduction

In this paper, we develop new proof techniques to design parameterized subexponential- time algorithms for problems on map graphs, particularly problems that involve hitting or connectivity constraints. The class of map graphs was introduced by Chen, Grigni, and Papadimitriou [7, 8] as a modification of the class of planar graphs. Roughly speaking, map graphs are graphs whose vertices represent countries in a map, where two countries are considered adjacent if and only if their boundaries have at least one point in common; this common point can be a single common point rather than necessarily an edge as standard planarity requires. Formally, amap Mis a pair (E, ω) defined as follows : E is a plane graph (i.e., a planar graph with an embedding) where each connected component ofE is biconnected, andω is a function that maps each facef ofE to 0 or 1. A facef ofE is called nation ifω(f) = 1 andlake otherwise. The graph associated withMis the simple graphG whereV(G) consists of the nations ofM, andE(G) contains{f1, f₂}for every pair of faces f1 andf2that are adjacent (that is, share at least one vertex). Accordingly, a graphGis called a map graph if there exists a mapMsuch thatGis the graph associated withM.

Every planar graph is a map graph [7, 8], but the converse does not hold true. Moreover, map graphs can have cliques of any size and thus they can be “highly non-planar”. These two properties of map graphs can be contrasted with those ofH-minor free graphs and unit disk graphs: the class ofH-minor free graphs generalizes the class of planar graphs, but can only have cliques of constant size (where the constant depends onH), while the class of unit disk graphs does not generalize the class of planar graphs, but can have cliques of any size.

At least in this sense, map graphs offer the best of both worlds. Nevertheless, this comes at the cost of substantial difficulties in the design of efficient algorithms on them.

Arguably, the two most natural and central algorithmic questions concerning map graphs are as follows. First, we would like to efficiently recognize map graphs, that is, determine whether a given graph is a map graph. In 1998, Thorup [29] announced the existence of a polynomial-time algorithm for map graph recognition. Although this algorithm is complicated and its running time is aboutO(n¹²⁰), wherenis the number of vertices of the input graph, no improvement has yet been found; the existence of a simpler or faster algorithm for map graph recognition has so far remained an important open question in the area (see, e.g., [9]).

The second algorithmic question – or rather family of algorithmic questions – concerns the design of efficient algorithms for various optimization problems on map graphs. Most well-known problems that are NP-complete on general graphs remain NP-complete when restricted to planar (and hence on map) graphs. Nevertheless, a large number of these problems can be solved faster or “better” when restricted to planar graphs. For example, nowadays we know of many problems that are APX-hard on general graphs, but which admit polynomial time approximation schemes (PTASes) or even efficient PTASes (EPTASes) on planar graphs (see, e.g., [4, 14, 15, 22]). Similarly, many parameterized problems that on general graphs cannot be solved in time 2^o(k)·n^O(1) unless the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [24] fails, admit parameterized subexponential-time algorithms on planar graphs (see, e.g., [1, 2, 14, 27]). It is compelling to ask whether the algorithmic results and techniques for planar graphs can be extended to map graphs.

For approximation algorithms, Chen [6] and Demaine et al. [12] developed PTASes for theMaximum Independent SetandMinimum r-Dominating Set problems on map graphs. Moreover, Fomin et al. [21, 22] developed an EPTAS forTreewidth-η Modulator for any fixed constant η ≥ 0, which encompasses Feedback Vertex Set (FVS) and Vertex Cover (VC). For parameterized subexponential-time algorithms on map graphs,

the situation is less explored. While on planar graphs there are general algorithmic methods – in particular, the powerful theory of bidimensionality [15, 13] – to design parameterized subexponential-time algorithms, we are not aware of any general algorithmic method that can be easily adapted to map graphs. Demaine et al. [12] gave a parameterized algorithm for Dominating Set, and more generally for (k, r)-Center, with running time 2^O(rlogr

√ k)n^O(1) on map graphs. Moreover, Fomin et al. [21, 22] gave 2^O(k0.75logk)n^O(1)-time parameterized algorithms forFVSandCycle Packingon map graphs. Additionally, Fomin et al. [21, 22]

noted that the same approach yields 2^O(k0.75logk)n^O(1)-time parameterized algorithms for Vertex Cover andConnected Vertex Cover (CVC)on map graphs. However, the existence of a parameterized subexponential-time algorithm forLongest Path/Cycleon map graphs was left open. (In these problems we are asked whether ann-vertex graph contains a path/cycle of length at least k.) Furthermore, time complexities of 2^O(k0.75logk)n^O(1), although having subexponential dependency on k, remain far from time complexities of 2^O(

√

klogk)n^O(1) and 2^O(

√

k)n^O(1) that commonly arise for planar graphs [27]. We remark that time complexities of 2^O(

√klogk)n^O(1) and 2^O(

√k)n^O(1) are particularly important since they are often known to be essentially optimal under the aforementioned ETH [27].

In the field of Parameterized Complexity, Longest Path/Cycle, FVSandCycle Packing serve as testbeds for development of fundamental algorithmic techniques such as color-coding [3], methods based on polynomial identity testing [25, 26, 30, 5], cut-and- count [11], and methods based on matroids [19]. By combining the bidimensionality theory of Demaine et al. [13] with efficient algorithms on graphs of bounded treewidth [17, 10], Longest Path/Cycle, Cycle PackingandFVSare solvable in time 2^O(

√k)n^O(1) on planar graphs. Furthermore, the parameterized subexponential-time “tractability” of these problems can be extended to graphs excluding some fixed graph as a minor [15].

Our results. We design parameterized subexponential-time algorithms with running time 2^O(

√

klogk)·n^O(1) for a number of natural and well-studied problems on map graphs.

Let F be a family of connected graphs that contains at least one planar graph. Then Connected Planar F-Deletion(or just F-Deletion) is defined as follows. The input is a graphGand a non-negative integerk, and our objective is to test whether there exists a setSof at mostkvertices such thatG−Sdoes not contain any of the graphs inFas a minor.

F-Deletionis a general problem and several problems such asVC,FVS,Treewidth-η Vertex Deletion,Pathwidth-η Vertex Deletion,Treedepth-η Vertex Deletion, Diamond Hitting SetandOuterplanar Vertex Deletionare its special cases. We give the first parameterized subexponential algorithm for this problem on map graphs, which runs in time 2^O(

√

klogk)·n^O(1). Our approach for F-Deletionalso directly extends to yield 2^O(

√

klogk)·n^O(1)-time parameterized algorithms for CVC andConnected Feedback Vertex Set (CFVS) on map graphs. (In this versions we are asked if there is aconnected vertex cover or a feedback vertex set of size at mostk.)

With additional ideas, we derive the first subexponential-time parameterized algorithm on map graphs forLongest Path/Cycle. Our technique also allows to improve the running time forCycle Packing(does a map graph contains at leastk vertex-disjoint cycles) from 2^O(k0.75logk)·n^O(1) to 2^O(

√

klogk)·n^O(1). Our results are summarized in Table 1.

Our methods. The starting point of our study is the technique of bidimensionality [15, 13].

The core engine behind this technique is a combinatorial lemma of Robertson, Seymour and Thomas [28] that states that every planar graph either has a√

k×√

k-grid as a minor, or its treewidth isO(√

k). Unfortunately, a clique onk−1 vertices has no√ k×√

k-grid as a minor

Table 1 Parameterized complexity of problems on map graphs. For F-Deletion,Longest Cycle, andLongest Pathno faster (than on general graphs) algorithms were known.

Our results Previous work (Connected) Vertex Cover 2^O(

√

klogk)·n^O(1) 2^O(k0.75logk)·n^O(1)[22]

(Connected) Feedback Vertex Set 2^O(

√

klogk)·n^O(1) 2^O(k0.75logk)·n^O(1)[22]

F-Deletion 2^O(

√

klogk)·n^O(1) 2^O(k)n^O(1) [18]

Longest Cycle/Path 2^O(

√

klogk)·n^O(1) 2^O(k)n^O(1) [10]

Cycle Packing 2^O(

√

klogk)·n^O(1) 2^O(k0.75logk)·n^O(1)[22]

and its treewidth isk−2. Because classes of geometric graphs such as unit disk graphs and map graphs can have arbitrarily large cliques, the combinatorial lemma is inapplicable to them. Nevertheless, a relaxation of this lemma has been proven useful for unit disk graphs.

Specifically, every unit disk graphGhas a natural partition (U1, . . . , Ut) ofV(G) such that each part induces a clique with “nice” properties – in particular, it has neighbors only in a constant number (to be precise, this constant is at most 24) of other parts; it was shown that

Geither has a√ k×√

k-grid as a minor, or it has a tree decomposition where every bag is the union ofO(√

k) of these cliques [20]. In particular, given a parameterized problem where any two cliques have constant-sized “interaction” in a solution, it is implied that any bag has O(√

k)-sized “interaction” with all other bags in a solution. For any map graphG, there also exists a natural collection of subsets ofV(G) that induce cliques with “nice” properties.

However, not only are these cliques not vertex disjoint, but each of these cliques can have neighbors inarbitrarily many other cliques.

In this paper, we first prove that every map graph either has a√ k×√

k-grid as a minor, or it has a tree decomposition where every bag is the union of O(√

k) of the cliques in the above collection. ForF-Deletion,CVC, andCFVS, this combinatorial lemma alone already suffices to design 2^O(

√

klogk)·n^O(1)-time algorithms on map graphs. Indeed, we can choose a fixed constantc >0 so that in case we have ac√

k×c√

k-grid as a minor, there does not exist a solution, and otherwise we can solve the problem by using dynamic programming over the given tree decomposition. Specifically, since every bag is the union ofO(√

k) cliques, and the size of each clique is upper bounded byO(k) (once we know that noc√

k×c√ k-grid exists), onlyO(√

k) vertices in the bag are not to be taken into a solution – there are only 2^O(

√klogk) choices to select these vertices, and once they are selected, the information stored about the remaining vertices is the same as in normal dynamic programming over a tree decomposition ofO(√

k) width.

This approach already substantially improves upon the previously best known algorithms forFVS,VCandCVCof Fomin et al. [21, 22]. However, 2^O(

√

klogk)·n^O(1)-time algorithms forLongest Path/CycleandCycle Packingon map graphs require more efforts. The main reason why we cannot apply the same arguments as for unit disk graphs is the following.

Recall that for unit disk graphs, given a parameterized problem where any two cliques have constant-sized “interaction” in asolution (in our case, this means a path/cycle on at leastkvertices, or a cycle packing ofkcycles), it is implied that any bag hasO(√

k)-sized

“interaction” with all other bags in a solution. Here, interaction between two cliques refers to the number of edges in a solution “passing” between these two cliques; similarly, interaction between a bagB and a collection of other bags refers to the number of edges in a solution that have one endpoint inB and the other endpoint in some bag in the collection. In this context, dealing with map graphs is substantially more difficult than dealing with unit disk

graphs. In map graphs vertices in a clique can have neighbors in arbitrarily many other cliques in the collection rather than only in a constant number as in unit disk graphs. This is why it is difficult to obtain anO(√

k)-sized “interaction” as for unit disk graphs.

Hence, we are forced to take a different approach for map graphs by bounding “the interaction within a clique across all the bags of a decomposition”. Towards this, we first need to strengthen our tree decomposition. To explain the new properties required, we note that every clique in the aforementioned collection of cliques, sayK, is either a single vertex or the neighborhood of some “special vertex” in an exterior bipartite graph (see Section 2).

Further, every vertex ofGoccurs as a singleton inK. We construct our decomposition in a way such that every bag is not necessarily a union ofO(√

k) cliques in K, but a union of carefully chosen subcliques ofO(√

k) cliques inK(with one subclique for each of these O(√

k) cliques); subcliques of the same clique chosen in different bags may be different.

We then prove properties that roughly state that, if we look at the collection of bags that include some vertexv ofG, then this collection induces a subtree and a path as follows: (♣) the subtree consists of the bags that correspond to the singleton cliquev, and the path goes

“upwards” (in the tree decomposition) from the root of this subtree. We thereby implicitly derive that in every bagB, every subclique of size larger than 1 can only have as neighbors vertices that are(i) in the bagB itself or in one of its descendants, or(ii)in cliques that have a subclique in the bagB. In particular, this means that if we prove that there exists a solution such that for any clique K inK, the number of edges inE(K) that “cross any bagB” (i.e., the edges inE(K) with one endpoint inB and the other in the collection of all bags that are not descendants ofB) is a constant, then we obtain a bound ofO(√

k) on the interaction between any bagB and the collection of all bags that are not descendants of B. We prove the mentioned statement using property (♣). The proof that such a property simultaneously holds for all cliques and all bags is the most challenging part of the proof.

In Section 3 we give our special tree decomposition of map graphs and in Section 4 we explain its application in the algorithm forLongest Cycleon map graphs. For the proofs of results marked with?and all other results we refer to the full version of the paper.

2 Preliminaries

For anyt∈N, we use [t] and [t]₀as shorthands for{1,2, . . . , t}and{0,1, . . . , t}, respectively.

For a setU, we use 2^U to denote the power set of U. For a sequence σ=x1x2. . . xn and any 1 ≤i ≤j ≤n, the sequence σ⁰ = x_i. . . x_j is called asegment of σ. For a sequence σ=x1x2. . . xn and a subset Z⊆ {x1, . . . , xn}, the restriction ofσonZ, denoted by σ|Z, is the sequence obtained fromσ by deleting the elements of{x1, . . . , xn} \Z.

Graphs. We use standard notation and terminology from the book of Diestel [16] for graph- related terms. Given a graph G, let V(G) andE(G) denote its vertex-set and edge-set, respectively. For a setQof graphs we slightly abuse terminology and letV(Q) andE(Q) denote the union of the sets of vertices and edges of the graphs inQ, respectively. For a vertex subset X ⊆V(G) in a graph G, E(X) denotes the set{{u, v} ∈E(G) :u, v ∈X}.

For a graphGand a degree-2 vertexv∈V(G), bycontractingv, we mean deletingvfromG and adding an edge between the two neighbors ofv inG.

A binary tree is a rooted tree where each node has at most two children. In a labelled binary tree, for each node with two children one of the children is labelled as “left child” and the other child is labelled as “right child”. Apostorder transversal of a labelled binary treeT is the sequenceσofV(T) where for each nodet∈V(T),t appears after all its descendants,

and if t has two children, then the nodes in the subtree rooted at the left child appear before the nodes in the subtree rooted at the right child. For a binary treeT, we say that a sequenceσofV(T) is a postorder transversal if there is a labelling ofT such thatσis its postorder transversal.

IDefinition 2.1(Treewidth). A tree decomposition of a graphGis a pair T = (TT, βT), whereT is a rooted tree andβT is a function fromV(TT)to2^V(G), that satisfies the following three conditions. (We use the term nodes to refer to the vertices ofTT.)

(a) S

x∈V(TT)βT(x) =V(G).

(b) For every edge{u, v} ∈E(G), there existsx∈V(TT)such that {u, v} ⊆βT(x).

(c) For every vertex v ∈ V(G), the set of nodes {t ∈ V(TT) : v ∈ βT(t)} induces a (connected) subtree of TT.

The widthofT is max_x∈V(TT)|βT(x)| −1. Each setβT(x)is called a bag. Moreover,γT(x) denotes the union of the bags of xand its descendants. Thetreewidthof Gis the minimum width among all possible tree decompositions ofG, and it is denoted bytw(G).

IDefinition 2.2. A tree decompositionT = (TT, βT) of a graphGis niceif for the root r of TT, it holds thatβT(r) =∅, and each nodev∈V(TT)is of one of the following types.

Leaf: v is a leaf inTT andβT(v) =∅. This bag is labelled with leaf.

Forget vertex: v has exactly one child u, and there exists a vertexw∈βT(u)such that βT(v) =βT(u)\ {w}. This bag is labelled with forget (w).

Introduce vertex: v has exactly one childu, and there exists a vertexw∈βT(v)such thatβT(v)\ {w}=βT(u). This bag is labelled with introduce(w).

Join: v has exactly two children, u and w, and βT(v) =βT(u) =βT(w). This bag is labelled with join.

We will use the following folklore observation and proposition in the later sections.

IObservation 2.3. Let T be a nice tree decomposition of a graph G. For anyv ∈V(G), there is exactly one node t∈V(TT)such that tis labelled with forget(v).

IProposition 2.4(Theorem 7.23 in [10], [23, 28]). There exists an O(n²)time algorithm that given an n-vertex planar graphGandt∈N, either outputs a (nice) tree decomposition of Gof width less than5t, or constructs at×tgrid minor in G.

Map graphs. Map graphs are the intersection graphs of finitely many connected and interior- disjoint regions of the Euclidean plane. Map graphs can be represented as thehalf-squares of planar bipartite graphs. For a bipartite graph B with bipartition V(B) =W ]U, the half-square ofB is the graphGwith vertex setW and edge set is defined as follows: two vertices inW are adjacent inGif they are at distance 2 inB. It is known that the half-square of a planar bipartite graph is a map graph [7, 8]. Moreover, for any map graphG, there exists a planar bipartite graphB such thatGis a half-square ofB [7, 8]; we refer to suchB as a planar bipartite graphcorresponding to the map graphG(see Figure 1).

Throughout this paper, we assume that any input map graphGis given with a corres- ponding planar bipartite graphB. This assumption is made without loss of generality in the sense that ifGis given with an embedding instead to witness that it is a map graph, thenB is easily computable in linear time [7, 8]. We remark that we consider map graphs as simple graphs, that is, there are no multiple edges between two verticesuandv, even if there are two or more internally vertex-disjoint paths of length 2 betweenuandv inB. For a map graph Gwith a corresponding planar bipartite graphB having bipartition V(B) =W ]U, we refer to the vertices inW =V(G) simply asverticesand the vertices inU asspecial vertices.

•

•

•

• (a)A mapM.

•

•

•

• v₁

v3

v₄

v2 (b)A map graphGas- sociated withM.

v1

v3

v4

v2

r

•

•

•

•

•

(c)A corresponding planar bipartite graphB of the map graphG. Here, red colored vertices are special vertices.

r r r r

r

r r

∅

v1 r v2 r v3 r v4 r v1 v2 v3 v4

(d) A tree decomposition D = (TD, βD) of B of width < 2. The nodes colored blue, green, red, and yellow are labelled withintroduce(vi), introduce(r),forget(vi) andjoin, resp.

Figure 1Example of a map graphG, and a corresponding planar bipartite graphB. Figure 1d represents a tree decomposition ofB(obtained after deleting the leaves of a nice tree decomposition).

Moreover, we denote the special vertices byS(G). Notice that for anys∈S(G),N_B(s) forms a clique inG; we refer to these cliques asspecial cliquesofG. We remark that the collection K of cliques mentioned in Section 1 refers to{N_B(s) :s∈S(G)} ∪ {{v}:v∈V(G)}.

3 Few Cliques Tree Decomposition of Map Graphs

In this section, we define a special tree decomposition for map graphs. This decomposition will be derived from a tree decomposition of the bipartite planar graph corresponding to the given map graph. Once we have defined our new decomposition, we will gather a few of its structural properties that will be useful in designing fast subexponential time algorithms.

IDefinition 3.1. Let Gbe a map graph with a corresponding planar bipartite graphB. Let D= (T_D, β_D)be a tree decomposition of B of width less than`. A pairD<sup>0</sup>= (T<sub>D</sub><sup>0</sup>, β<sub>D</sub><sup>0</sup>)is called the `-few cliques tree decomposition derived from D, or simply an (`,D)-FewCliTD, if it is constructed as follows (see Figure 2).

1. The treeT_D⁰ is equal toT_D. WheneverD⁰ andD are clear from context, we denote both TD⁰ andTD by T.

2. For each node t∈V(T),β_D⁰(t) = (β_D(t)∩V(G))∪(S

s∈βD(t)∩S(G)NB(s)∩γ_D(t)). That is, for each nodet∈V(T), we deriveβ_D0(t) fromβ_D(t) by replacing every special vertex s∈β_D(t)∩S(G)byNB(s)∩γ_D(t).

In words, the second item states that for every vertexv∈V(G) and nodet∈V(T), we have that v∈β_D⁰(t) if and only if either (i)v ∈β_D(t)∩V(G) or (ii)v ∈NB(s) for some s∈S(G)∩βD(t) andv∈βD(t⁰) for some node t⁰ in the subtree ofT rooted att.

We can prove that the (`,D)-FewCliTD(T, β_D⁰) in Definition 3.1 is a tree decomposition ofG(see the full version of the paper for a proof). We remark that if we replace the term NB(s)∩γ_D(t) by the termNB(s) in the second item of Definition 3.1, then we still derive a tree decomposition, but then some of the properties proved later do not hold true.

To simplify statements ahead, from now on, we have the following notation.

Throughout the section, we fix a map graphG, a corresponding planar bipartite graphB ofG, an integer`∈N, a nice tree decompositionDofB of width less than`and an`-few cliques tree decomposition D⁰ ofGderived fromDusing Definition 3.1

Recall that T =T_D =T_D⁰ and that for each node t∈V(T),β_D⁰(t) was obtained from βD(t) by replacing every special vertexs∈S(G) withNB(s)∩γD(s).

IDefinition 3.2. For a nodet∈V(T), we useOriginal(t) to denote the setβD(t)∩βD⁰(t), Fake(t) to denote the set β_D⁰(t)\β_D(t), and Cliques(t) to denote the set {NB(s) : s ∈ S(G)∩β_D(t)} of special cliques ofG.

Informally, for a nodet∈V(T),Original(t) denotes the set of vertices ofV(G) present in the bagβ_D(t),Fake(t) denotes the set of “new” vertices added toβ_D⁰(t) while replacing special vertices inβ_D(t), andCliques(t) is the set of special cliques in Gthat consist of one for each special vertexs∈β_D(t). For example, lett be the node in Figure 1d that is labelled with forget(v₁) byD. Then,Original(t) =∅, Fake(t) ={v₁}andCliques(t) ={{v₁, . . . , v₄}}.

In the remainder of this section we prove properties related to D andD⁰, which we use later in the paper. Towards the formulation of the first property, consider the tree decompositionD⁰ in Figure 2 and the set of its nodes whose bags contain the vertexv1as a

“fake” vertex. This set of nodes forms a path with one end-vertex being the unique node tv₁

ofT labelled with forget(v₁) byD and the other end-vertex being an ancestor oft_v1. In fact, the set of nodesQ={t∈V(T) :v1∈Fake(t) andr∈β_D(t)} forms the unique path in T fromt_v1 tot_r wheret_ris the unique child of the node labelled with forget(r) byD. This observation is abstracted and formalized in the following lemma.

ILemma 3.3. Let v∈V(G)and s∈S(G)such that v∈NB(s)and Q={t∈V(T) :v∈ Fake(t)ands∈β_D(t)} 6=∅. Letxbe the node in T labelled withforget(v)by D, andy be the unique child of the node labelled withforget(s) byD. Then,y is an ancestor of x, and

Qinduces a path inT which is the unique path betweenxandy inT.

Proof. First, we prove thatQinduces a (connected) subtree ofT. Suppose not. Then, there exist two connected componentsC1andC2ofT[Q] such that there exists a pathP inT from a vertex inC₁ to a vertex inC₂ whose internal vertices all belong toV(T)\Q. By Property (c) of the tree decompositionD, we have thats∈βD(t) for anyt∈V(P). Moreover, there is an internal vertexwofP such thatwis an ancestor of one of the end-vertices of P. This implies thatv∈γD(w), becausevbelong to the bags of the endpoints ofP (by the definition ofQandFake). As we have also shown thats∈β_D(t) for allt∈V(P), this implies that w∈Q, which is a contradiction. Hence, we have proved thatT[Q] is connected.

Next, we prove that T[Q] is a path such that one of its endpoints is a descendant of the other. Towards this, it is enough to prove that (i) for any distinctt, t⁰ ∈ Q, eithert is a descendant oft⁰ ort⁰ is a descendant oft. For the sake of contradiction, assume that there existt, t⁰∈Qsuch that neithert is a descendent oft⁰ nort⁰ is a descendent oft. By the definition ofQand becauset, t⁰∈Q, we have that v∈γD(t) andv∈γD(t⁰). Thus by Property (c) of the tree decomposition D, we have thatv∈β_D(t) andv∈β_D(t⁰). Because v∈Fake(t) andv∈Fake(t⁰), this is a contradiction to the definition ofFake.

It remains to prove thaty is an ancestor ofxand thatxandy are endpoints ofT[Q].

First, we prove thatxis an end-vertex of the pathT[Q]. Letx⁰ be the only child ofx. To provexis an end-vertex of the pathT[Q], it is enough to show thatx∈Qandx⁰∈/Q. Since xis labelled withforget(v) byD, we have thatv /∈β_D(x),v∈β_D(x⁰), and v∈γ_D(x). This implies thatv∈Original(x⁰) and hencex⁰ ∈/ Q. Now, we prove thatx∈Q. For this purpose, letR={t∈V(T) :s∈β_D(t)}. Clearly,Q⊆R. By Property (c) of the tree decomposition D, we have thatT[R] is connected. We have already proved thatT[Q] is a path and since Q⊆R,T[Q] is a path inT[R]. Sincexis labelled withforget(v) by D, for any nodex⁰⁰in the subtree rooted atxandx⁰⁰6=x, eitherv∈β_D(x⁰⁰) orv /∈γ_D(x⁰⁰) (this fact follows from Property (c) of D). This implies thatQcontains no node in the subtree ofT rooted atx and not equal tox. Moreover, observe that there exists a nodex^? in the subtree ofT rooted

∅

v₁ v₂ v₃ v₄ v1v2v3v4

v1v2 v3v4

v1 v2 v3 v4

v₁ v₂ v₃ v₄

fake introduce(vi)

introduce(vi) join

redundant join

forget({v1, v2, v3, v4})

Figure 2An (`,D)-FewCliTD D⁰derived from the nice tree decompositionDin Figure 1d using Definition 3.1. The labels of the nodes inD⁰ are mentioned on the right.

atxsuch that{s, v} ⊆β_D(x^?) and hencex^?∈R. Now, sinceQis non-empty andT[Q] is connected, we have thats∈β_D(x). Sincev /∈β_D(x),v∈γ_D(x) ands∈β_D(x), we conclude thatx∈Q. Thus, we have proved thatxis an end-vertex of the the pathT[Q].

Next we prove that y is the other end-vertex of the path T[Q] andy is an ancestor of x. Sincey is the only child of the nodey⁰ labelled withforget(s), we have thats∈β_D(y) ands /∈β_D(y⁰). This implies thaty⁰∈/Q. Thus to prove thaty is an end-vertex of the path T[Q], it is enough to prove thaty ∈Q. Since s∈β_D(x),s∈β_D(y),s /∈β_D(y⁰) andy⁰ is the parent ofy, by Property (c) ofD, we have thaty is an ancestor ofx. This also implies that v∈γ_D(y) andv /∈β_D(y). Hence,y∈Q. This completes the proof of the lemma. J In the next lemma we show that for any special vertex s∈S(G) and any nodet inT labelled with introduce(s) byD, it holds thattand its child carry the “same information”.

ILemma 3.4(?). Let s∈S(G)andt be a node inT labelled with introduce(s)byD. Let t⁰ be the only child oft. Then,Original(t) =Original(t⁰)andFake(t) =Fake(t⁰).

Next, we see a property of nodes t∈V(T) labelled withjoin.

ILemma 3.5(?). Lett be a node inT labelled withjoin by D, andt1 andt2 are its chil- dren. Then,Original(t) =Original(t₁) =Original(t₂),Cliques(t) =Cliques(t₁) =Cliques(t₂), Fake(t1)∩Fake(t2) =∅, andFake(t) =Fake(t1)∪Fake(t2).

Now, we define a notion ofnice `-few cliques tree decomposition ofGas the tree decom- position ofGderived from a nice tree decompositionDofB of width< `(see Definition 3.1) with additional labeling of nodes. In what follows, we describe this additional labeling of nodes. Towards this, observe that because of Lemma 3.4, for any special vertex s∈S(G) and any nodet∈V(T) labelled withintroduce(s) byD, the bagsβD⁰(t) andβD⁰(t⁰) carry the “same information” wheret⁰ is the only child oft. Informally, one may choose to handle these nodes by contracting them. However, to avoid redundant proofs ahead, instead of getting rid of such nodes, we label them with redundantinD⁰. Next, we explain how to label other nodes ofT in the decompositionD⁰ (see Figure 2). To this end, lett∈V(T).

Ift is labelled withleaf byD, then we labeltwith leaf. Here,βD⁰(t) =∅.

If t is labelled with introduce(v) by D for some v ∈ V(G), then we label t with introduce(v). In this case, thas only one childt⁰ in T andβ_D⁰(t)\ {v}=β_D⁰(t⁰).

If tis labelled withforget(v) byDfor somev∈V(G) andv∈Fake(t), then we labelt withfake introduce(v). In this case,t has only one childt⁰ andβ_D⁰(t) =β_D⁰(t⁰), but Original(t) =Original(t⁰)\ {v} andFake(t) =Fake(t⁰)∪ {v}.

If t is labelled with forget(v) by D for some v ∈ V(G) and v /∈ Fake(t), then we label t with forget(v). In this case, t has only one child t⁰, β_D⁰(t) = β_D⁰(t⁰)\ {v}, Original(t) =Original(t⁰)\ {v}andFake(t) =Fake(t⁰).

Supposetis labelled withforget(s) by Dfor some s∈S(G). Then,t has only one child t⁰. Here, we labelt with forget(β_D⁰(t⁰)\β_D⁰(t)). In this case, Fake(t)⊆Fake(t⁰) and Original(t) =Original(t⁰).

Ift is labelled withjoinby D, then we labeltwith join. Lett₁andt₂ be the children of t. Then, Original(t) =Original(t1) =Original(t2),Cliques(t) =Cliques(t1) =Cliques(t2), Fake(t1)∩Fake(t2) =∅, andFake(t) =Fake(t1)∪Fake(t2). (See Lemma 3.5).

Iftis labelled with introduce(s) for somes∈S(G), then we labeltwithredundant.

This completes the definition of the nice`-few cliques tree decomposition ofGderived fromD, to which we simply call an (`,D)-NFewCliTD. Notice that for each nodet in T,

|Original(t)|+|Cliques(t)| ≤`. That is, for any nodet∈V(T), there existi, j∈Nsuch that i+j≤`, the cardinality ofOriginal(t) is at mosti, and the vertices in βD⁰(t)\Original(t) were obtained from at most j special cliques. From now on, we assume that D⁰ is an (`,D)-NFewCliTDof a map graphG.

Since the number of nodes with labelforget(v) in the tree decompositionDis exactly one for anyv∈V(B) (see Observation 2.3), at most one node inT is labelled with fake introduce(v) in D⁰. This is formally stated in the following observation.

IObservation 3.6. Let t∈V(T) andv∈Fake(t). Then,

(i) there is a unique node t⁰∈V(T)such that t⁰ is labelled withfake introduce(v)inD⁰, (ii) t is an ancestor oft⁰ or t=t⁰, and

(iii) for any node t⁰⁰ in the unique path between tandt⁰, we have thatv∈Fake(t⁰⁰).

The correctness of Observation 3.6 follows from Observation 2.3 and Lemma 3.3. The discussion above, along with Proposition 2.4, implies the following lemma.

ILemma 3.7 (?). Given a map graph G, a corresponding planar bipartite graph B, and an integer`∈N, in timeO(n<sup>2</sup>), one can either correctly conclude that B contains an`×` grid as a minor, or compute a nice tree decompositionDof B of width less than5`and a (5`,D)-NFewCliTDof G.

Lastly, we prove an important property ofD⁰. In particular, the edges considered in the following lemma are precisely those that connect the vertices “already seen” (when we use dynamic programming (DP)) with vertices to “see in the future”.

ILemma 3.8. For any nodet∈V(T), the edges with one endpoint inγ_D⁰(t)and other in V(G)\γ_D⁰(t)are of two kinds: (i)edges incident with vertices in Original(t), and(ii)edges belonging to some special clique in Cliques(t)(these edges are incident to vertices inFake(t)).

Proof. Fixt∈V(T). SinceD⁰ is a tree decomposition ofG, for any edgee∈E(G) with one endpoint inγ_D⁰(t) and other inV(G)\γ_D⁰(t), the endpoint of ein γ_D⁰(t) should belong to βD⁰(t). Letube the endpoint ofethat belongs toβD⁰(t), andvbe the other endpoint of e.

Notice that the setβ_D⁰(t) is partitioned intoOriginal(t) andFake(t), soubelongs to either Original(t) orFake(t), and in the former case we are done. We now assume thatu∈Fake(t).

Since{u, v}=e∈E(G), there is a special vertexs∈S(G) such that{u, s},{v, s} ∈E(B).

If s ∈ β_D(t), then the edge {u, v} belongs to the special clique K = N_B(s) in G and K∈Cliques(t). We claim that indeeds∈βD(t). Towards this, notice thatu∈Fake(t). This implies thatu /∈β_D(t), butuis present in a bagβ_D(t⁰) of some descendantt⁰ oft. Moreover, since{u, s} ∈E(B), we further know that{u, s} ⊆βD(t1) for some descendentt1oft. Since

{v, s} ∈E(B) andv /∈γD⁰(t), there is a bagβD(t2) such that{v, s} ⊆βD(t2) andt2 is not a descendent oft. Thus, sinces∈β_D(t1)∩β_D(t2), by Property (c) of the tree decomposition D, we have thats∈β_D(t). This completes the proof of the lemma. J

4 Longest Cycle

In this section we prove the following theorem.

ITheorem 4.1. Longest Cycleon map graphs can be solved in 2^O(

√

klogk)·n^O(1) time.

Notice that if there is a special vertex s∈S(G) such that|N_B(s)| ≥k, thenGhas a cycle of length at leastk, becauseNB(s) forms a clique in G. Moreover, observe that if there is a “large enough” grid inB, then we can answerYes. These observations along with Lemma 3.7 lead to the following lemma.

ILemma 4.2(?).There is an algorithm that given an instance(G, B, k)of Longest Cycle, runs in timeO(n²), and either correctly concludes thatGhas a cycle of length at leastk, or outputs a nice tree decompositionDof B of width <5√

2k and a(5√

2k,D)-NFewCliTDD⁰ ofG such that for each nodet∈V(T),|βD⁰(t)| ≤5√

2·k^1.5.

Because of Lemma 4.2, to prove Theorem 4.1, we may assume that the input contains a (5√

2k,D)-NFewCliTD D⁰ of G (derived from a nice tree decomposition D of B) such that for each node t∈V(T),|βD⁰(t)| ≤5√

2·k^1.5. That is, from now on, we fix our input to be an instance (G, B, k) of Longest Cycle, a nice tree decomposition D of B and a (5√

2k,D)-NFewCliTDD⁰ of G such that for each nodet ∈V(T), |β_D⁰(t)| ≤ 5√ 2·k^1.5. Towards the proof of Theorem 4.1, the main ingredient is to prove the following claim: ifG has a cycle of length`, then there is a cycleC of length`, with the following property.

For each nodet∈V(T), the number of edges ofE(C) with one endpoint inβ_D⁰(t) and the other inV(G)\γ_D⁰(t) is upper bounded byO(√

k).

The above mentioned property is encapsulated in the following sublinear crossing lemma.

ILemma 4.3(Sublinear Crossing Lemma (?)). LetC be a cycle in G. Then there is a cycle C⁰ of the same length as C such that for any nodet∈V(T), the number of edges in E(C⁰) with one endpoint in β_D⁰(t)and the other inV(G)\γ_D⁰(t)is at most20√

2k.

Lemma 4.3 lies at the heart of the proof of Theorem 4.1 and is one of the main technical contributions of the paper. Assuming Lemma 4.3, the proof of Theorem 4.1 is by designing a DP algorithm on a (5√

2k,D)-NFewCliTDofG. This part is similar to the algorithm for Longest Cyclein [20] on a so calledspecial path decomposition. The main ingredient of Lemma 4.3 is the following lemma (Lemma 4.4). The proof of Lemma 4.3 is by an inductive argument assuming Lemma 4.4. The rest of the section is devoted to the proof of Lemma 4.4.

I Lemma 4.4. Let C be a cycle in G and K be a special clique in G. Then, there is a cycleC⁰ of the same length asC such that E(C⁰)\E(K) =E(C)\E(K)and for any node t∈V(T), the number of edges of E(C⁰)∩E(K)with one endpoint inFake(t)∩K and the other inV(G)\γ_D⁰(t)is at most4.

Before formally proving Lemma 4.4, we give a high level overview of the proof and an auxiliary lemma which we use in the proof of Lemma 4.4. The proof idea is to change the edges ofE(K)∩E(C) in C(because in Lemma 4.4 our objective is to bound the “crossing edges” from a subset ofE(K) for each nodet∈V(T)) to obtain a new cycleC⁰ of the same

length asC that satisfies the following property: (i) for any nodet∈V(T), the number of edges ofE(C⁰)∩E(K) with one endpoint inFake(t)∩K and the other inV(G)\γ_D⁰(t) is at most 4. For the ease of presentation, assume thatK⊆V(C). Now, consider the graphP obtained from the cycleC after deleting edges inE(K). Without loss of generality assume thatE(C)∩E(K)6=∅. Otherwise, Lemma 4.4 is true whereC⁰ =C. We considerP as a collection of vertex-disjoint paths where the end-vertices of the paths are inK. Some paths inP may be of length 0. LetZ be the set of end-vertices of the paths in P. Clearly,Z⊆K.

We will “complete” the collection of pathsP to a cycle by adding edges fromE(Z) satisfying Statement (i). Any cycle C⁰ withV(C⁰) =V(P) has the same length asC. So, all the work that is required for us is to complete the collection of pathsP to a cycle by adding edges from E(Z) satisfying Statement (i). Towards that, let bσ=v1, . . . , vk⁰ be an arbitrary sequence of vertices inZ. We show (in Claim 4.7) that (ii) there is a subset of edgesF ⊆E(Z) such thatE(P)∪F forms a cycleC⁰ with vertex setV(P) and for anyj ∈[k⁰], the number of edges inF with one endpoint in{v₁, . . . , vj} and the other in{vj+1, . . . , vk⁰}is at most 2.

This implies that for any 1≤i≤j ≤k⁰, the number of edges inF with one endpoint in {vi, . . . , vj} and the other in Z\ {vi, . . . , vj} is at most 4. In the light of Statement (ii), our aim will be to prove that (iii) for any node t∈V(T), there exist 1≤i≤j ≤k⁰ such thatFake(t)∩Z ⊆ {vi, . . . , vj} and no vertex in Z\γ_D⁰(t) belongs to{vi, . . . , vj}. Then, Statement (i) will follow (because edges of C⁰ incident with vertices in K\Z are from E(G)\E(K) and will not be counted in Statement (i)). In fact, we will prove that there is a sequenceσonZ (derived from a postorder transversal ofT) such that Statement (iii) is true (see Claim 4.8). The proof of Statement (ii) is encapsulated in the following lemma.

ILemma 4.5(?). Let`≥3be an integer. Letu<sub>1</sub>, . . . , u<sub>`</sub>be a sequence of vertices in a graph H whereX ={u1, . . . , u`} is a clique inH. LetQbe a family of vertex-disjoint paths inH (which possibly contains paths of length0) such that eachv∈X is an end-vertex of a path in

QandE(Q)∩E(X) =∅. Then, there is a setF ⊆E(X) with the following conditions.

(a) E(Q)∪F forms a cycle containing all the vertices of V(Q),

(b) For any j ∈[`], the number of edges in F with one endpoint in {u1, . . . , uj} and the other in{uj+1, . . . , u`} is at most2.

Next, we move to a formal proof of Lemma 4.4.

Proof of Lemma 4.4. Without loss of generality, assume that K⊆V(C). Otherwise, we can consider the statement of the lemma for cycleC in the graphG⁰=G−(K\V(C)) and special cliqueK∩V(C) ofG⁰. We also assume thatE(C)∩E(K)6=∅, else the correctness is trivial because we can takeC⁰ asC.

Letπ⁰ be a postorder transversal of the nodes in the rooted binary treeT, and letπbe the restriction ofπ⁰ where we only keep the nodes that are labeled withfake introduce(v) for some v ∈ K. Denote π = t1, . . . , tk⁰⁰ such that each ti, i ∈ [k⁰⁰], is labelled with fake introduce(xi) wherexi ∈K. Notice that S

t∈V(T)Fake(t)∩K ={x1, . . . , xk⁰⁰} (by Observation 3.6). Letσ₁ be the sequence x₁, . . . , x_k⁰⁰ andU ={x1, . . . , x_k⁰⁰}. Letσ₂ be a fixed arbitrary sequence ofK\U, i.e., all the vertices ofKthat are never “fakely introduced”.

Letσbe the sequence which is a concatenation ofσ₁andσ₂.

Let P = (V(C), E(C)\E(K)). That is, P is the graph obtained by deleting edges of E(K) from the cycleC. Notice that each connected component ofP is a path (may be of length 0) with end-vertices inK. LetZ be the set of end-vertices of the paths inP. Notice that for any vertexu∈K\Z, both edges ofC incident withuare fromE(C)\E(K) (see the left part of Figure 3). That is, E(C)\E(K) =E(C)\E(Z) =E(P). Since we seek a cycleC⁰ in whichE(C⁰)\E(K) =E(C)\E(K), no edge ofC⁰ incident withufor any vertexu∈K\Z, is inE(K). That is, all the edges ofE(C⁰)∩E(K) will belong toE(Z).

v1 v2 v3 v4 v5 v6 v7 v1 v2 v3 v4 v5 v6 v7

Figure 3Left part illustrates a cycleCinteracting with a special cliqueK={v1, . . . , v7}. The red curves represent edges inE(C)∩E(K) and green curves represent paths inC with endpoints in K and (at least one) internal vertices in V(G)\K. Thus, P is the collection of paths that is a union of the set of two “green” paths ((v2−v3) and (v1−v7−v5−v6)) and {[v4]}. Here Z={v1, v2, v3, v4, v6}. Any edge ofE(C) incident withv5 andv7 (i.e., vertices inK\Z) are from E(C)\E(K). The right part illustrates the proof of Claim 4.7. The edges ofE(C⁰)\E(C) mentioned in the proof of Claim 4.7 are colored blue.

IObservation 4.6. LetC⁰ be a cycle in Gsuch that E(C⁰)\E(K) =E(C)\E(K) and t∈V(T). The number of edges ofE(C⁰)∩E(K)with one endpoint inFake(t)∩K and the other inV(G)\γ_D⁰(t)is equal to the number of edges ofE(C⁰)∩E(Z)with one endpoint in Fake(t)∩Z and the other inV(G)\γ_D⁰(t).

LetZ ={v₁, . . . , v_k⁰}and σ⁰=σ|_Z =v₁, . . . , v_k⁰. The main ingredients of the proof are the following two claims.

BClaim 4.7. There is a cycleC⁰ of the same length asC such that (i)E(C⁰)\E(Z) = E(C)\E(Z), and (ii) for any j ∈ [k⁰], the number of edges of E(C⁰)∩E(Z) with one endpoint in{v1, . . . , vj}and the other in {vj+1, . . . , vk⁰}is at most 2.

The proof of Claim 4.7 follows from Lemma 4.5.

BClaim 4.8. For any nodet∈V(T), there is a segmentσ⁰⁰ ofσ⁰ such that each vertex in Fake(t)∩Z appears inσ⁰⁰, and each vertex inZ\γ_D⁰(t) does not appear inσ⁰⁰.

Proof. Fix a nodet∈V(T). Recall thatσ=σ₁σ₂ andσ⁰=σ|Z. Here, the set of vertices present inσ1 isU = (S

t∈V(T)Fake(t)∩K)⊇(S

t∈V(T)Fake(t)∩Z) (becauseZ⊆K), and no vertex inσ₂is fromU. This implies that all the vertices ofFake(t)∩Z are in the sequence σ1. That is, the sequence σ⁰⁰ we seek is also a sequence ofσ1|Z and this is the reason we definedσto beσ1σ2. Thus, to prove the claim it is enough to prove that there is a segment σ⁰₁ofσ₁|Z such that each vertex inFake(t)∩Z appears inσ⁰₁ and each vertex inZ\γ_D0(t) does not appear inσ⁰₁.

Recall that σ₁=x₁. . . x_k⁰⁰ is obtained from the sequenceπ=t₁, . . . , t_k⁰⁰. In turn, recall thatπ is the restriction of the postorder transversalπ⁰ of T, where for eachi∈[k⁰⁰],ti is labelled withfake introduce(x_i) forx_i∈K. LetW_tbe the nodes of the subtree ofT rooted att, andVt={v∈K: there ist⁰∈Wtsuch thatt⁰ is labelled withfake introduce(v)}.

The vertices inWtappear consecutively inπ. Thus, we can letπtbe the minimal segment ofπthat contains all the nodes in V_t. Leti, j∈[k⁰⁰] be such thatπ_t=t_i, . . . , t_j. Now, we defineσtbe the segmentxi, . . . , xj ofσ1. Now we prove the claim. By conditions (i) and (ii) in Observation 3.6,Fake(t)∩Z⊆V_t. Clearly, no vertex inZ\γ_D⁰(t) is inV_t. This implies that each vertex inFake(t)∩Z appears inσtand no vertex fromZ\γ_D⁰(t) appears inσt. In turn, this implies thatσ_t|_Z is the required segmentσ⁰⁰ ofσ⁰=σ|_Z. C Now, having the above two claims, we are ready to prove the lemma. By Claim 4.7, we have that there is a cycleC⁰ such that (i)E(C⁰)\E(Z) =E(C)\E(Z), and (ii) for any j∈[k⁰], the number of edges ofE(C)∩E(Z) with one endpoint in{v₁, . . . , vj}and other in {vj+1, . . . , vk⁰}is at most 2. By Claim 4.8, we know that for anyt∈V(T), there is a segment