FREE ELECTRONIC LIBRARY - Books, abstracts, thesis

Pages:   || 2 | 3 | 4 | 5 |

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

-- [ Page 1 ] --

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 Artificial 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


We present a fixed-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 fixed-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 fixed-parameter tractability. Unfortunately, according to this theory, it is very unlikely that the k-dominating set problem has an efficient fixed-parameter algorithm for general graphs. In contrast, this problem is fixed-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 first 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 fixed-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 define tree decompositions, treewidth, and fixed-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 finally we consider the design of fast fixed-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 fixed-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 fixed-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 definitions 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 finite, 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 define n to be the number of vertices of a graph when it is clear from context. We define 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.

Definition 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

–  –  –

Definition 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, first 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 fixed-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 fixed-parameter tractable.

Definition 3 ([DF99]) A parameterized problem L ⊂ Σ ∗ × N is fixed-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, defined formally below.

Definition 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 define 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-defined 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 defining 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 defining 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 defining pair is ({K5 }, 2) and cH = 4 [Wag37] and if H = K5 then the defining 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 definition 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].

Pages:   || 2 | 3 | 4 | 5 |

Similar works:

«OFFICE OF INSPECTOR GENERAL City of Chicago REPORT OF THE OFFICE OF INSPECTOR GENERAL: ************************* CHICAGO POLICE DEPARTMENT ASSAULT-RELATED CRIME STATISTICS CLASSIFICATION AND REPORTING AUDIT APRIL 2014 866-IG-TIPLINE (866-448-4754) www.chicagoinspectorgeneral.org OFFICE OF INSPECTOR GENERAL City of Chicago 740 N. Sedgwick Street, Suite 200 Chicago, Illinois 60654 Joseph M. Ferguson Telephone: (773) 478-7799 Inspector General Fax: (773) 478-3949 April 4, 2014 To the Mayor,...»

«Versionskontrolle mit Subversion Für Subversion 1.5 (Übersetzt aus der r3473) Ben Collins-Sussman Brian W. Fitzpatrick C. Michael Pilato Inhaltsverzeichnis Geleitwort Vorwort 1. Publikum 2. Wie dieses Buch zu lesen ist 3. Konventionen in diesem Buch 4. Aufbau dieses Buchs 5. Dieses Buch ist frei 6. Danksagungen 6.1. Von Ben Collins-Sussman 6.2. Von Brian W. Fitzpatrick 6.3. Von C. Michael Pilato 7. Was ist Subversion? 7.1. Ist Subversion das richtige Werkzeug? 7.2. Die Geschichte von...»


«Biostatistics: Types of Data Analysis Theresa A Scott, MS Vanderbilt University Department of Biostatistics theresa.scott@vanderbilt.edu http://biostat.mc.vanderbilt.edu/TheresaScott Theresa A Scott, MS (Vandy Biostats) Data Analysis 1 / 29 Goals of data analysis (1) To describe (summarize) the population of interest by describing what was observed in the (study) sample. Employs descriptive statistics, which involves Summarizing continuous variables using the mean, standard deviation, range,...»

«Florida State University DigiNole Commons Electronic Theses, Treatises and Dissertations The Graduate School November 2013 Electromagnetic Interactions Between Metal Nanoparticles and Fluorescent Dipoles Christopher John Breshike Florida State University Follow this and additional works at: http://diginole.lib.fsu.edu/etd Recommended Citation Breshike, Christopher John, Electromagnetic Interactions Between Metal Nanoparticles and Fluorescent Dipoles (2013). Electronic Theses, Treatises and...»

«Revelation 1:1 1 Revelation 1:6 De Revelation Dis book laan we bout de ting dem wa Jedus Christ show ta dem people wa da do God wok. God fus show Jedus dem ting yah, so dat Jedus kin mek dem wa da do e wok know dem ting wa gwine happen tareckly. Christ sen e angel ta John wa beena wok fa um, an e mek de angel show John dem ting yah. 2 An John done tell we all dem ting wa e see. So den, dis de book yah weh John done write down de wod wa God sen. Dat de trute wa Jedus Christ esef show um. 3 E...»

«Postdoctoral Fellowship Application Deadlines  Founders Affiliate July 22, 2015  Great Rivers Affiliate July 22, 2015  Greater Southeast Affiliate July 23, 2015  Midwest Affiliate July 23, 2015  SouthWest Affiliate July 24, 2015  Western States Affiliate July 24, 2015 Award Activation: Jan. 1, 2016 Applications must be received no later than 5:00 p.m. CDT on the deadline date. The system will shut down at 5:00 p.m. CDT. Early submission is encouraged. Your institutional Grants...»

«MAYOR AND COUNCIL WORK SESSION AND AGENDA MEETING October 9, 2012 8:00 P.M.CALL TO ORDER SALUTE TO COLORS Mayor Maio invited all those present to stand in a salute to colors. MAYOR'S STATEMENT AS TO COMPLIANCE WITH P.L. 1975 Adequate Notice of this Meeting has been provided according to the Open Public Meetings Act, Assembly Bill 1030. Notice of this Meeting was included in the Annual Meeting Notice sent to the New Jersey Herald and the Daily Record on January 3, 2012 and was placed on the...»

«РОЛЬ ИНЦИДЕНТА ВОКРУГ ИЗДАНИЯ ВОСПОМИНАНИЙ Д. ШУМУКА «ЗА СХИДНЫМ ОБРИЕМ» В РАЗРЫВЕ «СМОЛОСКИПА» И ОУН (М) Омельковец Александр Ярославович аспирант, Институт археографии и источниковедения имени М. Грушевского Национальной академии наук Украины, Украина, г. Киев E-mail:...»

«УДК 614.8 А.П. Парфёненко (Академия Государственной противопожарной службы МЧС России; e-mail: parf01@inbox.ru) ПРОБЛЕМЫ ЭВАКУАЦИИ ДЕТЕЙ И ПОДРОСТКОВ ПРИ ПОЖАРАХ Аннотация. Проведён анализ особенностей эвакуации детей и подростков из зданий учебно-воспитательных учреждений при...»

«dhs: отдел по работе с детьми, взрослыми и семьями Руководство воспитателя по уходу за детьми Программа DHS по уходу за детьми Независимость. Здоровье. Надежность.Часто используемые номера телефонов: Название и адрес Местный номер Бесплатный номер 503-378-5500 1-800-699-9074 Отдел...»

«Interdisciplinary Master’s study program in Computer Science and Mathematics Study program cycle: Second cycle study program.Anticipated academic title: Master Engineer in Computer Science and Mathematics. In Slovenian: Magister inženir računalništva in matematike (masculine form) or Magistrica inženirka računalništva in matematike (feminine form), for either gender abbreviated to mag. inž. rač. mat. Duration: 2 full years (4 terms) based on 120 ECTS credits. Basic goals: The program...»

<<  HOME   |    CONTACTS
2016 www.book.xlibx.info - Free e-library - Books, abstracts, thesis

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.