# «Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors Erik D. Demaine1, MohammadTaghi ...»

Algorithmica manuscript No.

(will be inserted by the editor)

Exponential Speedup of Fixed-Parameter Algorithms

for Classes of Graphs Excluding Single-Crossing

Graphs as Minors

Erik D. Demaine1, MohammadTaghi Hajiaghayi1, Dimitrios M. Thilikos2

MIT Computer Science and Artiﬁcial Intelligence Laboratory, 32 Vassar St., Cambridge,

MA 02139, USA, e-mail: {edemaine,hajiagha}@mit.edu

Departament de Llenguatges i Sistemes Inform` tics, Universitat Polit` cnica de Catalunya,

a e Campus Nord – M` dul C5, c/Jordi Girona Salgado 1-3, E-08034, Barcelona, Spain, eo mail: sedthilk@lsi.upc.es The date of receipt and acceptance will be inserted by the editor

**Abstract**

We present a ﬁxed-parameter algorithm that constructively solves the k-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in √ O(49.55 k nO(1) ) time. Examples of such graph classes are the K3,3 -minor free graphs and the K5 -minor-free graphs. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set, and a collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing ﬁxed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.

1 Introduction According to a 1998 survey book [HHS98], there are more than 200 published research papers on solving domination-like problems on graphs. Because this problem is very hard and NP-complete even for special kinds of graphs such as planar graphs, much attention has focused on solving this problem on a more restricted class of graphs. It is well-known that this problem can be solved on trees [CGH75] A preliminary version of this paper appeared in the Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002). The work of the third author was supported by the IST Program of the EU under contract number IST-99ALCOM-FT) and by the Spanish CYCIT TIC-2000-1970-CE.

Supported by the EU within the 6th Framework Programme under contract 001907 (DELIS) and by the Spanish CICYT project TIC-2002-04498-C05-03 (TRACER).

2 Erik D. Demaine et al.

or even the generalization of trees, graphs of bounded treewidth [TP93]. The approximability of the dominating set problem has received considerable attention, but it is not known and it is not believed that this problem has constant-factor approximation algorithms on general graphs [ACG+ 99].

Downey and Fellows [DF99] introduced a new concept to handle NP-hardness called ﬁxed-parameter tractability. Unfortunately, according to this theory, it is very unlikely that the k-dominating set problem has an efﬁcient ﬁxed-parameter algorithm for general graphs. In contrast, this problem is ﬁxed-parameter tractable on planar graphs. Alber et al. [ABF+ 02] demonstrated a solution to the planar √ k-dominating set in time O(46 34k n). Indeed, this result was the ﬁrst nontrivial result for the parameterized version of an NP-hard problem where the exponent of the exponential term grows sublinearly in the parameter. Recently, the √ running time of this algorithm was further improved to O(227 k n) [KP02] and √ O(215.13 k k + n3 + k 4 ) [FT03]. One of the aims of this paper is to generalize this result to nonplanar classes of graphs.

A graph G is H-minor-free if H cannot be obtained from any subgraph of G by contracting edges. A graph is called a single-crossing graph if it can be drawn in the plane with at most one crossing. Similar to the approach of Alber et al., we prove that for a single-crossing graph H, the treewidth of any H-minor-free √ graph G having a k-dominating set is bounded by O( k). We note that planar graphs are both K3,3 -minor-free and K5 -minor-free, where K3,3 and K5 are both single-crossing graphs. As a result, we generalize current exponential speedup in ﬁxed-parameter algorithms on planar graphs to other kinds of graphs by showing how we can solve the k-dominating set problem on √ class of graphs excluding any a single-crossing graph as a minor in time O(49.55 k nO(1) ). The genesis of our results lies in a result of Hajiaghayi et al. [HNRT01, DHN+ 04] on obtaining the local treewidth of the aforementioned class of graphs.

Using the solution for the k-dominating set problem on planar graphs, Kloks et al. [CKL01,KLL02,GKL01] and Alber et al. [ABF+ 02, AFN04] obtained exponential speedup in solving other problems such as vertex cover, independent set, clique-transversal set, kernels in digraph and feedback vertex set on planar graphs.

In this paper we also show how our results can be extended to these problems and many other problems such as variants of dominating set, edge dominating set, and a collection of vertex-removal problems.

Since the results of this paper were announced, several new papers have been developed by using and extending the results and techniques of this paper; see, e.g., [DHN+ 04,FT03,DFHT,DH04a,DFHT04b, DFHT04a, DHT04].

This paper is organized as follows. First, we introduce the terminology used throughout the paper, and formally deﬁne tree decompositions, treewidth, and ﬁxed-parameter tractability in Section 2. In Section 3, we introduce the concept of clique-sum, we prove two√ general theorems concerning the construction of tree decompositions of width O( k) for these graphs, and ﬁnally we consider the design of fast ﬁxed-parameter algorithms for them. In Section 4, we apply our general results to the k-dominating set problem, and in Section 5, we describe how this result can be applied to derive fast ﬁxed-parameter algorithms for many difTitle Suppressed Due to Excessive Length 3 ferent parameters. In Section 6, we prove some graph-theoretic results that provide a framework for designing ﬁxed-parameter algorithms for a collection of vertexremoval problems. In Section 7, we give some further extensions of our results to graphs with linear local treewidth. We end with some conclusions and open problems in Section 8.

2 Background

2.1 Preliminaries We assume the reader is familiar with general concepts of graph theory such as (un)directed graphs, trees and planar graphs. The reader is referred to standard references for appropriate background [BM76]. In addition, for exact deﬁnitions of various NP-hard graph-theoretic problems in this paper, the reader is referred to Garey and Johnson’s book on computers and intractability [GJ79].

Our graph terminology is as follows. All graphs are ﬁnite, simple and undirected, unless indicated otherwise. A graph G is represented by G = (V, E), where V (or V (G)) is the set of vertices and E (or E(G)) is the set of edges. We denote an edge e in a graph G between u and v by {u, v}. We deﬁne n to be the number of vertices of a graph when it is clear from context. We deﬁne the r-neighborhood r of a set S ⊆ V (G), denoted by NG (S), to be the set of vertices at distance at most r from at least one vertex of S ⊆ V (G); if S = {v} we simply use the notation r NG (v). The union of two disjoint graphs G1 and G2, G1 ∪ G2, is a graph G such that V (G) = V (G1 ) ∪ V (G2 ) and E(G) = E(G1 ) ∪ E(G2 ).

For generalizations of algorithms on undirected graphs to directed graphs, we consider underlying graphs of directed graphs. The underlying graph of a directed graph H is the undirected graph G in which V (G) = V (H) and {u, v} ∈ E(G) if and only if (u, v) ∈ E(H) or (v, u) ∈ E(H).

One way of describing classes of graphs is by using minors, introduced below.

Deﬁnition 1 Contracting an edge e = {u, v} is the operation of replacing both u and v by a single vertex w whose neighbors are all vertices that were neighbors of u or v, except u and v themselves. A graph G is a minor of a graph H if G can be obtained from a subgraph of H by contracting edges. A graph class C is a minorclosed class if any minor of any graph in C is also a member of C. A minor-closed graph class C is H-minor-free if H ∈ C.

For example, a planar graph is a graph excluding both K3,3 and K5 as minors.

2.2 Treewidth

Deﬁnition 2 ([RS86]) A tree decomposition of a graph G = (V, E), denoted by T D(G), is a pair (χ, T ) in which T = (I, F ) is a tree and χ = {χi | i ∈ I} is a

**family of subsets of V (G) such that:**

1. i∈I χi = V ;

2. for each edge e = {u, v} ∈ E there exists an i ∈ I such that both u and v belong to χi ; and

3. for all v ∈ V, the set of nodes {i ∈ I | v ∈ χi } forms a connected subtree of T.

To distinguish between vertices of the original graph G and vertices of T in T D(G), we call vertices of T nodes and their corresponding χi ’s bags. The maximum size of a bag in T D(G) minus one is called the width of the tree decomposition. The treewidth of a graph G, denoted tw(G), is the minimum width over all possible tree decompositions of G.

Many NP-complete problems have linear-time or polynomial-time algorithms when they are restricted to graphs of bounded treewidth. There are a few techniques for obtaining such algorithms. The main technique is called computing tables of characterizations of partial solutions. This technique is a general dynamic programming approach, ﬁrst introduced by Arnborg and Proskurowski [AP89].

Bodlaender [Bod97] gave a better presentation of this technique. Other approaches applicable for solving problems on graphs of bounded treewidth are graph reduction [ACPS93, BdF96] and describing the problems in certain types of logic [ALS88, Cou90].

**2.3 Fixed-Parameter Tractability**

Developing practical algorithms for NP-hard problems is an important issue. Recently, Downey and Fellows [DF99] introduced a new approach to cope with this NP-hardness, namely ﬁxed-parameter tractability. For many NP-complete problems, the inherent combinatorial explosion is often due to a certain part of a problem, namely a parameter. The parameter is often an integer and small in practice.

The running times of simple algorithms may be exponential in the parameter but polynomial in the problem size. For example, it has been shown that k-vertex cover has an algorithm with running time O(kn + 1.271k ) [CKJ01] and hence this problem is ﬁxed-parameter tractable.

Deﬁnition 3 ([DF99]) A parameterized problem L ⊂ Σ ∗ × N is ﬁxed-parameter tractable (FPT) if there is an algorithm that correctly decides, for input (x, k) ∈ Σ ∗ × N, whether (x, k) ∈ L in time f (k)nc, where n is the size of the main part of the input x, |x| = n, k is a parameter (usually an integer), c is a constant independent of k, and f is an arbitrary function.

3 General Results on Clique-Sum Graphs

of Hajiaghayi et al. [HNRT01,Haj01] to obtain the local treewidth of clique-sum graphs, deﬁned formally below.

Deﬁnition 4 Suppose G1 and G2 are graphs with disjoint vertex-sets and k ≥ 0 is an integer. For i = 1, 2, let Wi ⊆ V (Gi ) form a clique of size k and let Gi (i = 1, 2) be obtained from Gi by deleting some (possibly no) edges from Gi [Wi ] with both endpoints in Wi. Consider a bijection h : W1 → W2. We deﬁne a k-sum G of G1 and G2, denoted by G = G1 ⊕k G2 or simply by G = G1 ⊕ G2, to be the graph obtained from the union of G1 and G2 by identifying w with h(w) for all w ∈ W1. The images of the vertices of W1 and W2 in G1 ⊕k G2 form the join set.

In the rest of this section, when we refer to a vertex v of G in G1 or G2, we mean the corresponding vertex of v in G1 or G2 (or both). It is worth mentioning that ⊕ is not a well-deﬁned operator and it can have a set of possible results. The reader is referred to Figure 1 to see an example of a 5-sum operation.

a sequence of i-sums (i ≤ s) applied to planar graphs and graphs in C. We call a graph clique-sum if it is a member of a clique-sum class. We call the pair (C, s) the deﬁning pair of G and we call the maximum treewidth of graphs in C the base of G and the base of graphs in G. A series of k-sums (not necessarily unique) which generate a clique-sum graph G are called a decomposition of G into clique-sum operations.

According to the (nonalgorithmic) result of [RS93], if G is the class of graphs excluding a single crossing graph (can be drawn in the plane with at most one crossing) H then G is a clique-sum class with deﬁning pair (C, s) where the base of G is bounded by a constant cH depending only on H. In particular, if H = K3,3, the deﬁning pair is ({K5 }, 2) and cH = 4 [Wag37] and if H = K5 then the deﬁning pair is ({V8 }, 3) and cH = 4 [Wag37]. Here by V8 we mean the graph obtained from a cycle of length eight by joining each pair of diagonally opposite vertices by an edge. For more results on clique-sum classes see [Die89].

From the deﬁnition of clique-sum graphs, one can observe that, for any cliquesum graph G which excludes a single crossing graph H as a minor, any minor G of G is also a clique-sum graph which excludes the same graph H as a minor.

We call a clique-sum graph class G α-recognizable if there exists an algorithm that for any graph G ∈ G outputs in O(nα ) time a sequence of clique-sums of graphs of total size O(|V (G)|) that constructs G. We call a graph α-recognizable if it belongs in some α-recognizable clique-sum graph class.

One of the ingredients of our results is the following constructive version of the result in [RS93].

Theorem 1 ([DHT02,DHN+ 04]) For any graph G excluding a single-crossing graph H as a minor, we can construct in O(n4 ) time a series of clique-sum operations G = G1 ⊕ G2 ⊕ · · · ⊕ Gm where each Gi, 1 ≤ i ≤ m, is a minor of G and is either a planar graph or a graph of treewidth at most cH. Here each ⊕ is a 0-, 1-, 2- or 3-sum.

In the remainder of the paper we assume that cH is the smallest integer for which Theorem 1 holds. Notice that, according to the terminology introduced before, any graph class excluding a single-crossing graph as a minor is a 4-recognizable clique-sum graph class. As particular cases of Theorem 1 we mention that K3,3 minor-free graphs are 1-recognizable [Asa85] and K5 -minor-free graphs are 2recognizable [KM92]. For more examples of graph classes that can be characterized by clique-sum decompositions, see the work of Diestel [Die89, Die91].