Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos New York University, NY, USA Doug Tygar University of California, Berkeley, CA, USA Moshe Y. Vardi Rice University, Houston, TX, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany
3341
This page intentionally left blank
Rudolf Fleischer Gerhard Trippen (Eds.)
Algorithms and Computation 15th International Symposium, ISAAC 2004 Hong Kong, China, December 20-22, 2004 Proceedings
Springer
eBook ISBN: Print ISBN:
3-540-30551-3 3-540-24131-0
©2005 Springer Science + Business Media, Inc. Print ©2004 Springer-Verlag Berlin Heidelberg All rights reserved No part of this eBook may be reproduced or transmitted in any form or by any means, electronic, mechanical, recording, or otherwise, without written consent from the Publisher Created in the United States of America
Visit Springer's eBookstore at: and the Springer Global Website Online at:
http://ebooks.springerlink.com http://www.springeronline.com
Preface
This volume contains the proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), held in Hong Kong, 20–22 December, 2004. In the past, it has been held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), Vancouver (2002), and Kyoto (2003). ISAAC is an annual international symposium that covers a wide range of topics, namely algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in the active research community of algorithms and the theory of computation to present and exchange new ideas. In response to our call for papers we received 226 submissions. The task of selecting the papers in this volume was done by our program committee and other referees. After a thorough review process the committee selected 76 papers, the decisions being based on originality and relevance to the field of algorithms and computation. We hope all accepted papers will eventually appear in scientific journals in a more polished form. Two special issues, one of Algorithmica and one of the International Journal of Computational Geometry and Applications, with selected papers from ISAAC 2004 are in preparation. The best student paper award will be given for “Geometric optimization problems over sliding windows” by Bashir S. Sadjad and Timothy M. Chan from the University of Waterloo. Two eminent invited speakers, Prof. Erik D. Demaine, MIT, and Prof. David M. Mount, University of Maryland, also contributed to this volume. It is impossible to organize such a conference without the help of many individuals. We would like to express our appreciation to the authors of the submitted papers, and to the program committee members and external referees for their excellent work. We also would like to thank the organizing committee, most notably Gerhard Trippen, for their tremendous work in making ISAAC 2004 a successful conference. Finally, we thank our sponsors, the Croucher Foundation and the K.C. Wong Education Foundation, for their assistance and support.
October 2004
Rudolf Fleischer Gerhard Trippen
This page intentionally left blank
Organization
Program Committee Lars Arge, Duke University, USA Michael Bender, SUNY Stony Brook, USA Therese Biedl, University of Waterloo, Canada Adam Buchsbaum, AT&T Labs, Florham Park, USA Siu-Wing Cheng, HKUST, Hong Kong, China Xiaotie Deng, City University of Hong Kong, Hong Kong, China Rudolf Fleischer, Fudan University, China (Chair) Leszek Gasieniec, University of Liverpool, UK Seokhee Hong, University of Sydney, Australia Wen-Lian Hsu, Academia Sinica, Taipei, Taiwan Tak-Wah Lam, Hong Kong University, Hong Kong, China Guojun Li, Shandong University, China Tomomi Matsui, Tokyo University, Japan Christoph Meinel, University of Trier, Germany Friedhelm Meyer auf der Heide, University of Paderborn, Germany Mike Paterson, University of Warwick, UK Knut Reinert, Free University of Berlin, Germany Jörg-Rüdiger Sack, Carleton University, Canada Hiroki Shizuya, Tohoku University, Japan Jack Snoeyink, University of North Carolina at Chapel Hill, USA Roberto Solis-Oba, University of Western Ontario, Canada Ulrike Stege, University of Victoria, Canada John Watrous, University of Calgary, Canada Gerhard Woeginger, University of Twente, The Netherlands Hsu-Chun Yen, National Taiwan University, Taiwan
VIII
Organization
Organizing Committee Sunil Arya, HKUST, Hong Kong, China Leizhen Cai, Chinese University, Hong Kong, China Siu-Wing Cheng, HKUST, Hong Kong, China Francis Chin, Hong Kong University, Hong Kong, China Xiaotie Deng, City University, Hong Kong, China Rudolf Fleischer (chair), Fudan University, China Mordecai Golin, HKUST, Hong Kong, China Tak-Wah Lam, Hong Kong University, Hong Kong, China Gerhard Trippen, HKUST, Hong Kong, China Derick Wood, HKUST, Hong Kong, China Frances Yao, City University, Hong Kong, China Joseph Zhen Zhou, HKUST, Hong Kong, China
Sponsors The Croucher Foundation, Hong Kong, China The K.C. Wong Education Foundation, Hong Kong, China
Organization
Referees Pankaj Agarwal Heekap Ahn Amihood Amir Nikhil Bansal Marcin Bienkowski Johannes Blömer Carsten Böke Franz J. Brandenburg Gruia Calinescu H.L. Chan W.T. Chan Bernard Chazelle Bogdan Chelebus Ning Chen Xi Chen Yong Chen Tae-nam Cho Graham Cormode Valentina Damerow Bhaskar DasGupta Benjamin Doerr Andreas Döring Adrian Dumitrescu Peter Eades John Ellis Leah Epstein Thomas Erlebach Hongbin Fan Qizhi Fang Martin Farach-Colton Arash Farzan Fedor Fomin Gereon Frahling P.Y. Fung Luisa Gargano Mohammad GhasemZadeh Clemens Gröpl Qianping Gu Joachim Gudmundsson Arvind Gupta Torben Hagerup Mikael Hammar Herman Haverkort
Chin-Wen Ho W.K. Hon Tsan-Sheng Hsu Ji Hu Sha Huang Wanjun Huang John Iacono Martin Isenburg Michael Jacobson Xiaohua Jia David Johnson Valerie King Ralf Klasing Bettina Klinz Volker Klotz Ming-Tat Ko Jochen Konemann Yehuda Koren Miroslav Korzeniowski Dariusz Kowalski Miroslaw Kowaluk Piotr Krysta Eduardo Laber Gad M. Landau D.T. Lee Jianping Li Shuguang Li Weifa Liang Minming Liless Yuanxin (Leo) Liu Chi-Jen Lu Hsueh-I Lu Anna Lubiw Veli Mäkinen Andrea Mantler Alexander Martin Monaldo Mastrolilli Wendy Myrvold Nikola Nikolov Naomi Nishimura Chong-Dae Park Jung-Heum Park Kunsoo Park
IX
X
Organization
Andrzej Pelc David Peleg Xingqin Qi Prabakhar Ragde Manuel Rode Günter Rote Stefan Rührup Frank Ruskey David Sankoff Christian Scheideler Volker Schillings Allan Scott Jiri Sgall Chan-Su Shin Michiel Smid Christian Sohler Frits Spieksma Venkatesh Srinivasan Xiaoming Sun Ting-Yi Sung Don E. Taylor Gerard Tel Mikkel Thorup H.F. Ting I-Ming Tsai George Tzanetakis Miguel Vargas Martin Suresh Venkatasubramanian
Tomas Vinar Berthold Vöcking Klaus Volbert Lutz Vorwerk Bow-Yaw Wang Da-Wei Wang Lusheng Wang Wei Wang Xiaoli Wang Rolf Wanka Ingo Wegener Alexander Wolff Duncan Wong Prudence Wong David R. Wood Kuen-Pin Wu Kui Wu Qin Xin Yinfeng Xu S.M. Yiu Jinjiang Yuan Michael Zastre Jing Zhang Shaoqiang Zhang Yunlei Zhao Binhai Zhu Uri Zwick
Table of Contents
Puzzles, Art, and Magic with Algorithms Erik D. Demaine
1
The ABCs of AVDs: Geometric Retrieval Made Simple David M. Mount
2
Pareto Optimality in House Allocation Problems David J. Abraham, Katarína Cechlárová, David F. Manlove, Kurt Mehlhorn
3
Property-Preserving Data Reconstruction Nir Ailon, Bernard Chazelle, Seshadhri Comandur, Ding Liu
16
On the Monotone Circuit Complexity of Quadratic Boolean Functions Kazuyuki Amano, Akira Maruoka
28
Generalized Function Matching Amihood Amir, Igor Nor
41
Approximate Distance Oracles for Graphs with Dense Clusters Mattias Andersson, Joachim Gudmundsson, Christos Levcopoulos
53
Multicriteria Global Minimum Cuts Amitai Armon, Uri Zwick
65
Polyline Fitting of Planar Points Under Min-sum Criteria Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama
77
A Generalization of Magic Squares with Applications to Digital Halftoning Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. Nandy, Shinji Sasahara, Takeaki Uno
89
Voronoi Diagrams with a Transportation Network on the Euclidean Plane Sang Won Bae, Kyung- Yong Chwa
101
XII
Table of Contents
Structural Alignment of Two RNA Sequences with Lagrangian Relaxation Markus Bauer, Gunnar W. Klau
113
Poly-APX- and PTAS-Completeness in Standard and Differential Approximation Cristina Bazgan, Bruno Escoffier, Vangelis Th. Paschos
124
Efficient Algorithms for Maximum Sums Fredrik Bengtsson, Jingsen Chen
137
Equipartitions of Measures by 2-Fans Sergey Bereg
149
Augmenting the Edge-Connectivity of a Spider Tree Davide Bilò, Guido Proietti
159
On Nash Equilibria for Multicast Transmissions in Ad-Hoc Wireless Networks Vittorio Bilò, Michele Flammini, Giovanna Melideo, Luca Moscardelli
172
Structural Similarity in Graphs (A Relaxation Approach for Role Assignment) Ulrik Brandes, Jürgen Lerner
184
Flexibility of Steiner Trees in Uniform Orientation Metrics Marcus Brazil, Pawel Winter, Martin Zachariasen
196
Random Access to Advice Strings and Collapsing Results Jin-Yi Cai, Osamu Watanabe
209
Bounding the Payment of Approximate Truthful Mechanisms Gruia Calinescu
221
The Polymatroid Steiner Problems Gruia Calinescu, Alexander Zelikovsky
234
Geometric Optimization Problems Over Sliding Windows Timothy M. Chan, Bashir S. Sadjad
246
On-Line Windows Scheduling of Temporary Items Wun-Tat Chan, Prudence W.H. Wong
259
Table of Contents
XIII
Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy Danny Z. Chen, Xiaobo S. Hu, Shuang Luan, Shahid A. Naqvi, Chao Wang, Cedric X. Yu
271
An Efficient Exact Algorithm for the Minimum Ultrametric Tree Problem Hsin-Fu Chen, Maw-Shang Chang
282
On the Range Maximum-Sum Segment Query Problem Kuan-Yu Chen, Kun-Mao Chao
294
An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs Xujin Chen, Wenan Zang
306
Efficient Job Scheduling Algorithms with Multi-type Contentions Zhenming Chen, Vikas Singh, Jinhui Xu
318
Superimposing Voronoi Complexes for Shape Deformation Chao Chen, Ho-Lun Cheng
330
On Partial Lifting and the Elliptic Curve Discrete Logarithm Problem Qi Cheng, Ming-Deh Huang
342
Guarding Art Galleries by Guarding Witnesses Kyung-Yong Chwa, Byung-Cheol Jo, Christian Knauer, Esther Moet, René van Oostrum, Chan-Su Shin
352
On
Based Locality Measures of Space-Filling Curves H.K. Dai, H.C. Su
364
Composability of Infinite-State Activity Automata Zhe Dang, Oscar H. Ibarra, Jianwen Su
377
Error Compensation in Leaf Root Problems Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier
389
On Compact and Efficient Routing in Certain Graph Classes Feodor F. Dragan, Irina Lomonosov
402
Randomized Insertion and Deletion in Point Quad Trees Amalia Duch
415
Diagnosis in the Presence of Intermittent Faults Bin Fu, Richard Beigel
427
XIV
Table of Contents
Three-Round Adaptive Diagnosis in Binary Satoshi Fujita, Toru Araki
442
Fast Algorithms for Comparison of Similar Unordered Trees Daiji Fukagawa, Tatsuya Akutsu
452
GCD of Random Linear Forms Joachim von zur Gathen, Igor E. Shparlinski
464
On the Hardness and Easiness of Random 4-SAT Formulas Andreas Goerdt, André Lanka
470
Minimum Common String Partition Problem: Hardness and Approximations Avraham Goldstein, Petr Kolman, Jie Zheng
484
On the Complexity of Network Synchronization Darin Goldstein, Kojiro Kobayashi
496
Counting Spanning Trees and Other Structures in Non-constant-jump Circulant Graphs Mordecai J. Golin, Yiu Cho Leung, Yajun Wang
508
Adaptive Spatial Partitioning for Multidimensional Data Streams John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth
522
Paired Pointset Traversal Peter Hui, Marcus Schaefer
534
Approximated Two Choices in Randomized Load Balancing Kazuo Iwama, Akinori Kawachi
545
Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting Joseph JaJa, Christian W. Mortensen, Qingmin Shi
558
Local Gapped Subforest Alignment and Its Application in Finding RNA Structural Motifs Jesper Jansson, Ngo Trung Hieu, Wing-Kin Sung
569
The Maximum Agreement of Two Nested Phylogenetic Networks Jesper Jansson, Wing-Kin Sung
581
Table of Contents
XV
Sequences of Radius How to Fetch Many Huge Objects into Small Memory for Pairwise Computations Jerzy W. Jaromczyk, Zbigniew Lonc
594
New Bounds on Map Labeling with Circular Labels Minghui Jiang, Sergey Bereg, Zhongping Qin, Binhai Zhu
606
Optimal Buffer Management via Resource Augmentation Jae-Hoon Kim
618
Oriented Paths in Mixed Graphs Egon Wanke, Rolf Kötter
629
Polynomial Deterministic Rendezvous in Arbitrary Graphs Dariusz R. Kowalski, Andrzej Pelc
644
Distributions of Points and Large Quadrangles Hanno Lefmann
657
Cutting Out Polygons with Lines and Rays Ovidiu Daescu, Jun Luo
669
Advantages of Backward Searching - Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays Veli Mäkinen, Gonzalo Navarro, Kunihiko Sadakane
681
Inner Rectangular Drawings of Plane Graphs Kazuyuki Miura, Hiroki Haga, Takao Nishizeki
693
Approximating the Minmax Subtree Cover Problem in a Cactus Hiroshi Nagamochi, Taizo Kawada
705
Boundary-Optimal Triangulation Flooding Richard J. Nowakowski, Norbert Zeh
717
Exact Computation of Polynomial Zeros Expressible by Square Roots Timo von Oertzen
729
Many-to-many Disjoint Path Covers in a Graph with Faulty Elements Jung-Heum Park, Hee-Chul Kim, Hyeong-Seok Lim
742
An Algorithm for the Maximum Constrained Agreement Subtree Problem for Binary Trees Zeshan Peng, Hingfung Ting
754
XVI
Table of Contents
Planning the Transportation of Multiple Commodities in Bidirectional Pipeline Networks Artur Alves Pessoa
766
Efficient Algorithms for the Hotlink Assignment Problem: The Worst Case Search Artur Alves Pessoa, Eduardo Sany Laber, Críston de Souza
778
Dynamic Tree Cross Products Marcus Raitner
793
Spanners, Weak Spanners, and Power Spanners for Wireless Networks Christian Schindelhauer, Klaus Volbert, Martin Ziegler
805
Techniques for Indexing and Querying Temporal Observations for a Collection of Objects Qingmin Shi, Joseph JaJa
822
Approximation Algorithms for the Consecutive Ones Submatrix Problem on Sparse Matrices Jinsong Tan, Louxin Zhang
835
The Two-Guard Problem Revisited and Its Generalization Xuehou Tan
847
Canonical Data Structure for Interval Probe Graphs Ryuhei Uehara
859
Efficient Algorithms for the Longest Path Problem Ryuhei Uehara, Yushi Uno
871
Randomized Algorithms for Motif Detection Lusheng Wang, Liang Dong, Hui Fan
884
Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation Dominique de Werra, Marc Demange, Bruno Escoffier, Jerome Monnot, Vangelis Th. Paschos
896
Sweeping Graphs with Large Clique Number Boting Yang, Danny Dyer, Brian Alspach
908
Table of Contents
XVII
A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths Uri Zwick
921
Author Index
933
This page intentionally left blank
Puzzles, Art, and Magic with Algorithms Erik D. Demaine MIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar Street, Cambridge, MA 02139, USA
[email protected]
Solving and designing puzzles, creating sculpture and architecture, and inventing magic tricks all lead to fun and interesting algorithmic problems. This talk describes some of our explorations into these areas. Puzzles. Solving a puzzle is like solving a research problem. Both require the right cleverness to see the problem from the right angle, and then explore that idea until you find a solution. The main difference is that the puzzle poser usually guarantees that the puzzle is solvable. Puzzles also lead to the meta-puzzle of how to design algorithms that can design families of puzzles. Art. Elegant algorithms are beautiful. A special treat is when that beauty translates visually. Sometimes this is by design, when you develop an algorithm to compose artwork within a particular family. Other times the visual beauty of an algorithm just appears, without anticipation. Magic. Mathematics is the basis for many magic tricks, particularly “selfworking” tricks. One of the key people at the intersection of mathematics and magic is Martin Gardner, whose work has inspired several of the results described here. Algorithmically, our goal is to automatically design familes of magic tricks. This is joint work with Martin Demaine and several others.
R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, p. 1, 2004. © Springer- Verlag Berlin Heidelberg 2004
The ABCs of AVDs: Geometric Retrieval Made Simple David M. Mount Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742, USA
[email protected]
One of the best known structures in computational geometry is the Voronoi diagram. Given a set of points in space, called sites, this is a subdivision that partitions space into convex cells according which site is closest. The Voronoi diagram and its dual, the Delaunay triangulation are among the most fundamental proximity structures known, and have numerous uses in science. For example, applying point location to the subdivision defined by a Voronoi diagram answers nearest neighbor queries. Although they are popular in low dimensional spaces, there are various reasons why Voronoi diagrams are rarely used higher dimensions. First, the combinatorial complexity of the diagram grows rapidly, as fast as in space. Second, the diagram does not admit a straightforward search structure in higher dimensions. The AVD, or approximate Voronoi diagram was first proposed by Har-Peled as a simple and easily implemented alternative to the Voronoi diagram for answering approximate nearest neighbor queries. Given a user-supplied approximation bound, this structure is based on a simple hierarchical decomposition of space into rectangular cells, much like a quadtree. Given this structure, nearest neighbor queries can be answered by simply locating the cell that contains the query point, followed perhaps by a small number of distance calculations. If constructed properly, this remarkably simple structure provides the most efficient approach known for answering approximate nearest neighbor queries in spaces of constant dimensionality. Recent research has shown that the AVD can be adapted to answer other geometric retrieval problems. In this talk we will discuss a number of aspects of the AVD and its applications. This includes its origins, improved algorithms and analysis of its construction and space complexity, generalizations to approximate k-nearest neighbor searching, metric range searching, and other generalizations. This is based on joint work with Sunil Arya and Theocharis Malamatos.
R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, p. 2, 2004. © Springer-Verlag Berlin Heidelberg 2004
Pareto Optimality in House Allocation Problems David J. Abraham1,*, Katarína Cechlárová2, David F. Manlove3,**, and Kurt Mehlhorn4 1
Computer Science Department, Carnegie-Mellon University, 5000 Forbes Ave, Pittsburgh PA 15213-3890, USA
[email protected]
2
Institute of Mathematics, P.J. Šafárik University in Košice, Faculty of Science, Jesenná 5, 040 01 Košice, Slovakia
[email protected]
3
Department of Computing Science, University of Glasgow, Glasgow G12 8QQ, UK
[email protected] 4
Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany
[email protected]
Abstract. We study Pareto optimal matchings in the context of house allocation problems. We present an algorithm, based on Gale’s Top Trading Cycles Method, for finding a maximum cardinality Pareto optimal matching, where is the number of agents and is the total length of the preference lists. By contrast, we show that the problem of finding a minimum cardinality Pareto optimal matching is NP-hard, though approximable within a factor of 2. We then show that there exist Pareto optimal matchings of all sizes between a minimum and maximum cardinality Pareto optimal matching. Finally, we introduce the concept of a signature, which allows us to give a characterization, checkable in linear time, of instances that admit a unique Pareto optimal matching.
1
Introduction
We study the problem of allocating a set H of heterogeneous indivisible goods among a set A of agents [14, 8, 3, 4]. We assume that each agent ranks in order of preference a subset of H (the acceptable goods for and that monetary compensations are not possible. In the literature the situation in which each agent initially owns one good is known as a housing market [14, 12, 11]. When there are no initial property rights, we obtain the house allocation problem [8, 16, 1]. A mixed model, in which a subset of agents initially owns a good has also been studied [2]. Yuan [15] describes a large-scale application of these problems in the allocation of families to government-subsidized housing in China. * Work done whilst at Department of Computing Science, University of Glasgow, and Max-Planck-Institut für Informatik. ** Supported by grant GR/R84597/01 from the Engineering and Physical Sciences Research Council and RSE/Scottish Executive Personal Research Fellowship. R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 3–15, 2004. © Springer-Verlag Berlin Heidelberg 2004
4
D.J. Abraham et al.
Following convention we refer to the elements of H as houses, though the class of problems under consideration could equally be formulated in terms of allocating graduates to trainee positions, professors to offices, clients to servers, etc. For ease of exposition we begin by assuming that there are no initial property rights, though we later show how to take account of such a situation. Given such a problem instance, the task is to construct a matching, i.e. a subset M of A × H such that implies that finds acceptable, each agent is assigned to at most one house and vice versa. Furthermore one seeks a matching that is optimal in a precise sense, taking into account the agents’ preferences. Various notions of optimality have been considered in the literature, but a criterion that has received much attention, particularly from economists, is Pareto optimality. A matching M is Pareto optimal if there is no other matching such that no agent is worse off in than in M, whilst some agent is better off in than in M. For example, a matching M is not Pareto optimal if two agents could improve by swapping the houses that they are assigned to in M. There is a straightforward greedy algorithm, which we denote by GreedyPOM, for finding a Pareto optimal matching [1]: consider each agent in turn, giving his/her most-preferred vacant house (assuming such a house exists). This algorithm is also known as a serial dictatorship mechanism [1]. Roth and Sotomayor [13–Example 4.3] remark that a similar mechanism is used by the United States Naval Academy in order to match graduating students to their first posts as Naval Officers (in this context however, the algorithm considers each student in non-decreasing order of graduation results). However one may construct an example instance (see Section 2 for further details) in which Pareto optimal matchings may have different cardinalities and Greedy-POM could fail to produce a Pareto optimal matching of maximum size. Yet in many applications, one wishes to match as many agents as possible. Stronger notions of optimality have been considered in the literature. For example a matching M is rank-maximal [10] if, in M, the maximum number of agents are matched to their first-choice house, and subject to this condition, the maximum number of agents are matched to their second-choice house, and so on. Irving et al. [10] describe two algorithms for finding a rank-maximal matching, with complexities and O(Cnm), where is the total length of the preference lists and C is the maximum such that some agent is assigned to his/her kth-choice house in the constructed matching. Clearly a rank-maximal matching is Pareto optimal, however a rank-maximal matching need not be a maximum cardinality Pareto optimal matching (henceforth a maximum Pareto optimal matching). Alternatively, one may consider a maximum cardinality maximum utility matching M, in which we maximise over all maximum cardinality matchings, where indicates the utility of house being allocated to agent If one defines where is the rank of house in agent preference list and is the maximum length of an agent’s list, then a maximum cardinality maximum utility matching is in turn a maximum Pareto optimal matching. Since all utilities are integral, a maximum cardinality maximum utility matching may be found
Pareto Optimality in House Allocation Problems
5
in time [5]. However if one only requires to find a maximum cardinality matching that satisfies the weaker condition of being Pareto optimal, it is of interest to consider whether faster algorithms exist. The next two sections of this paper work towards answering this question. In Section 2 we give a formal definition of the problem model, and present necessary and sufficient conditions for a matching to be Pareto optimal. In Section 3 we use these conditions as the basis for an algorithm for finding a maximum Pareto optimal matching. This algorithm extends the Top Trading Cycles Method due to Gale [14], which has been the focus of much attention, particularly in the game theory and economics literature [14, 12, 11, 15, 2]. We then show that any improvement to the complexity of our algorithm would imply an improved algorithm for finding a maximum matching in a bipartite graph. We also demonstrate how to modify our algorithm in order to take account of initial property rights, guaranteeing that those who own a good initially will end up with a good that is either the same or better. In the remainder of the paper, we prove several related results. In Section 4 we consider the problem of finding a minimum Pareto optimal matching, showing that this problem is NP-hard, though approximable within a factor of 2. In Section 5 we prove an interpolation result, showing that there exist Pareto optimal matchings of all sizes between a minimum and maximum Pareto optimal matching. Finally, in Section 6 we give a characterization, checkable in linear time, of instances that admit a unique Pareto optimal matching.
2
Preliminaries
We begin with a formal definition of the problem model under consideration. An instance I of the PARETO OPTIMAL MATCHING problem (POM) comprises a bipartite graph G = ( A , H , E ) , where is the set of agents and is the set of houses. For each we denote by the vertices adjacent to these are referred to as the acceptable houses for Moreover has a linear order over We let and Henceforth we assume that G contains no isolated vertices. An assignment M is a subset of A × H such that only if finds acceptable (i.e. If we say that and are assigned to one another. For each let denote the assignees of in M. A matching is an assignment M such that 1 for each If we say that is unmatched in M, otherwise is matched in M. Let M be a matching in I. M is maximal if there is no (agent,house) pair such that and are both unmatched in M and Also M is trade-in-free if there is no (agent,house) pair such that is matched in M, is unmatched in M, and prefers to Finally M is coalitionfree if M admits no coalition, which is a sequence of matched agents for some such that prefers to (here, and in the remainder of this paper, all subscripts are taken modulo when reasoning about coalitions). The matching
6
D.J. Abraham et al.
is defined to be the matching obtained from M by satisfying C. The preferences of an agent extend to matchings as follows. Given two matchings M and we say that an agent prefers to M if either (i) is matched in and unmatched in M, or (ii) is matched in both M and and prefers to Given this definition, we may define a relation on the set of all matchings as follows: if and only if no agent prefers M to and some agent prefers to M. It is straightforward to then prove the following. Proposition 1. Given an instance I of POM, the relation partial order over the set of matchings in I.
forms a strict
A matching is defined to be Pareto optimal if and only if it is Intuitively a matching is Pareto optimal if no agent can be better off without requiring another agent to be worse off. The following proposition gives necessary and sufficient conditions for a matching to be Pareto optimal. Proposition 2. Let M be a matching in a given instance of POM. Then M is Pareto optimal if and only if M is maximal, trade-in-free and coalition-free. Proof. Let M be a Pareto optimal matching. If M is not maximal, then there exists an agent and a house both unmatched in M, such that Let If M is not trade-in-free, then there exist an agent and a house such that is matched in M, is unmatched in M, and prefers to Let Finally if M admits some coalition C, let be the matching obtained by satisfying C. In all three cases, a contradiction. Conversely let M be a matching that is maximal, trade-in-free and coalitionfree, and suppose for a contradiction that M is not Pareto optimal. Then there exists some matching such that Let be any agent matched in M who prefers to M. Note that such an agent must exist, since M is maximal and at least one agent prefers to M. It follows that is matched in M, say to for otherwise M is not trade-in-free. Therefore, and so must also prefer to M. Using this same argument, is matched in M, say to We can continue in this manner finding a sequence of agents where prefers to Since the number of agents is finite, this sequence must cycle, thereby contradicting the assumption that M is coalition-free. Henceforth we will establish the Pareto optimality of a given matching by showing that the conditions of the above proposition are satisfied. For a given matching M, we can trivially check whether M satisfies the maximality and trade-in-free properties in time. To check for the absence of coalitions, we construct the envy graph of M. This is a directed graph, denoted by G(M), consisting of one vertex for each agent, with an edge from to whenever is
Pareto Optimality in House Allocation Problems
7
matched in M and either (i) is unmatched in M and finds acceptable, or (ii) is matched in M and prefers to It is clear that M is coalition-free if and only if G(M) is acyclic. So we can perform this last check in time by using a cycle-detection algorithm on G(M). Putting these observations together, we have the following result. Proposition 3. Let M be a matching in a given instance of POM. Then we may check whether M is Pareto optimal in time. It is easy to construct an instance of POM in which the Pareto optimal matchings are of different sizes. For example let and let Suppose that prefers to whilst finds only acceptable. Then both and are Pareto optimal. Given this observation it is natural to consider the complexity of each of the problems of finding a maximum and minimum Pareto optimal matching. (Note that Greedy-POM produces given the agent ordering and produces given the agent ordering
3
Maximum Pareto Optimal Matchings
In this section, we describe a three-phase algorithm for finding a maximum Pareto optimal matching, mirroring the three necessary and sufficient conditions in Proposition 2. We let I be an instance of POM, and we assume the notation and terminology introduced in Section 2. Phase 1 involves using the HopcroftKarp algorithm [7] to compute a maximum matching M in G. This phase, which guarantees that M is maximal, takes time and dominates the runtime. The final two phases transform M into a trade-in-free and coalition-free matching respectively. We describe these phases in more detail below.
3.1
Phase 2 of the Algorithm
In this phase, we transform M into a trade-in-free matching by repeatedly identifying and promoting agents that prefer an unmatched house to their existing assignment. Each promotion breaks the existing assignment, thereby freeing a house, which itself may be a preferred assignment for a different agent. With the aid of suitable data structures, we can ensure that the next agent and house can be identified efficiently. For each house we maintain a linked list of pairs where is a matched agent who finds acceptable, and is the rank of in preference list. Initially the pairs in involve only those matched agents who prefer to though subsequently the pairs in may contain agents who prefer to The initialization of these lists can be carried out using one traversal of the agent preference lists, which we assume are represented as doubly linked lists or arrays, in time. For each matched agent we also use this traversal to initialize a variable, denoted by which stores the rank of in preference list. This
8
D.J. Abraham et al.
variable is maintained during the execution of the algorithm. We also assume that, for each matched agent we store One final initialization remains: construct a stack S of all unmatched houses where is non-empty. We now enter the loop described in Figure 1.
Fig. 1. Phase 2 loop
During each loop iteration we pop an unmatched house from S and remove the first pair from the list (which must be non-empty). If prefers to (i.e. then is promoted from to also M and are updated, and finally which is now unmatched, is pushed onto S if is non-empty. Otherwise is pushed back onto S if is non-empty. Each iteration of the loop removes a pair from a list Since agent preference lists are finite and no new pair is added to a list during a loop iteration, the while loop must eventually terminate with S empty. At this point no matched agent would trade for an unmatched house, and so M is trade-in-free. Additionally, M remains a maximum matching, since any agent matched at the end of Phase 1 is also matched at the end of Phase 2. Finally, it is clear that this phase runs in time given the data structures described above.
3.2
Phase 3 of the Algorithm
In this phase, we transform M into a coalition-free matching. Recall that coalitions in M correspond to cycles in the envy graph G(M). So a natural algorithm involves repeatedly finding and satisfying coalitions in G(M) until no more coalitions remain. This algorithm has a runtime of since there are coalitions, and cycle-detection takes time. A better starting point for an efficient algorithm is Gale’s Top Trading Cycles Method [14]. This method is also based on repeatedly finding and satisfying coalitions, however the number of iterations is reduced by the following observation: no agent assigned to his/her first choice can be in a coalition. We remove such agents from consideration, and since the houses assigned to them are no longer exchangeable, they can be deleted from the preference lists of the remaining agents. This observation can now be recursively applied to the reduced
Pareto Optimality in House Allocation Problems
9
Fig. 2. Phase 3 loop
preference lists. At some point, either no agents remain, in which case the matching is coalition-free, or no agent is assigned to his/her reduced first choice (i.e. the first choice on his/her reduced preference list). In this last case, it turns out that there must be a coalition C in M, which can be found in time by searching the envy graph restricted to reduced first-choice edges. After satisfying C, each agent in C is assigned to his/her reduced first choice. Therefore, no agent is in more than one coalition, giving coalitions overall. The runtime of this preliminary implementation then is We now present a linear-time extension of Yuan’s description of the Top Trading Cycles Method [15]. In our implementation, deletions of houses from agents’ preference lists are not explicitly carried out. Instead, a house that is no longer exchangeable is labelled (all houses are initially unlabelled). For each agent we maintain a pointer to the first unlabelled house on preference list – this is equivalent to the first house on reduced preference list. Initially points to the first house on preference list, and subsequently traverses left to right. Also, in order to identify coalitions, we initialize a counter to 0 for each agent Then, we enter the main body of the algorithm, as given in Figure 2. This algorithm repeatedly searches for coalitions, building a path P of agents (represented by a stack) in the (simulated) envy graph restricted to reduced firstchoice edges. At each iteration of the while loop, we pop an agent from the stack and move up if necessary. If P cycles (i.e. we find that there is a coalition C – the agents involved in C are removed from consideration
10
D.J. Abraham et al.
and the houses assigned to these agents are labelled (in practice the agents in C can be identified and C can be satisfied during the stack popping operations). Alternatively, if P reaches a dead-end is already assigned to his/her first choice), this agent is removed from consideration and his/her assigned house is labelled. Otherwise, we keep extending the path by following the reduced firstchoice edges. At the termination of this phase we note that M is coalition-free by the correctness of the Top Trading Cycles Method [14]. Also M remains a maximum trade-in-free matching, since each agent and house matched at the end of Phase 2 is also matched at the end of Phase 3. Finally, it is clear this phase runs in time given the data structures described above. We summarize the preceding discussion in the following theorem. Theorem 1. A maximum Pareto optimal matching can be found in time. Such a matching is also a maximum matching of agents to houses. We now show that any improvement to the complexity of the above algorithm would imply an improved algorithm for finding a maximum matching in a bipartite graph. Without loss of generality, let G = (A, H, E) be an arbitrary bipartite graph with no isolated vertices. Construct an instance I of POM with bipartite graph G, where each agent preference list in I is an arbitrary permutation over neighbours in G. By Theorem 1, any maximum Pareto optimal matching in I is also a maximum matching in G. Since I may be constructed from G in time, the complexity of finding a maximum matching in a bipartite graph is bounded above by the complexity of finding a maximum Pareto optimal matching.
3.3
Initial Property Rights
Suppose that a subset of the agents already own a house. We now describe an individually rational modification of our algorithm, which ensures that every agent in ends up with the same house or better. We begin with a matching M that pre-assigns every agent to his/her existing house We then truncate the preference list of each such by removing all houses less preferable than Now, we enter Phase 1, where we use the Hopcroft-Karp algorithm to exhaustively augment M into some matching Members of must still be matched in and since their preference lists were truncated, their new assignments must be at least as preferable as those in M. Note that may not be a maximum matching of A to H, however does have maximum cardinality among all matchings that respect the initial property rights. The remaining two phases do not move any agent from being matched to unmatched, and so the result follows immediately. In the special case that all agents own a house initially (i.e. I is an instance of a housing market), it is clear that Phases 1 and 2 of the algorithm are not required. Moreover it is known that Phase 3 produces the unique matching that belongs to the core of the market [12], a stronger notion than Pareto optimality.
Pareto Optimality in House Allocation Problems
4
11
Minimum Pareto Optimal Matchings
In this section, we consider the problem of finding a minimum Pareto optimal matching. Let MIN-POM denote the problem deciding, given an instance I of POM and an integer K, whether I admits a Pareto optimal matching of size at most K. We firstly prove that MIN-POM is NP-complete via a reduction from MMM, which is the problem of deciding, given a graph G and an integer K, whether G admits a maximal matching of size at most K. Theorem 2. MIN-POM is NP-complete. Proof. By Proposition 3, MIN-POM belongs to NP. To show NP-hardness, we give a reduction from the NP-complete restriction of MMM to subdivision graphs [6] (given a graph G, the subdivision graph of G is obtained by subdividing each edge into two edges where is a new vertex corresponding to Let G = (V, E) (a subdivision graph) and K (a positive integer) be given as an instance of MMM. Then V is a disjoint union of two sets U and W, where each edge joins a vertex in U to a vertex in W. Assume that and Without loss of generality assume that each vertex has degree 2, and moreover assume that and are two sequences such that and We create an instance I of MIN-POM as follows. Let A be the set of agents and let H be the set of houses, where and For each we create preference lists for agents and as follows:
We claim that G has a maximal matching of size at most K if and only if I has a Pareto optimal matching of size at most For, suppose that M is a maximal matching in G of size at most K. We construct a set as follows. For any that is unmatched in M, add the pair to Now suppose that If add the pairs and to If add the pairs and to Clearly is a matching in I, and It is straightforward to verify that, by the maximality of M in G, is Pareto optimal in I. Conversely suppose that is a Pareto optimal matching in I of size at most For each either or for otherwise is not trade-in-free. Hence we may construct a matching M in G as follows. For each if for some add to M. Then The maximality of clearly implies that M is maximal in G. For a given instance I of POM with bipartite graph G, we denote by and the sizes of a minimum and maximum Pareto optimal matching in I respectively. Similarly, we denote by and the sizes of a minimum maximal and a maximum matching in G respectively. It is known that
12
D.J. Abraham et al.
[9]. By Proposition 2, Pareto optimal matchings in I are maximal matchings in G. Hence, by Theorem 1, we have that It is therefore immediate that, for a given instance I of POM, the problem of finding a minimum Pareto optimal matching is approximable within a factor of 2.
5
Interpolation of Pareto Optimal Matchings
In this section, we prove that, for a given instance I of POM, there are Pareto optimal matchings of all sizes between and Given a matching M, an augmenting path P for M is an alternating sequence of distinct agents and houses where and are unmatched in M, and We associate with each such augmenting path a vector whose ith component contains the rank of for Given two augmenting paths P and Q for M, we say that if (i) both P and Q begin from the same agent, and (ii) is lexicographically less than Also for paths P and Q, we define three operations: is the substring of P from to is the substring of P from to and P · Q denotes the concatenation of P and Q. Theorem 3. For a given instance I of POM, there exist Pareto optimal matchings of size for each such that Proof. Let M be any Pareto optimal matching such that and let be the matching that results from augmenting M along some augmenting path P. We will show in turn that is maximal, trade-in-free and coalition-free; the result then follows by induction. If is not maximal, then clearly we contradict the maximality of M. Now suppose that is not trade-in-free. Then there exists an agent and house where is matched in is unmatched in and prefers to Since is also unmatched in M, must be in P, for otherwise and M is not trade-in-free. But then is an augmenting path for M, contradicting the of P. Finally suppose for a contradiction that is not coalition-free. Then there exists a coalition with respect to At least one agent in P must also be in C, for otherwise M is not coalition-free. Let be the first such agent in P. We establish some properties of Firstly, must be matched in M, for otherwise M admits the augmenting path contradicting the of P. Also, cannot appear before in P, for otherwise is not the first agent in P to be in C. Lastly, cannot appear after in P, for otherwise M admits the augmenting path contradicting the of P. So, it must be the case that is matched in M and does not appear in P. Let be the first agent in C after such that is in P. Note that by the above properties of but since C is a cycle, is possible.
Pareto Optimality in House Allocation Problems
It follows that the subsequence C is disjoint from P, and so augmenting path of M. But then prefers to
contradicts the
13
of is a valid of P, since
Corollary 1. Given an instance I of POM and a Pareto optimal matching M in I of size we can construct a Pareto optimal matching of size or determine that no such matching exists, in time. Proof. Let G be the bipartite graph in I, with edges in M directed from H to A, and edges not in M directed from A to H. Also associate with each non-matching edge the rank of for We search for a augmenting path by performing an ordered depth first search of G starting from the set of unmatched agents, where for each agent in the search, we explore outgoing edges from in increasing order of rank. In general, ordered depth-first search is asymptotically slower than depth-first search. However, the result holds, since each preference list is already given in increasing order of rank. We remark that the results of this section extend to the case where a subset of the agents have initial property rights.
6
Uniqueness of Pareto Optimal Matchings
In this section, we give a characterization of instances with no initial property rights that admit a unique Pareto optimal matching. This is based on the concept of a signature of a Pareto optimal matching. If a matching M is Pareto optimal, the envy graph G(M) contains no cycles, and therefore admits a topological ordering. We say that a reversed topological ordering of G(M), denoted by is a signature of M. The next lemma will help us establish that the signature of a matching is unique for that matching. This lemma is similar to [1–Lemma 1], though the proof here, which uses the concept of a signature, is much simpler. Lemma 1. Given an instance I of POM, the algorithm Greedy-POM can generate any Pareto optimal matching in I. Proof. Let M be an arbitrary Pareto optimal matching in I. We claim that by processing the agents in order of the greedy algorithm returns M. Suppose for a contradiction that Greedy-POM returns a matching It follows that since is Pareto optimal, some agent must prefer to M. Let be the first such agent in Now, must be matched in M, say to for otherwise M is not maximal (if is unmatched in M), or M is not trade-in-free (if is matched in M). G(M) must therefore contain an edge from to meaning that precedes in At the time is processed by Greedy-POM, is unmatched (since it is assigned later to So, must prefer to contradicting the assumption that was the first such agent in
14
D.J. Abraham et al.
Corollary 2. Given an instance I of POM, every agent permutation is a signature of exactly one Pareto optimal matching in I. We can now present a necessary and sufficient condition, checkable in linear time, for a POM instance to admit a unique Pareto optimal matching. Theorem 4. An instance I of POM admits a unique Pareto optimal matching M if and only if every agent is matched in M with his/her first choice. Proof. Let M be the unique Pareto optimal matching in I. Since every agent permutation is a signature of M, G(M) contains no edges. Then every agent must be matched to his/her first choice. Conversely, let M be a matching in I in which every agent is matched with his/her first choice. Then if is any matching in I such that it follows that Hence M is the unique Pareto optimal matching in I.
7
Concluding Remarks
We conclude with an open problem. The basic POM definition given in Section 2 can be generalized by permitting agents to contain ties in their preference lists (i.e. to rank equally two or more houses). In this context the definition of the relation is the same as that given in Section 2, and hence the definition of Pareto optimality remains unchanged. A maximum Pareto optimal matching can be found in time using a similar reduction to the Assignment problem as described in Section 1 (in this case is the number of houses that prefers to However is the problem of finding a maximum Pareto optimal matching solvable in time?
References 1.
2. 3. 4. 5. 6. 7.
and T. Sönmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3):689–701, 1998. and T. Sönmez. House allocation with existing tenants. Journal of Economic Theory, 88:233–260, 1999. X. Deng, C. Papadimitriou, and S. Safra. On the complexity of equilibria. Journal of Computer and System Sciences, 67(2):311–324, 2003. S.P. Fekete, M. Skutella, and G.J. Woeginger. The complexity of economic equilibria for house allocation markets. Inf. Proc. Lett., 88:219–223, 2003. H.N. Gabow and R.E. Tarjan. Faster scaling algorithms for network problems. SIAM Journal on Computing, 18(5):1013–1036, 1989. J.D. Horton and K. Kilakos. Minimum edge dominating sets. SIAM Journal on Discrete Mathematics, 6:375–387, 1993. J.E. Hopcroft and R.M. Karp. A Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing, 2:225–231, 1973.
Pareto Optimality in House Allocation Problems
15
8. A. Hylland and R. Zeckhauser. The efficient allocation of individuals to positions. Journal of Political Economy, 87(2):293–314, 1979. 9. B. Korte and D. Hausmann. An analysis of the greedy heuristic for independence systems. Annals of Discrete Mathematics, 2:65–74, 1978. 10. R.W. Irving, T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch. Rank-maximal matchings. Proceedings of SODA ’04, pages 68–75. ACM-SIAM, 2004. 11. A.E. Roth. Incentive compatibility in a market with indivisible goods. Economics Letters, 9:127–132, 1982. 12. A.E. Roth and A. Postlewaite. Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4:131–137, 1977. 13. A.E. Roth and M.A.O. Sotomayor. Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press, 1990. 14. L. Shapley and H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1:23–37, 1974. 15. Y. Yuan. Residence exchange wanted: a stable residence exchange problem. European Journal of Operational Research, 90:536–546, 1996. 16. L. Zhou. On a conjecture by Gale about one-sided matching problems. Journal of Economic Theory, 52(1):123–135, 1990.
Property-Preserving Data Reconstruction* Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu Dept. Comp. Sci., Princeton University, Princeton NJ 08544, USA {nailon, chazelle, csesha, dingliu}@cs.princeton.edu
Abstract. We initiate a new line of investigation into online property preserving data reconstruction. Consider a dataset which is assumed to satisfy various (known) structural properties; eg, it may consist of sorted numbers, or points on a manifold, or vectors in a polyhedral cone, or codewords from an error-correcting code. Because of noise and errors, however, an (unknown) fraction of the data is deemed unsound, ie, in violation with the expected structural properties. Can one still query into the dataset in an online fashion and be provided data that is always sound? In other words, can one design a filter which, when given a query to any item I in the dataset, returns a sound item J that, although not necessarily in the dataset, differs from I as infrequently as possible. No preprocessing should be allowed and queries should be answered online. We consider the case of a monotone function. Specifically, the dataset encodes a function that is at (unknown) distance from monotone, meaning that can—and must—be modified at places to become monotone. Our main result is a randomized filter that can answer any query in time while modifying the function at only places. The amortized time over function evaluations is The filter works as stated with probability arbitrarily close to 1. We also provide an alternative filter with worst case query time and function modifications.
1
Introduction
It is a fact of (computing) life that massive datasets often come laden with varying degrees of reliability. Errors might be inherent to the data acquisition itself (faulty sensors, white/bursty noise, aliasing), or to data processing (roundoff errors, numerical instability, coding bugs), or even to intrinsic uncertainty (think of surveys and poll data). Classical error correction postulates the existence of exact data and uses redundancy to provide recovery mechanisms in the presence of errors. Mesh generation in computer graphics, on the other hand, will often deal with reconstruction mostly on the basis of esthetic criteria, while signal processing might filter out noise by relying on frequency domain models. * This work was supported in part by NSF grants CCR-998817, 0306283, ARO Grant DAAH04-96-1-0181. R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 16–27, 2004. © Springer-Verlag Berlin Heidelberg 2004
Property-Preserving Data Reconstruction
17
In the case of geometric datasets, reconstruction must sometimes seek to enforce structural properties. Early work on geometric robustness [5,9] pointed out the importance of topological consistency. For example, one might want to ensure that the output of an imprecise, error-prone computation of a Voronoi diagram is still a Voronoi diagram (albeit that of a slightly perturbed set of points). Geometric algorithm design is notoriously sensitive to structure: Dimensionality, convexity, and monotonicity are features that often impact the design and complexity of geometric algorithms. Consider a computation that requires that the input be a set of points in convex position. If the input is noisy, convexity might be violated and the algorithm might crash. Is there a filter that can be inserted between the algorithm (the client) and the dataset so that: (i) the client is always provided with a point set in convex position; and (ii) the “filtered” data differs as little as possible from the original (noisy) data? In an offline setting, the filter can always go over the entire dataset, compute the “nearest” convex-position point set, and store it as its filtered dataset. This is unrealistic in the presence of massive input size, however, and only online solutions requiring no preprocessing at all can be considered viable. We call this online property-preserving data reconstruction. Besides convexity, other properties we might wish to preserve include low dimensionality and angular constraints: Consider a dataset consisting of points on a low-dim manifold embedded in very high dimensional space. Obviously, the slighest noise is enough to make the point set full-dimensional. How to “pull back” points to the (unknown) manifold online can be highly nonobvious. Angle constraints are of paramount importance in industrial/architectural design. Opposite walls of a building have a habit of being parallel, and no amount of noise and error should violate that property. Again, the design of a suitable filter to enforce such angular constraints online is an interesting open problem. In this paper we consider one of the simplest possible instances of online property-preserving reconstruction: monotone functions. Sorted lists of numbers are a requirement for all sorts of operations. A binary search, for example, will easily err if the list is not perfectly sorted. In this case of property-preserving data reconstruction, the filter must be able to return a value that is consistent with a sorted list and differs from the original as little as possible. (An immediate application of such a filter is to provide robustness for binary searching in nearsorted lists.) We formalize the problem. Let be a function at an unknown distance from monotonicity, which means that can (and must) be modified at places to become monotone. Figure 1 illustrates the filter in action. To avoid confusion, we use the term “query” to denote interaction between the client and the filter, and “lookup” to denote interaction between the filter and the dataset. Given a query the filter generates lookups to the dataset, from which it receives the values and then computes a value such that the function is monotone and differs from in at most places, for some (typically constant, but not necessarily so). We note two things.
18
N. Ailon et al.
1. Once the filter returns for some query it commits to this value and must return the same value upon future queries. 2. The filter may choose to follow a multi-round protocol and adaptively generate lookups to the dataset depending on previous results. The function is defined on the fly, and it can depend on both the queries and on random bits. Therefore, after the first few queries, might only be defined on a small fraction of the domain. At any point in time, if distinct have been queried so far, then querying the remaining (whether the client does it or not) while honoring past commitments leads to a monotone function close enough to It is natural to measure the performance of the filter with respect to two functions. A performs lookups per query, and returns a function that is at a distance of at most from monotonicity, with high probability. The lookup-per-query guarantee can be either amortized or in worst case (the running times are deterministic). Ideally, we would like to depend only on and to be constant. There is a natural tradeoff between and we expect to decrease as increases. We will see an example of this in this work.
Theorem 1. There exists a randomized for any fixed with a worst case lookups-per-query guarantee. The amortized lookups-perquery over function evaluations is The filter behaves as stated with probability arbitrarily close to 1. We also provide an alternative filter with a better lookups-per-query guarantee and a worse distance guarantee. Theorem 2. There exists a per-query guarantee.
with a worst case lookups-
It is important to note that, in this work, we think of the client as adversarial. That is, the filter’s guarantees must hold for all sequences of client queries. However, in some cases it might be useful to assume the client’s queries are drawn from some known probability distribution. We will see that the filter can take advantage of this. Theorem 3. Assuming the client draws the queries independently, uniformly at random, a can be devised. We are not aware of any previous work on this specific problem. Of course, property testing is by now a well studied area [4,8], with many nontrivial results regarding combinatorial, algebraic, and geometric problems [2,3,7]. More recent work [1,6] has provided sublinear algorithms for estimating the distance of a function to monotone. We use ideas from [1] in this work.
2
The
We use the following notation in what follows. The distance between two functions and over the domain is defined as the fractional size of
Property-Preserving Data Reconstruction
19
domain points on which they disagree. The function and the domain size which are the input to the problem (the dataset in Figure 1) are fixed. We use to denote the distance of from monotonicity, and to denote the monotone function closest to So the distance between and is and minimizes the distance between and any monotone function. We use to denote the function outputted by the filter.
Fig. 1. The property-preserving reconstruction filter: few places
2.1
is sound and differs from
in
Preliminaries
Proving Theorem 1 requires a few preliminaries, beginning with these definitions: and exists
Given such that
or, similarly,
the integer
is called
if there
such that
Otherwise the integer is called and Let be the joint distribution of independent 0/1 random variables which can be sampled independently. If for all then is called else it is Lemma 1. (Ailon et al. [1]) Given any fixed if is either then with probability 2/3 we can tell which is the case in is neither, the algorithm returns an arbitrary answer.
or time. If
In the following we use the algorithm of Lemma 1 to test, with high probability of success, whether a given integer is or for any fixed Given an interval we define two 0/1 random variables and given a random integer iff The algorithm bad-good-test (Fig. 2) tests if a given integer is or Lemma 2. Given any fixed and a parameter if is either then bad-good-test will tell which is the case in time and with probability at least
or
20
N. Ailon et al.
Proof. If integer is then the expectation of every or defined in bad-good-test is at most and so the distribution is On the other hand, if is then there exists some or with expectation at least and so is The algorithm from Lemma 1 distinguishes between and with probability 2/3 in time. Since we repeat it times and take a majority vote, a standard Chernoff bound argument shows that bad-good-test fails with probability at most
Fig. 2. Testing if an integer is
Lemma 3. There are at most Moreover, the monotone function agree with on integers.
or
integers (Ailon et al. [1]). which is closest to can be assumed to
Finally, we let denote an arbitrarily small positive real. Choosing a small enough will satisfy the distance guarantee of Theorem 1. 2.2
The Algorithm
We now describe the algorithm monotonize. Our goal, as described above, is: given a fixed compute a function online such that: (1) is monotone; (2) is to Specifically, on query monotonize computes in time Whenever monotonize outputs a value this value must be recorded to ensure consistency. The procedure will therefore hold an internal data structure that will record past commitments. The data structure can be designed to allow efficient retrievals, but we omit the details because we are mainly interested in the number of it performs, and not the cost of other operations. Given a query monotonize first checks whether was committed to in the past, and returns that commitment in that case. If not, more work should be done. In virtue of Lemma 3, monotonize tries to keep the values at
Property-Preserving Data Reconstruction
21
integers and change the values for other queries. We will use bad-good-test to decide whether is bad or good. Suppose now we decide that is and hence needs a value that might be different from Ideally, we would like to find the closest integers (to the left of and (to the right of and assign to some value between and Because of the sublinear time constraint, we slightly relax this condition. Instead, the idea is to find an interval around such that the fraction of integers in is at least but their fraction in a slightly smaller interval is This ensures that such an interval can be detected through random sampling and that there are not many integers between and any integer in this interval (a relaxation of the closest condition). We will search for a good interval within the interval determined by the closest committed values on the left and right of Denote this interval by Once such a good interval is found, we try to find a value that is sandwiched between values of evaluated at two points in Finding is done in find-good-value (Figure 3). We commit to the value on restricted to If no good intervals are found, we spread the value of on in the interval
Fig. 3. Finding a good value in an interval
Lemma 4. The procedure find-good-value returns, with probability a value that is sandwiched between and where are This requires the existence of at least a fraction of integers in I. The running time of find-good-value is for fixed Proof. The expected number X of samples for which bad-good-test returns is at most by Lemma 2. The expected total number Y of samples for which bad-good-test returns is at least The probability that X exceeds Y/2 is at most if is chosen large enough, using Chernoff bounds. Therefore, with probability at least more than half the values that are appended to the list L are the function evaluated at points (“good values”). By taking the median of
22
N. Ailon et al.
values in L, in such a case, we are guaranteed to get a value sandwiched between two good values. The time bound follows from Lemma 2.
Fig. 4. Computing a monotone function online
To find a good interval, we do a binary search among all the intervals of length starting or ending at that is, and There are such intervals, and thus the running time is times the time spent for each interval. The overall algorithm monotonize is shown in Figure 4. The following claim together with a suitable rescaling of concludes the proof of the first part of Theorem 1. Claim. Given any with probability monotonize computes a monotone function that is within distance to Given a query is computed online in time when is assumed to be fixed. Proof. First we analyze the running time. The bad-good-test in line 3 takes time. If the algorithm determines that is then the whileloops run times. In one iteration of the while-loop, the algorithm
Property-Preserving Data Reconstruction
23
calls bad-good-test times. Each call takes time by Lemma 2. Therefore, the time complexity of the while-loop is By Lemma 4, the running time of the call to find-good-integer is The time complexity of the algorithm is therefore Let us first look at the while-loop. If I has more than of integers, then the number of outputs is with inverse polynomial probability. This can be shown through Chernoff bounds. On the other hand, if I has less than of integers, then the number of outputs is with inverse polynomial probability. Therefore, we can assume that When find-good-value is called on interval has at least a of integers. The interval has at most of integers. Both these events hold with probability for some large constant These events occur totally at most a polynomial number of times. We can also assume that, during the execution of the algorithm, the first call of bad-good-test (in line 3) correctly distinguishes between and As shown in Lemma 2, this holds with probability This is totally called at most times. By a union-bound, all of the above events occur with probability for some positive constant To show that the function is monotone, we first note that if bad-good-test outputs for (leading to being set to then is not If is bad, then lies between the value at two points in If is assigned to all the values of in then would be monotone with respect to all the values at the points already committed to. Similarly, can be assigned to the values of in without disturbing monotonicity. Therefore, since the algorithm assigns some value between and to is remains monotone. Finally we show that is within distance to We earlier showed that for the fraction of integers in is at most Since by the end of the algorithm the fraction of integers in (or is at most In other words, each time we make a total of corrections to at least a of these changes are made on integers. By Lemma 2.4 in [1], the total number of integers is at most So the total number of changes we made on is at most for some constant This concludes the proof.
2.3
Achieving Logarithmic Amortized Query Time
In this section we show how to modify the algorithm to achieve better amortized query time. The worst case query time for a single query remains the same. We need a technical lemma first. Lemma 5. For any integers such that interval
let be a integer. Let be two Then there is a witness to badness in the
24
N. Ailon et al.
Proof. If then we claim that is a witness to badness. In fact, since and is a violating pair, it is immediate that at least one of them is 0-bad with respect to the interval Since is must be 0-bad (and hence bad) with respect to In this case, is a witness to badness. Similarly, will be a witness if In the following we assume that Let be a witness to badness. Without loss of generality, assume that If then we are done, so let Since is and is we know that: number of violations in with respect to is number of violations in with respect to is We also know that each violation in with respect to is also a violation with respect to so the number of violations with respect to in is This shows that has a witness to its badness in The improvement on amortized query time comes from the following strategy: each time the algorithm answers a client query, it also generates a new query by itself and answers that query. This self query is completely independent of all the client queries, and we call it an oblivious query. The oblivious queries are generated based on the balanced binary tree on The root of this tree is The left subtree of the root corresponds to the interval and similarly the right subtree corresponds to The two subtrees are then defined recursively. This tree is denoted by T. The oblivious queries are generated according to the following order. We start from the root of T and scan its elements one by one by going down level by level. Within each level we scan from left to right. This defines an ordering of all integers in which is the order to make oblivious queries. This ordering ensures that, after the oblivious query, is divided by all the oblivious queries into a set of disjoint intervals of length at most Each oblivious query is either a integer itself in which case monotonize returns at line 6, or it causes two integers being outputted and in monotonize). These two integers lie on the left and right side of the oblivious query, respectively. This shows that after the oblivious query, is divided by some integers into a set of smaller intervals each of length at most Based on Lemma 5, whenever we call bad-good-test (in find-good-integer or monotonize) to test the badness of an integer we only need to search for a witness within a smaller interval such that (resp. is the closest integer on the left (resp. right) of As explained above, these integers come as by-products of oblivious queries. This will reduce the running time of bad-good-test to (to achieve success probability at least where Accordingly, the time spent on binary searching intervals in monotonize is reduced to By the distribution of oblivious queries, for the client query where the running time of monotonize is now The same is true for the oblivious query. To bound the amortized running time, it suffices to focus on the smallest such that all distinct queries appear in the first queries (including both client and oblivious queries). We can also ignore repetition queries (those that
Property-Preserving Data Reconstruction
25
have appeared before) since each one only takes time using standard data structure techniques. Therefore, without loss of generality, we assume that the first client queries are distinct. The total query time for these queries is:
It is simple to verify that this sum is the proof of the second part of Theorem 1. Claim. With probability that is within distance computed online in time the first client queries is
3
The following claim concludes
monotonize computes a monotone function to Each single evaluation of is and the amortized query time over
The
We prove Theorem 2. To do this, we define a function by a random process. The function is determined after some coin flipping done by the algorithm (before handling the client queries). Although the function is defined after the coin flips, the algorithm doesn’t explicitly know it. In order to explicitly calculate at a point, the algorithm will have to do some Our construction and analysis will upper bound and the amount of work required for explicitly calculating at a point. As before, let be a monotone function such that Let be the set of points So For simplicity of notation, assume the formal values of of any function on evaluated at 0 (resp. We build a randomized binary tree with nodes labeled where is defined as follows:
After constructing the randomized tree T, the function at point is defined as follows. If is the root of the tree, then Otherwise, Let
26
N. Ailon et al.
denote the labels of the nodes on the path from the root to node where is the root of the tree and is the parent of Assume that was already defined on Let and If then define otherwise define as an arbitrary value in The function is clearly monotone. The number of required for computing is the length of the path from the root to We omit the proof of the following fact. Lemma 6. The expected length of this path for any
is at most
We show that
We first observe that for any if then it is guaranteed that Therefore, any for which can be charged to some on the path from the root to The amount of charge on any is at most the size of the subtree in T. We omit the proof of the following lemma. Lemma 7. The expected size of the subtree rooted at node any
in T is
for
Therefore, the expected total amount of charge is at most By Chebyshev’s inequality, the total amount of charge is at most with high probability. The total amount of charge is an upper bound on the distance between and This proves Theorem 2, except for the fact that the lookups-per-query guarantee is only on expectation, and not worse case (due to Lemma 6). We note without proof that the random tree T can be constructed as a balanced binary tree, so that Lemma 6 is unnecessary, and Lemma 7 is still true. So we get a worst case (instead of expected) guarantee of on the length of the path from the root to (and hence on the number of per client query). This concludes the proof of Theorem 2. To prove Theorem 3, where the client queries are assumed to be uniformly and independently chosen in we observe that the choices the client makes can be used to build T. More precisely, we can build T on the fly, as follows: The root of T is the first client query. The left child of is the first client query in the interval and the right child of is the first client query in the interval In general, the root of any subtree in T is the first client query in the interval corresponding to that subtree. Clearly, this results in a tree T drawn from the same probability distribution as in So we still have Lemma 7, guaranteeing the upper bound on the expected distance between and But now we observe that for any new client query the path from the root of T to (excluding was already queried, so we need only one more namely This concludes the proof of Theorem 3.
References 1. Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Estimating the distance to a monotone Function. Proc. 8th RANDOM, 2004
Property-Preserving Data Reconstruction
27
2. Fischer, E.: The art of uninformed decisions: A primer to property testing. Bulletin of EATCS, 75: 97-126, 2001 3. Goldreich, O.: Combinatorial property testing - A survey. “Randomization Methods in Algorithm Design,” 45-60, 1998 4. Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45 (1998), 653–750 5. Hoffmann, C.M., Hopcroft, J.E., Karasick, M.S.: Towards implementing robust geometric computations. Proc. 4th SOCG (1988), 106-117. 6. Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation. ECCC 2004 7. Ron, D.: Property testing. “Handbook on Randomization,” Volume II, 597-649, 2001 8. Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25 (1996), 647–668 9. Salesin, S., Stolfi, J., Guibas, L.J.: Epsilon geometry: building robust algorithms from imprecise computations. Proc. 5th SOCG (1988), 208-217
On the Monotone Circuit Complexity of Quadratic Boolean Functions Kazuyuki Amano and Akira Maruoka Graduate School of Information Sciences, Tohoku University, Aoba 6-6-05, Aramaki, Sendai 980-8579, Japan {ama|maruoka}@ecei.tohoku.ac.jp
Abstract. Several results on the monotone circuit complexity and the conjunctive complexity, i.e., the minimal number of AND gates in monotone circuits, of quadratic Boolean functions are proved. We focus on the comparison between single level circuits, which have only one level of AND gates, and arbitrary monotone circuits, and show that there is a huge gap between the conjunctive complexity of single level circuits and that of general monotone circuits for some explicit quadratic function. Almost tight upper bounds on the largest gap between the single level conjunctive complexity and the general conjunctive complexity over all quadratic functions are also proved. Moreover, we describe the way of lower bounding the single level circuit complexity, and give a set of quadratic functions whose monotone complexity is strictly smaller than its single level complexity.
1
Introduction
Deriving a superlinear lower bound on the Boolean circuit-size complexity for an explicit Boolean function is one of the most challenging problems in computational complexity. In order to attack the problem, the complexity of many types of restricted circuits have been investigated. The model of monotone Boolean circuits, i.e., circuits with only AND and OR gates, is one of the most well-studied models. In this paper, we investigate the monotone circuit complexity of the class of quadratic Boolean functions, i.e., functions of the form where Although we have a series of strong lower bounds on the monotone circuit complexity of explicitly defined Boolean functions [2, 3, 4, 5, 7, 8, 9, 15, 16, 18], such as exponential lower bounds for the clique function, we believe that an investigation of the monotone complexity of quadratic functions is important for several reasons: (i) The method of approximations and many variants of them have been successful to obtain exponential lower bounds on the monotone circuit complexity [2, 3, 4, 5, 7, 8, 9, 15, 16, 18]. However, several researchers have pointed out that these methods are shown to be equivalent [4, 5, 8, 9, 18]. In addition, a simple analysis of the method shows that it cannot yield any non-trivial lower R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 28–40, 2004. © Springer-Verlag Berlin Heidelberg 2004
On the Monotone Circuit Complexity of Quadratic Boolean Functions
29
bounds on the monotone circuit complexity of a quadratic Boolean function. This is because the method is in fact lower bounding the minimum of the number of AND gates and that of OR gates needed to compute the function, and every quadratic Boolean function on variables can be computed by a monotone circuit including at most AND gates. So a superlinear lower bound for quadratic Boolean functions may imply an essentially different method for lower bounding the monotone circuit complexity. (ii) For some natural class of quadratic Boolean functions, which we will describe in Section 4, we can show that a superlinear lower bound on the monotone circuit complexity of a function in that class immediately implies the lower bound of the same order on the general circuit complexity of In addition, we hope that a lower bound proof that is highly specialized for a particular function may not fulfill the “largeness” condition in the notion of “natural proof” [17]. A quadratic Boolean function is naturally represented by a graph. Let G = (V, E) be an undirected graph with vertex set and edge set A quadratic (Boolean) function associated with G is defined by There have been a series of researches on the complexity of quadratic Boolean functions (sometimes under the name of graph complexity), which are mostly concerned on the circuits of constant depth with unbound fan-in gates (e.g., [10, 12, 14]). In this paper, we restrict the fan-in of gates to two and mainly focus on the comparison between single level monotone circuits and general monotone circuits. A single level circuit is a circuit which has only one level of AND gates. Obviously, every quadratic function can be computed by a single level circuit of size Not surprisingly, if we restrict ourselves to circuits of single level, we can easily derive a superlinear lower bound on the size. (We will describe this in more detail in Section 3.3.) However, it seems quite difficult to obtain a good lower bound on the general monotone circuit size for an explicit quadratic function. One of the major difference between single level circuits and general circuits in a computation of quadratic functions relies on the use of “absorption” rule, i.e., (and We think that an investigation on the efficiency of the absorption rule in a monotone computation may be a key to obtain a tighter/higher lower bound on the monotone complexity, and this was the initial motivation of our work. The contributions of this paper are as follows: First, in Section 3, we consider the conjunctive complexity of quadratic Boolean functions. The conjunctive complexity of a quadratic function is the minimal number of AND gates in a monotone circuit that computes Such measures have been widely studied by e.g., Tuza [20], Lenz and Wegener [11]. In Section 3,2, we prove that there is a huge gap between the conjunctive complexity of single level circuits and that of general monotone circuits for some explicit quadratic function (Theorem 2). Almost tight upper bounds on the largest gap between the single level conjunctive complexity and the general conjunctive complexity over all quadratic
30
K. Amano and A. Maruoka
functions are also proved (Theorem 4). Then, in Section 3.3, we describe the way of lower bounding the single level circuit complexity (Theorem 8), and give a set of quadratic functions whose monotone circuit complexity is strictly smaller than its single level complexity (Theorem 10). Finally, in Section 4, we discuss the relationship between the complexity of monotone circuits and of non-monotone circuits for quadratic functions based on the notion of pseudo complements (Theorem 11).
2
Boolean Circuits
A Boolean circuit is a directed acyclic graph. Nodes with indegree zero are called input nodes and there are distinguished nodes with outdegree zero called output nodes. An input node is labeled by a Boolean variable or a constant 0 or 1. Each non-input node has indegree 2 or 1 and is called the gate node. A gate node of indegree 2 is labeled by a Boolean operation AND or OR A gate node of indegree 1 is labeled by a Boolean operation NOT (¬). A gate in a Boolean circuit computes a Boolean function in a natural way. If is a gate in a Boolean circuit, we will also use to denote the function computed by A Boolean circuit computes Boolean functions that are computed by the output gates. A monotone Boolean circuit is a Boolean circuit that contains no NOT gates. A Boolean function that can be computed by a monotone Boolean circuit is called a monotone Boolean function. Since we will not discuss any non-Boolean functions, we may drop the word “Boolean”.
3 3.1
Single Level Versus Multi Level Notations
Let G = (V, E) be an undirected graph with vertex set and edge set A quadratic (Boolean) function associated with G is defined by For a monotone circuit C, the level of C is defined as the maximal number of AND gates on a path from an input to an output in C. In particular, a circuit of level 1, i.e., a circuit such that no path combines AND gates, is called a single level circuit. Obviously, for every graph G = (V, E) on the function can be computed by a single level circuit including at most AND gates and OR gates using the form Let be a monotone function. The circuit complexity (the monotone circuit complexity, resp.) of denoted by resp.), is the minimal number of gates in a Boolean circuit (a monotone circuit, resp.) for and the single level complexity of denoted by is the minimal number of gates in a single level monotone circuit for In this paper, we also investigate the number of AND gates needed to compute a function, which is called as the conjunctive complexity. The conjunc-
On the Monotone Circuit Complexity of Quadratic Boolean Functions
31
tive complexity (the single level conjunctive complexity, resp.) of denoted by resp.), is the minimal number of AND gates in a monotone circuit (a single level monotone circuit, resp.) that computes
3.2
Conjunctive Complexity
If we restrict ourselves to circuits of single level, the conjunctive complexity of a quadratic function is equal to the minimal number of complete bipartite graphs whose union (of the edge sets) coincides with G. Since the single level conjunctive complexity is a purely graph theoretical complexity measure, it has been widely studied (see e.g., [11]). In contrast, little is known about the conjunctive complexity In the following, we show that almost all quadratic functions have a conjunctive complexity which improves the lower bound of Lenz and Wegener [11]. We remark that it was shown that almost all quadratic functions have a single level conjunctive complexity of larger than Theorem 1. For each functions is larger than cn.
the conjunctive complexity of almost all quadratic
Proof. The proof of the theorem is analogous to the proof of the lower bound due to Lenz and Wegener [11]. The only difference is to use the result of Zwick [24], which says that if can be computed by a monotone circuit that contains AND gates, then can also be computed by a monotone circuit that contains AND gates and OR gates, instead of the result of Alon and Boppana [2], which is slightly weaker than the result of Zwick. Careful inspection of Zwick’s proof reveals that the hidden constant in the Big-O notation of their upper bound is at most 3. The standard counting argument shows that, for each the monotone circuit complexity of almost all quadratic functions is at least Hence, for almost all graphs on vertices G, if we denote the conjunctive complexity of by then
holds. A simple calculation shows that
for sufficiently large
One might conjecture that an optimal circuit for a quadratic function with respect to the conjunctive complexity is always given by a single level circuit. This was known as the single level conjecture (with respect to the conjunctive complexity) and was disproved by Lenz and Wegener [11]. They provided an explicit graph H on 8 vertices such that and asked what the largest possible value of is (as open problem No. 7 in [11]). In the following, we improve their result by giving an explicit construction of a graph G on vertices such that
32
K. Amano and A. Maruoka
Theorem 2. There is a graph G on and
vertices such that
Proof. Let
be a bipartite graph with and For simplicity, we assume that for some positive integer Let G be a graph on such that where and are the complete graphs on U and V respectively. In the following, we show that and First, we show that Let C be a single level monotone circuit for For a function let denote the set of all prime implicants of Since contains edges, it is sufficient to show that for every gate in C, if contains more than two edges in then can be eliminated without changing the output of C. Let and be two inputs of Note that and are OR’s of variables. Suppose that contains three edges in say Then, w.l.o.g., we can assume that for some distinct indices and are appearing in and and are appearing in This implies that contains which is not included in Hence cannot contribute the output of C, and can be removed safely. We now show that Let be a positive integer whose value will be chosen later. Let and For simplicity, we assume that is an integer. For we represent by a vector It will be convenient to consider that is represented by an number. For and let resp.) be the set of variables consists of all resp.) such that for some i.e., the digit of the representation of is equal to We claim that is equivalent to
where OR(X) denotes the disjunction of all variables of X and denotes the function on variables, i.e., it outputs 1 iff the number of ones in an input is greater than or equal to Before we show the correctness of Eq. (1), we determine the value of and estimate the number of AND gates needed to compute Eq. (1). Since (i) the AND of functions can be computed by a circuit of level log with AND gates, and (ii) the 2-threshold function on variables can be computed by a single level circuit that includes AND gates1, we can construct a circuit including at most 1
Proof: Let and consider that an integer is represented by a log binary number. Let be the OR of all such that digit of binary representation of is equal to Then it is easy to check that
On the Monotone Circuit Complexity of Quadratic Boolean Functions
AND gates. If we choose
33
the RHS of Eq. (2) is upper bounded by
Now we proceed to the proof of the correctness of Eq. (1). Obviously, for an input with at most 1 ones, both and Eq. (1) output 0. For an input with at least 3 ones, both and Eq. (1) output 1 because (at least) one of two sets U and V contain at least 2 variables that assigned the value 1. Thus, the interesting cases are for an input with 2 ones. (Case 1) or for some Obviously, both and Eq.(1) output 1 in this case. (Case 2) for some By the definition of G, outputs 1 on such an input. For each if is equal to the digit of representation of This implies the output of Eq. (1) is also 1. (Case 3) for some By the definition of G, outputs 0 on such an input. Since there is such that the digit of the representation of and are different. For such the value of is 0, and this implies the output of Eq. (1) is also 0. Remark 3. The graph we defined in the proof of Theorem 2 consists of three subgraphs, and Interestingly, the single level conjunctive complexity and the conjunctive complexity of each subgraph are identical, i.e., and Let Theorem 2 shows that is trivial since ture that our lower bound is tight, i.e., a slightly weaker upper bound of
Note that the upper bound of for every G on vertices. We conjecBelow we prove
Theorem 4. Let G be a graph on vertices. Suppose that for some function Then Proof. (Sketch) Let G be a graph on vertices whose single level conjunctive complexity is Let C be an arbitrary monotone circuit that computes Below we show that C must contain AND gates. For a monotone function let be the set of all prime implicants of whose length is The covering number of denoted by cov(h), is defined as the minimal such that there are pairs of sets of variables that satisfy (i) (ii) and (iii) In such a case, we say that a set of pairs covers Obviously, for every G.
K. Amano and A. Maruoka
34
We define the operation as follows: Suppose that Then is the disjunction of all prime implicants of whose length is at most 2. Let C* be a circuit obtained from C by replacing each gate in C with gate. The theorem known as the “replacement rules” (see e.g., [22, Theorem 5.1]) guarantees that the circuit C* also computes In the following, we assume that if and are two inputs of an gate in C*, then and are disjoint. (If then we replace by where is obtained from by removing all prime implicants in S. This does not affect on the number of gates in C* and the output of C*. In addition, this replacement has no influence on the covering number of each gate.) For an gate in C*, the level of is defined as the maximal number of gates on a path from an input to (the output of) Note that the lowest gate is of level 1. Let be the level of the circuit C*, and for let be the number of gates whose level is Note that the number of gates in C*, say is given by Let be an arbitrary gate of level in C*. We claim that
To prove these inequalities, we need the following lemma. Lemma 5. Let Then Proof. as
Let
where the
Suppose that
and
and and
and
We can express
and
are disjunctions of variables such that We have
It is easy to check that, for each pair covered by two pairs Similarly, each pair can be covered by a set of at most
can be and resp.) can be covered by a resp.). Altogether, pairs.
On the Monotone Circuit Complexity of Quadratic Boolean Functions
35
Proof of Theorem 4 (continued). By Lemma 5, Eq. (4) immediately implies Eq. (3) for each Hence we only need to show Eq. (4). We show this by induction on The base case, is obvious since RHS of Eq. (4) is and the covering number of an input of an gate of level 2 is shown to be at most The induction step is as follows : Since the function computed by an input of an gate of level can be represented by the disjunction of variables and outputs of gates of level at most the covering number of it is upper bounded by
which completes the proof of the induction step. The assumption in the statement of the theorem implies that times the value of Eq. (3) for is and this implies (since Hence we have which completes the proof of the theorem.
3.3
Disproving Single Level Conjecture for Multi-output Functions
Again, if we restrict ourselves to circuits of single level, a good lower bound on can easily be derived by combining the graph theoretic arguments and the results that have been developed for obtaining a lower bound on the monotone complexity of the Boolean sums, which we state below. Definition 6. Let is a set of Boolean sums if each function is a disjunction of variables in X. For a disjunction f of variables in X, we use denote the subset of X on which essentially depends. A set of Boolean sums F is called if for every holds. Theorem 7 ([13]). Let be a set of Boolean sums. If F is then the size of an optimal monotone circuit for F is at least
By using the above theorem, we can show the following. Theorem 8. Let G = (V, E) be a graph that does not contain a copy of Then
36
K. Amano and A. Maruoka
Proof. Let C be an optimal single level monotone circuit for We represent where is the number of AND gates in C, and and are disjunctions of variables computed by the inputs of the AND gate. For each at least one of or contain at most one variable. This is because if and then G must contain (if two sets are disjoint), or must contain a prime implicant of length 1 (if two sets are not disjoint). Hence, without loss of generality, we can assume that for every (by exchanging and if necessary). Let Now we convert C to a circuit by the following construction:
Since we can save AND gates and the number of additional OR gates we need is shown to be at most the size of is not greater than that of C. For each let It is obvious that is a subset of the set of neighbors of Since G does not contain for every distinct Hence the set of functions can be viewed as the (1, 1)-disjoint Boolean sums. Therefore, the size of is at least
The first inequality follows from Lemma 7. An explicit construction of the graph on vertices that does not contain and has edges based on the notion of the “projective plane” was known (e.g., [1]). The above theorem yields for such G. We remark that we can extend the arguments of the proof of Theorem 8 for a graph that does not contain a copy of for Thus an explicit construction for such a graph may yield higher lower bounds on the size of single level circuits. The question that then arises is : “Is there a quadratic function such that is strictly smaller than The problem of answering this question was stated as open problem in [11]. We have shown in the previous section that the answer is “yes” if we only count the number of AND gates. In the following, we show that the answer is also “yes” if we consider a set of quadratic functions. For a set of graphs a set of quadratic functions associated with denoted by is defined by the set of functions Lemma 9. Let
be a set of Boolean sums on be a set of quadratic functions on
Let
On the Monotone Circuit Complexity of Quadratic Boolean Functions
37
where each is obtained from by replacing each variable in with the conjunction Then an optimal single level monotone circuit for F is a circuit obtained from an optimal monotone circuit for H that consists of OR gates only by replacing each input node with an AND gate Proof. Let C be an optimal single level monotone circuit for F. Let be an AND gate in C. Since C is a single level circuit, we can represent where and are disjunctions of variables. Suppose that contains a prime implicant not of the form for some In such a case, there is an assignment to the input variables that contains at most 2 ones such that outputs 1 and outputs 0 for every This implies that there are no paths from an input to an output of C that leads through (since C is a single level circuit), and this contradicts the assumption that C is optimal. Hence we can conclude that every AND gate computes the conjunction of the form for some
Theorem 10. There is a set of graphs is strictly smaller than
such that
Proof. To prove the theorem, we use the construction of Boolean sums given by Tarjan [19] (or [22, p. 164]), which was used for disproving that AND gates are powerless for computing Boolean sums. Let be a set of Boolean functions on defined as follows: Let
and define for It was shown that 18 OR gates are necessary to compute H if no AND gates are used. On the other hand, we can compute H by a circuit that contains 16 OR gates and one AND gate (an AND gate that computes can save two OR gates.) Define a set of the quadratic functions as in the statement of Lemma 9. By the above argument, we have On the other hand, by Lemma 9, we have which completes the proof of the theorem. As for the case of the conjunctive complexity, to determine the largest possible value of seems to be an interesting subject. The construction in the proof of Theorem 10 gives the lower bound of 29/28. More sophisticated constructions may yield a slightly better constant. The authors do not know whether there is a set of quadratic functions F such that the ratio is more than a constant at the time of writing this paper.
K. Amano and A. Maruoka
38
4
Monotone Versus Non-monotone
The graph G that we defined in the proof of Theorem 2 has the form of where is a bipartite graph, and and are the complete graphs on U and V respectively. Interestingly, it is shown that NOT gates are almost powerless for quadratic functions associated with graphs of such form. Theorem 11. (implicitly in [21]) Let G be a graph on where for some partition
such that Then
Proof. (Sketch) In fact, the result by Wegener [21, Theorem 4.4] is of the form For the purpose of completeness and in order to determine the hidden constants, we describe the sketch of the proof. Given an optimal circuit C computing By using the DeMorgan’s law, we can convert C to a so-called standard circuit for that is a Boolean circuit in which the permitted gate operations are and whose input nodes are labeled by literals, whose size is at most twice of the size of C. Let and Let and Let be a function computed by a circuit obtained from by replacing each resp.) with resp.) and each resp.) with resp.). The key to the proof is the observation that can be computed by (In other words, we can use and as pseudoinputs and and as pseudocomplements for and respectively. See [21] for more details.) By following the equation
where
and
we can compute and with at most gates. Clearly, additional gates are suffice to compute OR(U) and OR(V). All and can be computed with gates. Moreover, gates are suffice to compute all and Altogether we use at most gates. We remark that the standard counting argument shows that the circuit complexity of almost all quadratic functions associated with graphs of the form where is For a bipartite graph let be the graph The relationship between the monotone complexity of and of seems to be an interesting. Since is known to be we have On the other hand, we do not know whether or not. However, if we consider multioutput functions, computing a set of functions may significantly easier than computing a set of functions
On the Monotone Circuit Complexity of Quadratic Boolean Functions
The
Boolean convolution is the function with output
39
defined by
Each
is naturally represented by a bipartite graph where and Let denote the function with output It was known that the monotone complexity of the Boolean convolution is [23] and the (general) circuit complexity of it is [22, p.168]. These imply that whereas
Acknowledgments. The authors would like to thank anonymous reviewers for their helpful suggestions which helped in improving the quality of this paper.
References 1. N. Alon, Eigenvalues, Geometric Expanders, Sorting in Rounds, and Ramsey Theory, Combinatorica 6 (1986) 207–219 2. N. Alon and R. Boppana, The Monotone Circuit Complexity of Boolean Functions, Combinatorica 7(1) (1987) 1–22 3. A. Andreev, On a Method for Obtaining Lower Bounds for the Complexity of Individual Monotone Functions, Soviet Math. Dokl. 31(3) (1985) 530–534 4. K. Amano and A. Maruoka, The Potential of the Approximation Method, SIAM J. Comput. 33(2) (2004) 433–447 (Preliminary version in : Proc. of 37th FOCS (1996) 431–440) 5. C. Berg, S. Ulfberg, Symmetric Approximation Arguments for Monotone Lower Bounds Without Sunflowers, Computational Complexity 8(1) (1999) 1–20 6. P.E. Dunne, The Complexity of Boolean Networks, Academic Press (1988) 7. A. Haken, Counting Bottlenecks to Show Monotone Proc. of 36th FOCS (1995) 36–40 8. D. Harnik, R. Raz, Higher Lower Bounds for Monotone Size, Proc. of 32nd STOC (2000) 191–201 9. S. Jukna, Combinatorics of Monotone Computations, Combinatorica 19(1) (1999) 65-85 10. S. Jukna, On Graph Complexity, ECCC TR04-004 (2004) 11. K. Lenz and I. Wegener, The Conjunctive Complexity of Quadratic Boolean Functions, Theor. Comput. Sci. 81 (1991) 257–268 12. S.V. Lokam, Graph Complexity and Slice Functions, Theory Comput. Syst. 36 (2003) 71–88 13. K. Mehlhorn, Some Remarks on Boolean Sums, Acta Inf. 12 (1979) 371–375 and P.Savický, Graph Complexity, Acta Inf. 25 (1988) 515–535 14. P. Pudlák, 15. A. Razborov, Lower Bounds on the Monotone Complexity of Some Boolean Function, Soviet Math. Dokl. 31 (1985) 354–357 16. A. Razborov, On the Method of Approximation, Proc. 21th STOC (1989) 167–176
40
K. Amano and A. Maruoka
17. A. Razborov, S. Rudich, Natural Proofs, J. Comput. Syst. Sci. 55(1) (1997) 24–35 18. J. Simon and S.C. Tsai, On the Bottleneck Counting Argument, Theor. Comput. Sci. 237(1-2) (2000) 429–437 19. R. Tarjan, Complexity of Monotone Networks for Computing Conjunctions, Ann. Disc. Math. 2 (1978) 121–133 20. Z. Tuza, Covering of Graphs by Complete Bipartite Subgraphs, Complexity of 0-1 Martix, Combinatorica 4 (1984) 111–116 21. I. Wegener, More on the Complexity of Slice Functions, Theor. Comput. Sci. 43 (1986) 201–211 22. I. Wegener, The Complexity of Boolean Functions, Wiley-Teubner (1987) 23. J. Weiss, An Lower Bound on the Complexity of Boolean Convolution, Info. and Cont. 59 (1983) 84–88 24. U. Zwick, On the Number of ANDs versus the Number of ORs in Monotone Boolean Circuits, Inf. Process. Let. 59 (1996) 29–30
Generalized Function Matching Amihood Amir1,* and Igor Nor2,** 1
Department of Computer Science, Bar-Ilan University, Ramat-Gan 52900, Israel +972-3-531-8770, Fax +972-3-736-0498 College of Computing, Georgia Tech, Atlanta, GA 30332-0280 2 Department of Computer Science, Bar-Ilan University, Ramat-Gan 52900, Israel {amir, norigo}@cs.biu.ac.il
Abstract. We present problems in different application areas: tandem repeats (computational biology), poetry and music analysis, and author validation, that require a more sophisticated pattern matching model that hitherto considered. We introduce a new matching criterion – generalized function matching – that encapsulates the notion suggested by the above problems. The generalized function matching problem has as its input a text T of length over alphabet and a pattern of length over alphabet We seek all text locations where the prefix of the substring that starts at is equal to for some function We give a polynomial time algorithm for the generalized pattern matching problem over bounded alphabets. We identify in this problem an important new phenomenon in pattern matching. One where there is a significant complexity difference between the bounded alphabet and infinite alphabet case. We prove that the generalized pattern matching problem over infinite alphabets is To our knowledge, this is the first case in the literature where a pattern matching problem over a bounded alphabet can be solved in polynomial time but the infinite alphabet version is Keywords: Pattern matching, function matching, parameterized matching,
1
Introduction
The last few decades have prompted the evolution of pattern matching from a combinatorial solution of the exact string matching problem [15,17] to an area concerned with approximate matching of various relationships motivated by computational molecular biology, computer vision, and complex searches in * Partly supported by NSF grant CCR-01-04494 and ISF grant 282/01. ** Partly supported by ISF grant 282/01. R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 41–52, 2004. © Springer-Verlag Berlin Heidelberg 2004
42
A. Amir and I. Nor
digitized and distributed multimedia libraries [14, 8]. In [2] a new generalized matching paradigm, that of function matching, was introduced. In this paper we generalize the function matching model to make it more suitable for several important applications in a number of diverse areas. In the traditional pattern matching model, one seeks exact occurrences of a given pattern in a text, i.e. text locations where every text symbol is equal to its corresponding pattern symbol. In the parameterized matching problem, introduced by Baker [10], one seeks text locations where there exists a bijection on the alphabet for which every text symbol is equal to the image under of the corresponding pattern symbol. The parameterized matching problem was introduced by Baker [10]. Her main motivation lay in software maintenance, where program fragments are to be considered “identical” even if variable names are different. Therefore, strings under this model are comprised of symbols from two disjoint sets and containing fixed symbols and parameter symbols respectively. In this paradigm, one seeks parameterized occurrences, i.e., occurrences up to renaming of the parameter symbols, of a string in another. This renaming is a bijection In [2] it was pointed out that for some applications cannot be a bijection. Rather, it should be simply a function. More precisely, P matches T at location if for every element all occurrences of have the same corresponding symbol in T. In other words, unlike in parameterized matching, there may be a several different symbols in the pattern which are mapped to the same text symbol. An example of a problem where parameterized matching proves insufficient and function matching is required is the following. One of the interesting problems in web searching is searching for color images (e.g. [20, 9, 5]). The simplest possible cases is searching for an icon in a screen, a task that the Human-Computer Interaction Lab at the University of Maryland was confronted with. If the colors were fixed, then this is exact two-dimensional pattern matching [4]. However, if the color map is different the exact matching algorithm would not find the pattern. Parameterized two dimensional search is precisely what is needed. If, in addition, we are also willing to lose resolution, then we would use a two dimensional function matching search. However, even a function can not answer more sophisticated questions on the text structure where the repeating element is not a single symbol, but rather, say, a substring. A very useful and famous example is the tandem repeat. Tandemly repeated DNA sequences are widespread throughout the human genome and show sufficient variability among individuals in a population that they have become important in several fields including genetic mapping, linkage analysis, and human identity testing. This importance has led to very active research in efficient algorithms to find tandem repeats (e.g. [11]). Tandem repeats may appear in various lengths. They are called sattelites in the ranges of 100 kb to over 1 Mb, minisattelites in the ranges of 1 kb to 20 kb, and micro sattelites or short tandem repeats (STRs) in the range of 1 to 6 base pairs. The repeat is not just a single repetition. In the case of STR’s, for example, the whole repetitive region may span up to 150 base pairs. Thus, an analysis of a repeat region may be a
Generalized Function Matching
43
query of the type: Find a region of the form AAAAA, which means: “find a region where a substring appears adjacent to itself five times”. Clearly one may think of more complex combinations, and interrelations between different substrings. Other motivations for the problem may arise from poetry and music analysis, or author validation, among others. Various forms of poetry have quite a rigid order and organization. For example, the English or Shakespearean sonnet uses the rhyme scheme ABABCDCDEFEFGG, the Italian sonnet using the rhyme scheme ABBAABBACDECDE. Various music forms also have a distinct structure. One may want to search for a repeated theme, for instance. Finally, in the authorship verification problem one is asked to verify authorship of an anonymous (or fraudulent) text (e.g. [16]). It is possible that certain writing structure will give the clue. The above examples are a sample of diverse application areas encountering search problems that are not solved by state of the art methods in pattern matching. This need led us to introduce, in this paper, the generalized function matching criterion, and to explore the efficiency of searching in this paradigm. Definition 1. The Generalized Function Matching with Don’t Cares Problem is defined as follows. Input: Text T of length over alphabet Pattern P of length over alphabet where is a “don’t care”. A in the text matches any pattern symbol, while in the pattern matches any text substring. Output: Every index for which there exist some function such that the prefix of the text substring starting at is equal to Function matching was a natural generalization of parameterized matching. However, relaxing the bijection restriction introduced non-trivial technical difficulties. Many powerful pattern matching techniques such as automata methods [17,12], subword trees [23, 13], dueling [21, 4] and deterministic sampling [22] assume transitivity of the matching relation. For any pattern matching criteria where transitivity does not exist, the above methods do not help. Examples of pattern matching with non-transitive matching relation are string matching with “don’t cares” [15], less-than matching [7], pattern matching with mismatches [1, 18] and swapped matching [19, 3, 6]. It is interesting to note that the efficient algorithms for solving the above problems all used convolutions as their main tool. Convolutions were introduced by Fischer and Paterson [15] as a technique for solving pattern matching problems where the match relation is not transitive. Indeed, in [2] convolutions played a key role in the efficient algorithm for function matching. It turns out that for generalized function matching, even convolutions are not powerful enough. There are three main contributions in this paper. 1. The introduction of an important new type of generalized pattern matching, that of generalized function matching. 2. An example of an important new phenomenom in pattern matching. One where there is a significant complexity difference between the bounded al-
44
A. Amir and I. Nor
phabet and infinite alphabet case. In all known pattern matching applications to date it was always the case that a polynomial time algorithm for infinite alphabet existed whenever a polynomial time algorithm for a bounded alphabet existed. A couple of examples are the exact matching case, where the time for both bounded and infinite alphabet is linear [17], pattern matching with mismatches, where the time for bounded alphabets is and for infinite alphabets is [1]. To our knowledge, this is the first case where a pattern matching problem over a bounded alphabet can be solved in polynomial time but the infinite alphabet version is 3. We show a polynomial time algorithm for the generalized function matching problem with don’t cares over bounded alphabets. We prove that the generalized function matching problem with don’t cares over infinite alphabets is
2
The Bounded Alphabet Case
We reformulate the problem using simplified notations. The generalized function matching with don’t cares problem is the following. Input: Text Pattern Output: All text locations for which such that (where we denote and Note that also in the case where there are in Each such matches the symbol in that is aligned with it. Notice also that the in the pattern can be replaced by different characters that are not in Formally, let be the number of don’t cares in the pattern. Define Let be the string obtained by replacing the ith with Lemma 1. The generalized function matches of in T.
in T are exactly those of P
Proof: It is clear that any generalized function matching of in T is also a generalized function matching of P in T. The other direction is also true since the only property that may be lost by the replacement is the injectivity. But since function matching (unlike parameterized matching) does not require this property, this is not a problem. Note: The don’t cares replacement is linear relatively to since the maximal number of don’t cares in the pattern is Note also that we have made an implicit assumption that “don’t care” in the pattern can match anything in the text. A more limiting assumption would be that a “don’t care” can only match the image under of a symbol from Here we choose to apply the broadest possible interpretation. We will show in section 3 that the generalized function matching problem with don’t cares in the text only is for infinite alphabets. Lemma 1
Generalized Function Matching
45
guarantees that for infinite alphabets this problem is equivalent to the generalized function matching with don’t cares problem. In this section we proceed to give a polynomial time algorithm for the generalized function matching problem with don’t cares in the text only for bounded alphabets. The algorithm is a simple greedy algorithm. Algorithm’s Idea: For every text location consider every pattern symbol sequentially, trying to match it to all possible substrings starting where the last matched substring ended. Clearly this greedy strategy “blows up” for infinite alphabets, but for bounded alphabets, once all symbols were assigned to a substring there is only one possible assignment for every symbol. We present a pseudocode of the algorithm and its time analysis.
Algorithm’s Time: It is easy to see that the algorithm can be streamlined and achieve time In any event, for a fixed bounded alphabet, the time is for some - clearly polynomial.
3
The Infinite Alphabet Case
Before proving the it is necessary to convert the given optimization problem to a decision problem. It is possible to choose the most general way for this purpose, so that the only requirement for the decision problem is to answer the question “Is there a generalized function matching of the given pattern in the text?”. Formally, the generalized function matching decision problem is the following. Definition 2. The Generalized Function Matching with Don’t Cares Decision Problem is defined as follows. Input: Text Pattern Decide: Is there a text locations i, for which
where
46
A. Amir and I. Nor
Theorem 1.
is
Proof: Clearly
Suppose there is an input and Guess text location and guess a function Now verify the following: 1. Construct by replacing every by 2. Compare (character-by-character) to 3. If there is equality then accept, else reject. Clearly the guess is polynomial in the input size: at most elements for each of the (possibly) different symbols of P, for a total of The verification is linear time. We now show that Definition 3. The Vertex Cover(VC) problem is the following. Input: Graph G = (V,E), positive integer Decide: Does G contain and either
or
The Reduction: Given a general input of the VC problem G = (V,E), we construct the input for the generalized function matching. Define: different symbols that will be assigned generalized function matching. Refer to these symbols as pattern variables. different symbols whose task is pattern blocks borders. different symbols whose task is text blocks borders. pattern and text block separators. Denote by
and
means
sequential appearances of the pattern
or text separator, respectively. We refer to them as sequential separator sets (of text or pattern). sequential don’t cares. We are ready to construct the pattern.
where The text is constructed as follows:
where and are the two vertices of edge and parameter separators’ repetitions will be specified later.
the number of
Generalized Function Matching
47
The idea of the reduction is to build a text block for every graph edge. This text block contains the two vertices that define the edge, a lot of don’t cares, whose purpose will be explained in the following lemmas, and two more symbols, different from all others, that are located at the left and the right block borders. The number of pattern and text blocks is equal to the number of edges. Every two adjacent blocks are separated by block separators, (different in the text and pattern). The pattern blocks are almost identical (except for their borders), and can be matched to any text block. Lemma 2. The reduction is polynomial in the size of the input problem. Proof: Each pattern block contains and 2 different The pattern contains pattern blocks, so without counting the pattern separators the size is: which is In the text, every edge appears exactly once and for each of them there is one block. So, a text block contains 2 symbols for 2 edge vertices, 3 sets of don’t care and 2 borders symbols. There are text blocks, so not counting the text separators the size is: which is Define the number of times sequential separators repeat, to be for both pattern and text separators. The reduction stays polynomial size since the number of separators will be the main part of the pattern and text. The pattern size is therefore while the text size is also it means both of them are polynomial in the input size. Example: V = (1, 2, ..., 9), E = ((1,2), (2,5), (3,5), (1,8)),
The next lemma is the main lemma required for the Lemma 3. which Proof:
VC of Assume
in G = (V, E) such that
proof.
there is a text location
VC of size in G. This means there is a set In this case there is a match located at
it is: only one to and the rest that surround the
thus
for
and
while for every match will be set to don’t cares
Lemma 4. The matching described above exists. Proof: Based on the VC existence assumption, for every edge (text block) there is at least one symbol which is in Thus, for every block in
48
A. Amir and I. Nor
the text, there is at least one symbol that belongs to the VC. So, choose this symbol for Since there are don’t cares on both sides of any in the reduced text, set to a left of and to a right of Assign to since their number is the same. All other matches are between sets of separators and are not within those sets so there are no intersections by this matching. This way one can match any pattern blocks to the parallel text block while the remaining symbols inside the text block will be set to and Since to the left and right of in any block there are at least symbols don’t cares and one there is always at least one symbol for any A schematic of this function matching appears below.
where the
blocks match is:
Assume
index
function
such that
Lemma 5. Proof: The number of repetitions of the pattern separator is It can only be function matched to a symbol that appears at least 1) times. The only such text symbol is
and it appears exactly
times. Therefore Lemma 6. Any set of sequential
is matched to set of sequential
Proof: Since every is matched to either or But pattern separators are located sequentially, in sets of while the maximal number of sequential in the text is which is less than the number of sequential separators. Thus, it is impossible to match one complete set to sequential don’t cares only. On the other hand, the symbols immediately to the left and right of a text separator are and respectively, and they are different from the text separator symbol. Thus, the only way for generalized function matching of a sequence of pattern separators is to match it to a sequence of text separators. The immediate conclusion from the above lemmas is that every set of sequential pattern separators is matched to a set of sequential text separators. Moreover, the beginning of this matching is from the first text character:
Generalized Function Matching
49
This means that for every the ith set of pattern separators is assigned to the ith set of text separators. This leads to the conclusion that the existence of a generalized function matching on a pattern and text constructed by the reduction causes every pattern block to be matched to the text block with the same index. Schematically we get:
Lemma 7. For every pattern block that is generalized function matched to text block such that for such that or In other words, either or is in the sequence matched by one of the Proof: We start by claiming that every pattern block has at least one that is assigned to some text block symbols which are not solely don’t cares. This is clear since the maximum number of sequential don’t cares is while the number of sequentially located is at least one of them matches to non don’t cares symbols. Moreover, since and have to be matched to some not empty text symbols, will be the first symbol of matching, while has to be the last symbol of matching. Thus, for every pattern block such that where one of the is either or the two graph vertices that define the appropriate graph edge. The idea for finding the vertex cover in case of generalized function matching is based on the next simple fact. The Single Matching Claim: If every is matched to exactly one symbol (and the rest of the symbols are matched to and then the matching is the VC. Proof: Based on the proven property that for every block there is at least one that matches to a sequence that has or (or both) symbol, and adding the assumption that the size of all matchings is exactly 1, one can conclude that for every block there is exactly one that is matched to some while the other pattern variables are matched to in this block. The reason is that around any there are thus if is matched to a and the size of every matching is 1, the other pattern variables should be matched to in this particular block. This reasoning is true for all blocks. Thus, generalized function matching covers every text block and, as a result, every graph edge. The number of the pattern variables is so the vertex cover size is also The following lemma shows how to construct a generalized function matching that satisfies the requirement of the single matching claim, i.e. that for all pattern variables Once this is the case, the single matching claim guarantees the existence of a vertex cover of size
50
A. Amir and I. Nor
Lemma 8. Suppose there is a generalized function matching on the constructed pattern and text and suppose there are for which Then one can construct another generalized function matching where Proof: By induction on Base Case: Assume there is exactly one for which while for all other pattern variables It is necessary to show that in this case there is another generalized function matching such that Proof: Let be the only pattern variable where We will show that there is a matching where is the only pattern variable where We do that iteratively by starting from the situation where is the only pattern variable for which and creating a matching where is the only pattern variable for which This iteration is proven by the following lemma. Lemma 9. Suppose there is exactly one so that while all other pattern variables are matched to a single symbol. Denote and Then one can change the matching so that and all others pattern variables have the same assignments as they had had before. Proof: Suppose that the suggested change is not a correct generalized function matching. This means there is some text block that is not the match of pattern block using the suggested matching. The only pattern variables whose assignments were changed were and and they always follow each other. Therefore the generalized function matching of the pair remains unchanged. Note that if there was injectivity before, it may now be lost, however, this is not a requirement in function matching. Thus in case of this local change the entire matching will stay correct. The following lemma immediately follows, since one can iteratively “move to the left” the symbol such that until it becomes Lemma 10. Under the induction base case conditions, one can change the generalized function matching so the only pattern variable that will be matched to more than one symbol will be the first one while the others will be matched to exactly one text symbol. Our current situation is that we have a generalized function matching where every pattern variable, except the first, is matched to a single text symbol. The following lemma shows how to construct a matching where every pattern variable is matched to a single text symbol, and then by the single matching claim we have a vertex cover.
Generalized Function Matching
Lemma 11. If a matching exists where the matching where Proof: Let
51
and
Then construct matching for every block j,
such that
and is a generalized function matching since there is no problem with the because they are different in every block. also must match in every block because was a function and is simply the last element of
Induction Step: Assume correctness for Prove the correctness for Let be the leftmost pattern variable that satisfies Then while all pattern variables for are matched to exactly one text symbol, to the right of there are pattern variables that are matched to more than one text symbol. Consider One can perform the same trick that had been done in the base case of the induction – construct a different generalized function matching by transfering all symbols of to except the first symbol. The correctness of this operation is explained in a similar fashion to that of the base case of the induction. As a result, while and this is another correct generalized function matching. If was equal to 1 in the original matching, continue performing this change in right direction until reaching the first where satisfies the condition: Performing the operation now reduces the number of pattern variables that are matched to more than one symbol to so one can use the induction hypothesis and complete the proof.
4
Conclusion and Open Problems
We have shown what is, to our knowledge, the first known pattern matching problem that has a polynomial time solution for bounded alphabets but is for infinite alphabets. It would be interesting to find out whether the generalized function matching without don’t cares has a polynomial time solution. Also, it is of interest to know whether generalized parameterized matching is or in Finally, the generalized function matching problem has many applications. Thus it is important to find a good approximation to the problem.
References l. K. Abrahamson. Generalized string matching. SIAM J. Comp., 16(6):1039–1051, 1987. 2. A. Amir, A. Aumann, R. Cole, M. Lewenstein, and E. Porat. Function matching: Algorithms, applications, and a lower bound. In Proc. 30th ICALP, pages 929–942, 2003. 3. A. Amir, Y. Aumann, G. Landau, M. Lewenstein, and N. Lewenstein. Pattern matching with swaps. Proc. 38th IEEE FOCS, pages 144–153, 1997.
52
A. Amir and I. Nor
4. A. Amir, G. Benson, and M. Farach. An alphabet independent approach to two dimensional pattern matching. SIAM J. Comp., 23(2):313–323, 1994. 5. A. Amir, K. W. Church, and E. Dar. Separable attributes: a technique for solving the submatrices character count problem. In Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 400–401, 2002. 6. A. Amir, R. Cole, R. Hariharan, M. Lewenstein, and E. Porat. Overlap matching. In Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 279–288, 2001. 7. A. Amir and M. Farach. Efficient 2-dimensional approximate matching of halfrectangular figures. Information and Computation, 118(1):1–11, April 1995. 8. A. Apostolico and Z. Galil (editors). Pattern Matching Algorithms. Oxford University Press, 1997. 9. G.P. Babu, B.M. Mehtre, and M.S. Kankanhalli. Color indexing for efficient image retrieval. Multimedia Tools and Applications, 1(4):327–348, Nov. 1995. 10. B. S. Baker. A theory of parameterized pattern matching: algorithms and applications. In Proc. 25th Annual ACM Symposium on the Theory of Computation, pages 71–80, 1993. 11. G. Benson. Tandem repeats finder: a program to analyze dna sequence. Nucleic Acids Research, 27(2):573–580, 1999. 12. R.S. Boyer and J.S. Moore. A fast string searching algorithm. Comm. ACM, 20:762–772, 1977. 13. M. T. Chen and J. Seiferas. Efficient and elegant subword tree construction. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, chapter 12, pages 97–107. NATO ASI Series F: Computer and System Sciences, 1985. 14. M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, 1994. 15. M.J. Fischer and M.S. Paterson. String matching and other products. Complexity of Computation, R.M. Karp (editor), SIAM-AMS Proceedings, 7:113–125, 1974. 16. D. Holmes. The evolution of stylometry in humanities scholarship. Literary and Linguistic Computing, 13(3):111–117, 1998. 17. D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comp., 6:323–350, 1977. 18. S. Rao Kosaraju. Efficient string matching. Manuscript, 1987. 19. S. Muthukrishnan. New results and open problems related to non-standard stringology. In Proc. 6th Combinatorial Pattern Matching Conference, pages 298– 317. Lecture Notes in Computer Science 937, Springer-Verlag, 1995. 20. M. Swain and D. Ballard. Color indexing. International Journal of Computer Vision, 7(1):11–32, 1991. 21. U. Vishkin. Optimal parallel pattern matching in strings. Proc. 12th ICALP, pages 91–113, 1985. 22. U. Vishkin. Deterministic sampling - a new technique for fast pattern matching. SIAM J. Comp., 20:303–314, 1991. 23. P. Weiner. Linear pattern matching algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1–11, 1973.
Approximate Distance Oracles for Graphs with Dense Clusters Mattias Andersson1, Joachim Gudmundsson2, and Christos Levcopoulos1 1
Department of Computer Science, Lund University, Box 118, 221 00 Lund, Sweden
[email protected],
[email protected] 2
Department of Mathematics and Computing Science, TU Eindhoven, 5600 MB, Eindhoven, the Netherlands
[email protected]
Abstract. Let
be a collection of N pairwise vertex disjoint where the weight of an edge is equal to the Euclidean distance between its endpoints. Let be a graph on with M edges of non-negative weight. The union of the two graphs is denoted We present a data structure of size that answers shortest path queries in in constant time, where is constant.
1
Introduction
The shortest-path (SP) problem for weighted graphs with vertices and edges is a fundamental problem for which efficient solutions can now be found in any standard algorithms text, see also [8, 11, 18]. Lately the approximation version of this problem has also been studied extensively [2, 7, 9]. In numerous algorithms, the query version of the SP-problem frequently appears as a subroutine. In such a query, we are given two vertices and have to compute or approximate the shortest path between them. Thorup and Zwick [20] presented an algorithm for undirected weighted graphs that computes solutions to the query version of the SP problem in time, using a data structure that takes expected time to construct and utilizes space. It is not an approximation scheme in the true sense because the value needs to be a positive integer. Since the query time is essentially bounded by a constant, Thorup and Zwick refer to their queries as approximate distance oracles. We focus on the geometric version of this problem. A geometric graph has vertices corresponding to points in and edge weights from a Euclidean metric. Throughout this paper we will assume that is a constant. A geometric graph is said to be a for if for any two points and in there exists a path of length at most times the Euclidean distance between and For geometric graphs, also, considerable previous work exists on the shortest path and related problems. A good survey can be found in [17], see also [3, 6, 10, 19]. The geometric query version was recently studied by Gudmundsson et al. [13, 14] R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 53–64, 2004. © Springer-Verlag Berlin Heidelberg 2004
54
M. Andersson, J. Gudmundsson, and C. Levcopoulos
Fig. 1. The three figures models parts of the transportation network in Norway, Sweden and Finland. (a) The domestic railway network in the three countries (not complete). (b) The railway connections between the countries together with the main air and sea connections within, and between, Norway, Sweden and Finland. (c) The two networks combined into one graph
and they presented the first data structure that answers approximate shortestpath queries in constant time, provided that the input graph is a for some known constant Their data structure uses space and can be constructed in time In this paper we extend the results in [13, 14] to hold also for “islands” of i.e., a set of N vertex disjoint inter-connected through “airports” i.e. M edges of arbitrary non-negative weight. We construct a data structure that can answer shortest path queries in constant time. The data structure uses space and can be constructed in time Hence, for the bound is essentially the same as in [13, 14]. We claim that the generalization studied is natural in many applications. Consider for example the freight costs within Norway, Sweden and Finland, see Fig. 1. The railway network and the road network within a country are usually for some small value and the weight (transport cost) of an edge is linearly dependent on the Euclidean distance. In Fig. 1a the railway networks of Norway, Sweden and Finland (although not complete) is shown. The weight of an edge is dependent on the Euclidean distance between its endpoints. Hence, each country’s railway network and road network can most often be modeled as a Euclidean for some small constant (Places that are not reachable by train are treated as single containing only one point, for example Haugesund on the west coast of Norway is only reachable by boat.). Apart from these edges there are also edges that model, for example, air freight, sea freight, or inter-connecting railway transports. An example of this is shown Fig. 1b, where the main air and sea routes together with the inter-connecting railway tracks are shown. The weight of these edges can be completely independent of the Euclidean distance, as is usually the case when it comes to air fares. The
Approximate Distance Oracles for Graphs with Dense Clusters
55
reason why inter-connecting railway transport is included in the latter set of edges is because the railway networks of different countries are usually sparsely connected. For example, there are one connection between Sweden and Finland, four between Norway and Sweden, and zero between Finland and Norway. In [14] it was shown that an approximate shortest-path distance oracle can be applied to a large number of problems, for example, finding a shortest obstacle-avoiding path between two vertices in a planar polygonal domain with obstacles and interesting query versions of closest pair problems. The extension presented in this paper also generalizes the results for the above mentioned problems. The main idea for obtaining our results is to develop a method to efficiently combine existing methods for with methods for general graphs. One problem, for example, may be given a starting point and a destination which should be the first airport to travel to, since (in theory) there might be a non-constant number of airports on island? In order to achieve this, we determine a small number, of representative “junction” points, so that every point in the graph is represented by exactly one such junction point located on the same island as All endpoints of the M edges of are also treated as such junction points. For all pairs of junction points we precompute approximate distances, using space For any two points and an approximately shortest path between them is found either by only using edges of one of the or by following a path from to its representative junction point then from to and finally from to In order to choose such a small set of suitable representative junction points we present, in Section 2.4, a partition of space which may be useful also in other applications. In Section 3 we show general correctness, and in Section 4 we mention some refinements and extensions of the main results. Due to lack of space, many proofs are omitted in this extended abstract. Our model of computation is the traditional algebraic computation model with the added power of indirect addressing. We will use the following notation. For points and in denotes the Euclidean distance between and If is a geometric graph, then denotes the Euclidean length of a shortest path in between and If P is a path in between and of length with then P is a shortest path for and The main result of this paper is stated in the following theorem: Theorem 1. Consider two graphs and where is a collection of N vertex disjoint Euclidean is a constant), and is a graph with M edges of non-negative weight. The union of the two graphs is denoted One can construct a data structure in time using space that can answer shortest path queries in in constant time, where is a given constant. The set of pairwise vertex disjoint and will be denoted
of
is called the “islands” of An edge is
56
M. Andersson, J. Gudmundsson, and C. Levcopoulos
said to be an inter-connecting edge (even though both its endpoints may belong to the same island). A vertex incident to an edge in is called an airport, for simplicity (even though these vertices may represent any kind of junction point). The set of all airports of is denoted Note that the total number of airports is since the number of inter-connecting edges is M.
2
Tools
In the construction of the distance oracle we will need several tools, among them the well-separated pair decomposition by Callahan and Kosaraju [5], a graph pruning tool by Gudmundsson et al. [14, 15] and well-separated clusters by Krznaric and Levcopoulos [16]. In this section we briefly recollect these tools. In section 2.4 we also show a useful tool that clusters points with respect to a subset of representative points, as described in the introduction.
2.1
Well-Separated Pair Decomposition
Definition 1. [5] Let be a real number, and let A and B be two finite sets of points in We say that A and B are well-separated with respect to if there are two disjoint balls and having the same radius, such that contains A and, contains B, and the distance between and is at least times the radius of We refer to as the separation ratio. Lemma 1. [5] Let A and B be two sets of points that are well-separated with respect to let and be two points of A, and let and be two points of B. Then and Definition 2 ([5]). Let S be a set of points in and let be a real number. A well-separated pair decomposition (WSPD) for S with respect to is a sequence of pairs of non-empty subsets of S, such that 1. for all 2. for each unordered pair of distinct points of S, there is exactly one pair in the sequence, such that (i) and or (ii) and 3. and are well-separated with respect to for all
The integer is called the size of the WSPD. Callahan and Kosaraju show how such a WSPD can be computed. They start by constructing in time, a split tree T having the points in S as leaves. Given this tree, they show how a WSPD of size can be computed in time In this WSPD, each pair is represented by two nodes and of T. That is, and are the sets of all points stored at the leaves of the subtrees rooted at and respectively. Theorem 2. [5] Let S be a set of points in WSPD for S with respect to having size time.
and let be a real number. A can be computed in
57
Approximate Distance Oracles for Graphs with Dense Clusters
2.2
Pruning a
In [14] it was shown how the WSPD can be used to prune an existing Assume that we are given a Compute a WSPD for with separation constant and Let be the graph that contains for each exactly one (arbitrary) edge of E with and provided such an edge exists. It holds that is a spanner of and hence: Fact 1. (Corollary 1 in [15]) Given a real constant and a for some real constant with vertices and edges, one can compute a of with edges in time
2.3
Well-Separated Clusters
Let be a set of points in the plane, and let be a real constant. Let the rectangular diameter of abbreviated be the diameter of the smallest axis-aligned rectangle containing We may now consider the following cluster definitions from [16]: Definition 3. A subset of is a between any point of and any point of
if equals or the distance is greater than
Definition 4. The hierarchy of of is a rooted tree whose nodes correspond to distinct such that the root corresponds to and leaves to single points of Let be any internal node and let be its corresponding The children of correspond to every such that and there is no such that The following observation is straightforward. Observation 1. Let A and B be two distinct and let points of A, and let and be two points of B. Then Proof. Assume w.l.o.g that
and that
and
be two
This means
The cluster tree can also be computed efficiently. Theorem 3. Let hierarchy of
2.4
be a set of points in and a real constant of can be computed in time and space.
the
Partitioning Space into Small Cells
Given a set of points in and a subset we will show how to associate a representative point with each point such that the distance for any point is a good approximation of the distance The total number of representative points is The idea is to partition space into cells, such that all points included in a cell may share a common representative point. We will use the following fact by Mount et al. [4]:
58
M. Andersson, J. Gudmundsson, and C. Levcopoulos
Fact 2. (Theorem 1 in [4]) Consider a set of points in There is a constant such that in time it is possible to construct a data structure of size such that for any Minkowski metric: (i) Given any and a nearest neighbor of in S can be reported in (ii) More generally, given and any a sequence of nearest neighbors can be computed in time. Computing Representative Points. As input we are given the point set and a positive real value Set As a pre-processing step we compute the tree of with as described in Theorem 3. For a level in let be the nodes at that level, where are the associated clusters. For each cluster pick an arbitrary vertex as the center point of The set of the center points is denoted Perform the following four steps for each level of 1. Compute an approximate nearest neighbor structure with as input, as described in Fact 2. 2. For each center point in compute the nearest neighbor of The point returned by the structure is denoted where 3. For each cluster construct two squares; and with centers at and side length and respectively, where The two squares are called the inner and outer shells of and the set theoretical difference between the inner and the outer shell is denoted the doughnut of 4. The inner shell of is recursively partitioned into four equally sized squares, until each square either (a) is completely included in the union of the outer shells of the children of In this case the square is deleted and, hence, not further partitioned. Or, where K is the smallest distance between (b) has diameter at most a point within and a point in of K can be computed in time This implies that the diameter of is bounded by
The resulting cells are denoted inner cells. Note that, due to step 4a, every inner cell is empty of points from Finally, after all levels of have been processed, we assign a representative point to each point in Preprocess all the produced cells and perform a point-location query for each point. If belongs to a doughnut cell then the center point of the associated cluster (see step 1) is the representative point of
Approximate Distance Oracles for Graphs with Dense Clusters
59
Otherwise, if belongs to an inner cell C and is the first point within C processed in this step then rep(C) is set to If is not the first point then Further, note that an inner cell may overlap with the union of the outer shells of the children of If a point is included in both an inner cell and an outer shell, we treat it as if it belonged to the inner cell, and assign a representative point as above. We state the main result of this section. Theorem 4. Given a set of points in a subset and a positive real value the above algorithm associates with each point a representative point such that for any point it holds that
The number of representative points is
3
and they can be computed in time
Constructing the Oracle
This section is divided into three subsections: first we present the construction of the structure, then how queries are answered and, finally the analysis is presented. Consider two graphs and with the same vertex set, where is a collection of N vertex disjoint Euclidean with edges where is a constant, and is a graph with M edges of non-negative weight. The union of the two graphs is denoted
3.1
Constructing the Basic Structures
In this section we show how to pre-process in time such that we obtain three structures that will help us answer approximate distance queries in constant time. We will assume that the number of edges in each subgraph is linear with respect to the number of vertices in if not the subgraph is pruned using Fact 1. Hence, we can from now on assume that Let be the set of vertices in incident on an inter-connecting edge. Now we can apply Theorem 4 with parameters and to obtain a representative point for each point in Now we are ready to present the three structures: Oracle A: An oracle that given points and returns a 3-tuple where SI is a boolean with value ‘true’ if and belongs to the same island, otherwise it is ‘false’, and and are the representative points for and respectively. Oracle B: An approximate distance oracle for any pair of points belonging to the same island. Matrix D: An matrix. For each pair of representative points, and D contains the approximate shortest distance between and
60
M. Andersson, J. Gudmundsson, and C. Levcopoulos
The representative point of a point is denoted and the set of all representative points of and is denoted and respectively. Note that Now we turn our attention to the construction of the oracles and the matrix. Oracle A: The oracle is a 4-level tree, denoted with the points of corresponding to the leaves of The parents of the leaves correspond to the representative points of and their parents correspond to the islands of Finally, the root of corresponds to Since the representative points already are computed, the tree can be constructed in linear time. The root is at level 0 and the leaves are at level 3 in Assume that one is given two points and Follow the paths from and respectively to the root of If and have the same ancestor at level 1 then they lie on the same island and hence SI is set to ‘true’, otherwise to ‘false’. Finally, the ancestor of and the ancestor of at level 2 correspond to the representative points of and Obviously a query can be answered in constant time since the number of levels in is four. Oracle B: This oracle is the structure that is easiest to build since we can apply the following result to each of the islands (see also [14]). Fact 3. Let be a set of points in let be a positive real constant and let be a for for some real constant having edges. In time we can preprocess into a data structure of size such that for any two points and in we can in constant time compute a to the shortest-path distance in between and Hence, oracle B will actually be a collection of oracles, one for each island. Given two points and the appropriate oracle can easily be found in constant time using a similar construction as for oracle A. Thus, after preprocessing using space, shortest path queries between points on the same island can be answered in constant time. Matrix D: For each compute the WSPD of with separation constant As output we obtain a set of well-separated pairs such that Next, construct the non-Euclidean graph where is constructed as follows. For each and each well-separated pair of the WSPD of select two (arbitrary) representative points and Add the edge to with weight where denotes a call to oracle for with parameters and Note that the graph will have vertices and edges. Let D be an matrix. For each representative point compute the single-source shortest path in to every point in and store the distance of each path in The total time for this step is and it can be obtained by running Dijkstra’s algorithm M times. Lemma 2. The oracles A and B, and the matrix D can be built in time and the total complexity of A, B and M is
Approximate Distance Oracles for Graphs with Dense Clusters
Fig. 2. Illustrating the approximate shortest path between the “airports” along the path
and
61
The boxes illustrate
Proof. The lemma is obtained by adding up the complexity for the pre-processing together with the cost of building each structure. Recall that as pre-processing steps we first pruned the subgraphs and then we computed the representative point for each point in This was done in time using space, according to Fact 1 and Theorem 4. Next, oracle A was constructed in linear time using linear space, followed by the construction of oracle B which, according to Fact 3 was done in time using space. Finally, the matrix D was constructed by first computing the graph Then a single-source shortest path query was performed for each vertex in Since the complexity of is it follows that D was computed in time using space. Hence, adding up these bounds gives the lemma.
3.2
Querying
Given the two oracles and the matrices presented above the query algorithm is very simple, see pseudo-code below. Let denote the representative point of Now assume that we are given two points and If and do not belong to the same island we return the sum of and If and belong to the same island then we query Oracle B with input and return the value obtained from the oracle. Obviously this is done in constant time.
3.3
Correctness
Let and
be a shortest path in a graph between two points to be positive real values such that
and
Set
62
M. Andersson, J. Gudmundsson, and C. Levcopoulos
Observation 2. Let
and
be any pair of points in
Observation 3. Given a point where Lemma 3. Let
and
It holds that
it holds that
be any pair of representative points in
it holds that
Proof. Note that it suffices to prove that according to Observation 2. The proof is done by induction on the Euclidean length of Base case: Recall that was constructed to build the matrix D. Assume that is the closest pair of In this case there exists a wellseparated pair such that and otherwise could not be the closest pair. Hence the claim holds since there is an edge in of weight Induction hypothesis: Assume that the lemma holds for all pairs in closer than to each other. Induction step: If then there exists an edge in and a wellseparated pair such that and According to the induction hypothesis there is path between and of weight and a path between and of weight Also, the weight of the edge is Putting together the weights we obtain that
In the third step we used the fact that Corollary 1. Let
and be any representative points in
Lemma 4. Given a pair of points
it holds that
Lemma 5. Let
it holds that
and
be any points in
it holds that
Approximate Distance Oracles for Graphs with Dense Clusters
63
Proof.
On line 1 we used Observation 2 together with Lemma 3. On the following line we used Observation 3, applied Lemma 4 and finally replaced with Putting together Lemma 2 and Lemma 5 gives us Theorem 1. For convenience we restate Theorem 1 below: Theorem 1. Consider two graphs and where is a collection of N vertex disjoint Euclidean is a constant), and is a graph with M edges of non-negative weight. The union of the two graphs is denoted One can construct a data structure in time using space that can answer shortest path queries in in constant time, where is a given constant.
4
Conclusion
In this paper we presented a data structure that answers approximate distance queries in constant time in the case when the input is a set of vertex disjoint Euclidean inter-connected with edges of arbitrary weight. The result can be slightly extended and improved. For example, the data structure can be modified to handle the case when each island is a i.e., every island has different (although constant) dilation. Also, a refined analysis yields that the data structure of Theorem 1 only uses space, where is the set of all airports. Recall that the subdivision of the graph into islands needs to be given. An interesting open problem is to find such a subdivision, i.e., compute a subdivision of a graph into a minimum number of vertex-disjoint The problem is NP-hard in the case when since this is equivalent to finding a minimum clique partition which is known to be NP-hard. For general graphs the problem cannot be approximated within a factor of in polynomial time [1].
64
M. Andersson, J. Gudmundsson, and C. Levcopoulos
References 1. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi. Complexity and Approximation – Combinatorial optimization problems and their approximability properties. Springer Verlag, ISBN 3-540-65431-3, 1999. 2. D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167–1181, 1999. 3. S. Arikati, D. Z. Chen, L. P. Chew, G. Das, M. Smid, and C. D. Zaroliagis. Planar spanners and approximate shortest path queries among obstacles in the plane. In Proc. 4th European Symposium on Algorithms, pp. 514-528, 1996. 4. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching. Journal of the ACM, 45(6):891-923, 1998. 5. P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to and potential fields. Journal of the ACM, 42(1):67–90, 1995. 6. D. Z. Chen. On the all-pairs Euclidean short path problem. In Proc. 6th ACMSIAM Symposium on Discrete Algorithms, pp. 292-301, 1995. 7. E. Cohen. Fast algorithms for constructing and paths with stretch SIAM Journal on Computing, 28(1):210–236, 1998. 8. E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. In Numerische Mathmatik vol. 1, 1959. 9. D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740–1759, 2000. 10. D. Eppstein and D. Hart. Shortest Paths in an Arrangement with Line Orientations. 10th ACM-SIAM Symposium on Discrete Algorithms, pp. 310-316, 1999. 11. M. L. Fredman, R. E. Tarjan Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, 1987. 12. D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338–355, 1984. 13. J. Gudmundsson, C. Levcopoulos, G. Narasimhan and M. Smid. Approximate Distance Oracles Revisited. In Proc. 13th International Symposium on Algorithms and Computation, pp. 357-368, 2002. 14. J. Gudmundsson, C. Levcopoulos, G. Narasimhan and M. Smid. Approximate Distance Oracles for Geometric Spanners. Submitted August 2004. http://win.tue.nl/ hgudmund/glns-adogs-04.pdf. Extended abstract published in Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 828-837, 2002. 15. J. Gudmundsson, G. Narasimhan and M. Smid. Fast Pruning of Geometric Spanners. Submitted June 2004. http://win.tue.nl/ hgudmund/gns-fps-04.pdf 16. D. Krznaric and C. Levcopoulos. Computing hierarchies of clusters from the Euclidean minimum spanning tree in linear time. In Proc. 15th Conf. on Foundations of Software Technology and Theoretical Computer Science, pp. 443-455, 1995. 17. J. S. B. Mitchell. Shortest paths and networks. In Handbook of Discrete and Computational Geometry, pp. 445–466. CRC Press LLC, 1997. 18. R. Raman. Recent results on the single-source shortest paths problem. SIGACT News 28:81-87,1997. 19. J. A. Storer and J. H. Reif. Shortest Paths in the Plane with Polygonal Obstacles. Journal of the ACM, 41(5): 982-1012, 1994. 20. M. Thorup and U. Zwick. Approximate distance oracles. In Proc. 33rd ACM Symposium on Theory of Computing, pp. 183-192, 2001.
Multicriteria Global Minimum Cuts Amitai Armon and Uri Zwick School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel
Abstract. We consider two multicriteria versions of the global minimum cut problem in undirected graphs. In the setting, each edge of the input graph has non-negative costs associated with it. These costs are measured in separate, non interchangeable, units. In the AND-version of the problem, purchasing an edge requires the payment of all the costs associated with it. In the OR-version, an edge can be purchased by paying any one of the associated with it. Given bounds the basic multicriteria decision problem is whether there exists a cut C of the graph that can be purchased using a budget of units of the criterion, for We show that the AND-version of the multicriteria global minimum cut problem is polynomial for any fixed number of criteria. The ORversion of the problem, on the other hand, is NP-hard even for but can be solved in pseudo-polynomial time for any fixed number of criteria. It also admits an FPTAS. Further extensions, some applications, and multicriteria versions of two other optimization problems are also discussed.
1
Introduction
We consider two multicriteria versions of the global minimum cut problem in undirected graphs. Let G = (V, E) be an undirected graph, and let be nonnegative cost (or weight) functions defined on its edges. A cut C of G is a subset such that and The edges cut by this cut are (As the graph is undirected, C and V–C define the same cut.) In the AND-version of the problem, the weight (or cost) of the cut is
In the OR-version of the problem we pay only one of the costs associated with each edge of the cut. More specifically, we choose a function which specifies which cost is paid for each edge of the cut. The cost of the cut C, with respect to the choice function is then cost in the OR-version: R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 65–76, 2004. © Springer-Verlag Berlin Heidelberg 2004
66
A. Armon and U. Zwick
The basic multicriteria global minimum cut decision problem asks, given cost bounds is there a cut C such that for In the optimization problem we are given bounds and asked to find a cut C for which is minimized, subject to the constraints for The min-max version of the problem asks for a cut C for which is minimized, i.e., a cut whose largest cost is as small as possible. The Pareto set of an instance is the set of cost vectors of cuts that are not dominated by the cost vector of any other cut. It follows, therefore, that if is the cost vector of a cut of the graph, then there exists a vector such that for Corresponding definitions can be made for the OR-version of the problem. Multicriteria optimization is an active field of research (see, e.g., the books of Climacao [3] and Ehrgott [4]). (Most research is focused, in our terminology, on AND-versions of various optimization problems. All results cited below refer to the AND-versions of the problems, unless stated otherwise.) Papadimitriou and Yannakakis [17] investigated the complexity of several multicriteria optimization problems. In particular, they considered the multicriteria minimum cut problem, in which the cut must separate two specified vertices, and They proved that this problem is strongly NP-complete, even for just two criteria. We show here that (the AND-version of) the multicriteria global minimum cut decision problem can be solved in polynomial time for any fixed number of criteria, making it strictly easier than its variant. The running time of our algorithm is where is the number of edges in the graph, is the number of vertices, and is the number of criteria. This easily implies tractability of the optimization problem and also yields a pseudo-polynomial algorithm for constructing the Pareto set. The problem, however, becomes strongly NP-hard when the number of criteria is not fixed. We also show that the directed version of the problem is strongly NP-hard even for just two criteria. The single-criterion minimum cut problem has been studied for more than four decades as a fundamental graph optimization problem (see, e.g., [6, 15, 13, 19, 11, 12]). Minimum cuts are used in solving a large variety of problems, including VLSI design, network design and reliability, clustering, and more (see [12] and references therein). The best known deterministic algorithms for this problem run in time (Nagamochi and Ibaraki [15] and Stoer and Wagner [19]). The best known randomized algorithm runs in time (Karger [12]). (A huge gap between the deterministic and randomized complexities!) These algorithms are faster than the best known algorithms for the minimum cut problem which are based on network flow. The polynomial time algorithm for the multicriteria problem relies on the fact that the standard single criterion global minimum cut problem has only a polynomial number of almost optimal solutions. More specifically, Karger and Stein [13] showed that for every not necessarily integral, the number of solutions is only Karger [12] improved this bound to Nagamochi et al. [16] gave a deterministic time algo-
Multicriteria Global Minimum Cuts
67
rithm for finding all the cuts. Our algorithm for the multicriteria problem uses their algorithms. Apart from the theoretical interest in minimum cuts in the multicriteria setting, there are some applications in which this problem is of interest. (The multicriteria global minimum cut problem is of interest in almost any application of the single criterion global minimum cut problem.) A multicriteria minimum balanced-partition is required, for example, in the situations described in [18]. A special case of the bicriteria global minimum cut problem, called the min-cut, was considered by Bruglieri et al. [1,2]. The input to this problem is an undirected graph G = (V,E) with a single weight function defined on its edges. The goal is to find a cut of minimum cost that contains at most edges. This is exactly the optimization version of the bicriteria minimum cut problem, where for every and must not exceed Bruglieri et al. [1, 2] ask whether this problem can be solved in polynomial time. We answer their question in the affirmative. We also obtain a polynomial time algorithm for finding a minimum cut which contains at most vertices on the smallest side of the cut. As mentioned, most research on multicriteria optimization focused, in our terminology, on AND-versions of various multicriteria optimization problems. We consider here also the OR-versions of the global minimum cuts problem, the shortest path problem, and the minimum spanning tree problem. OR-versions of multicriteria optimization problems may be seen as generalizations of the scheduling problem on unrelated machines (see [9,14,10]). The input to such a scheduling problem is a set of jobs that should be scheduled on machines. The job has a cost vector associated with it, where is the processing time of the job on the machine. The goal is to allocate the jobs to the machines so as to minimize the makespan, i.e., the completion time of the last job. (Jobs allocated to the same machine are processed sequentially.) This is precisely the OR-version of the min-max minimum cut problem on a graph with two vertices and parallel edges. As another example where the OR-version of the multicriteria minimum-cut problem is of interest, consider a cyber-terrorist wishing to disconnect a computer network, where there is more than one option for damaging each link. Specifically, assume that each link can either be disconnected by an electronic attack, which requires a certain amount of work hours (that may differ for different links), or by physically disconnecting it, e.g. by cutting an underground cable using explosives (the required amount may again differ from link to link). Given an upper bound on the amount of available explosives, what is the minimum time required for electronic attacks? It follows immediately from the simple reduction given above that the ORversion of the multicriteria global minimum cut problem is NP-hard even for just two criteria. We show, however, that the problem can be solved in pseudopolynomial time for any fixed number of criteria. We also show that the problem can be solved in polynomial time when the number of criteria, is fixed and at least of the weight functions assume only a fixed number of values. We also
68
A. Armon and U. Zwick
obtain some results on the complexity of the OR-versions of the shortest path and minimum spanning tree problems. The rest of this paper is organized as follows. In the next section we consider the AND-version of the global minimum cut problem. In Section 3 we then consider the OR-version of the problem. In Section 4 we consider the OR-version of the multicriteria shortest path and minimum spanning tree problems. Finally, we conclude in Section 5 with some concluding remarks and open problems.
2
Multicriteria Global Minimum Cut: The AND-Version
We first present a polynomial time algorithm for the min-max version of the multicriteria global minimum cut. The algorithm for solving the min-max version of the problem is then used to solve the decision and optimization problems.
2.1
The Min-Max Problem
An optimal min-max cut is a cut C for which is minimized. We show that the simple algorithm given in Figure 1 solves the min-max version of the global minimum cut problem in polynomial time, for every fixed A cut in a graph G with respect to a single weight function is a cut whose weight is at most times the weight of the minimum cut. Theorem 1. Algorithm Min-Max solves the min-max version of the global minimum cut problem. For any fixed it can be implemented to run, deterministically, in time. Proof. We begin by proving the correctness of the algorithm. We show that if C is an optimal min-max cut, and D is any other cut in the graph, then where for every This follows as
The inequality follows from the assumption that C is an optimal min-max cut. In particular, if D is an optimal minimum cut with respect to the single weight function then and it follows that C is a cut of G with respect to This proves the correctness of the algorithm. We next consider the complexity of the algorithm. Karger and Stein [13] showed that every graph has at most cuts and gave a randomized algorithm for finding an implicit representation of them all in time. A deterministic algorithm of Nagamochi et al. [16] explicitly finds all the cuts in time. Choosing the best min-max cut among all the cuts also takes only time. It is also easy to see that for any solution to the min-max problem in approximate cuts in
we can find an time, by checking all the
Multicriteria Global Minimum Cuts
69
The randomized algorithm of Karger and Stein [13] extends to finding all the minimum in time. (An is a partition of the graph vertices into sets, instead of 2). Thus, it is easy to see that the min-max multicriteria problem can also be solved for in time using this randomized (Monte-Carlo) algorithm.
2.2
The Decision Problem
We next show that the algorithm for the min-max version of the lem can be used to solve the decision version of the problem: Given is there a cut C such that for Theorem 2. For any fixed the decision version of the imum cut problem can be solved, deterministically, in
probbounds
global mintime.
Proof. The decision problem can be easily reduced to the min-max problem. Given weight functions and bounds we simply produce scaled versions for every and of the weight functions. Clearly the answer to the decision problem is ‘yes’ if and only if there is a cut C for which
2.3
The Optimization Problem
We next tackle the optimization problem: Given bounds a cut C for which is minimized, subject to to the constraints for
find
Theorem 3. For any fixed the optimization version of the global minimum cut problem for graphs with integer edge weights can be solved, deterministically, in time, where Proof. If the weight function assumes only integral values, we can easily use binary search to solve the optimization problem. Given the bounds we conduct a binary search for the minimal value for which there is a cut C such that for As the minimal is an integer in the range [0, M], this requires the solution of only O(log M) decision problems. The algorithm given above is not completely satisfactory as it is not strongly polynomial and does not work with non-integral weights. These problems can be fixed, however, as we show below. Theorem 4. For any fixed the optimization version of the global minimum cut problem for graphs with arbitrary real edge weights can be solved, deterministically, in time. Proof. We first isolate a small interval that contains the minimal value of Let be the set of values assumed by the weight function.
70
A. Armon and U. Zwick
The minimum of the optimization problem lies in an interval for some (If C is the cut that attains the optimum, let be the weight of the heaviest edge, with respect to in the cut.) Using a binary search on the values in S, we can find such an interval that contains the minimum. This requires the solution of only decision problems. Next, we conduct a binary search in the interval until we narrow it down to an interval of the form which is guaranteed to contain the right answer. This again requires the solution of only decision problems. Next, we run a modified version of the Min-Max algorithm given in Figure 1 on the following scaled versions of the weights: for and It is easy to see that if C is an optimal solution of the optimization problem, then C is also an solution of the min-max problem. This in turn implies, as in the proof of Theorem 1, that C is also a minimum cut with respect to the weight function for every Instead of finding all the minimum cuts with respect to as done by algorithm Min-Max, we find all the minimum cuts. Among all these cuts we find a cut C for which i.e., for and for which is minimized. This cut is the optimal solution to the optimization problem. We next analyze the complexity of the algorithm. The decision problems can be solved in time. All the cuts can then be found in time using the algorithm of Nagamochi et al. [16]. (Note that Checking all these cuts also takes only time. This completes the proof of the theorem.
Fig. 1. A strongly polynomial time algorithm for the min-max version of the global minimum cut problem
2.4
Two Applications
Theorem 5. Let G = (V, E) be an undirected graph and let be a weight function defined on its edges. Let Then, there is a deterministic time algorithm for finding a cut of minimum weight that contains at most edges.
Multicriteria Global Minimum Cuts
Proof. We simply let the optimization problem with
and
for every
71
and solve
As mentioned in the introduction, this solves an open problem raised by Bruglieri et al. [1,2]. We also have: Theorem 6. Let G = (V, E) be an undirected graph and let be a weight function defined on its edges. Let Then, there is a deterministic time algorithm for finding a cut of minimum weight with at most vertices on its smaller side. Proof. We set up two weight functions over a complete graph on for every and if otherwise. We then find a cut C that minimizes the constraint
2.5
vertices: and subject to
The Pareto Set
Suppose all weight functions are integral. Let for The Pareto set can be trivially found by invoking the basic decision algorithm times, or the optimization algorithm times. These naive algorithms are pseudo-polynomial for every fixed Using very similar ideas we can also obtain an FPTAS for finding an approximate Pareto set, a notion defined by Papadimitriou and Yannakakis [17]. It is defined as a set of feasible such that for every solution there is a in the set within a factor of in all coordinates. More formally, the set is a set of cost vectors of cuts in the graph such that for every cut C there exists such that for It is easy to see that we can find this set in polynomial time by checking only powers of instead of checking all the possible values.
2.6
Hardness Results
Theorem 7. The multicriteria minimum cut problem with a non-fixed number of criteria is strongly NP-complete. Proof. We use a reduction from the bisection width problem (see [5], problem ND17): Given an unweighted input graph G = (V,E) on vertices and a bound is there a bisection of the graph that cuts at most edges? We transform such an instance in the following way: Assume that We add two vertices, and and add edges connecting them to each of the vertices in V. Let be the resulting graph. Each edge of is now assigned weights. For we let and for all other edges. We assign for the edges of the form and otherwise. Similarly, we assign for the edges of the form and otherwise. Finally, for and otherwise. It is now easy to see that G has a bisection of width
72
A. Armon and U. Zwick
at most
if and only if has a cut C for which and
for
It is also not difficult to show that the directed multicriteria global minimum cut problem is strongly NP-complete even for two criteria. We omit the details.
3 3.1
Multicriteria Global Minimum Cut: The OR-Version Relation to Scheduling on Unrelated Machines
As mentioned in the introduction, there is a trivial reduction from the scheduling on unrelated machines problem to the OR-version of the min-max multicriteria global minimum cut problem. Known hardness results for the scheduling problem (see Lenstra et al. [14]) then imply the following: Theorem 8. The OR-version of the min-max multicriteria global minimum cut problem is NP-hard even for just two criteria. The problem with a non-fixed number of criteria cannot be approximated to within a ratio better than 3/2, unless P=NP. The scheduling problem on a fixed number of unrelated machines can however be solved in pseudo-polynomial time. Horowitz and Sahni [9] present a simple branch-and-bound pseudo-polynomial algorithm for that problem which runs in time, where is the number of jobs, is the number of machines, and M is the optimal makespan. This immediately implies: Theorem 9. Let G = (V, E) be an undirected graph with integral weight functions defined on it edges. Let C be a cut in G. Then, a choice function which minimizes can be found in pseudo-polynomial time. Jansen and Porkolab [10] obtained an FPTAS for the unrelated machines scheduling problem, which runs in time. It can be used instead of the exact algorithm of [9] when approximate solutions are acceptable.
3.2
The Min-max Version
We show that the simple algorithm given in Figure 2, which is a variant of the algorithm given in Figure 1, solves the OR-version of the min-max problem in pseudo-polynomial time, for any fixed number of criteria. Theorem 10. The OR-version of the min-max problem with integer edge weights can be solved in where M is the optimal min-max value.
global minimum cut time,
Proof. We begin again with the correctness proof. Let C be an optimal min-max cut and let be the corresponding optimal choice function. Let D be any other
Multicriteria Global Minimum Cuts
73
Fig. 2. A pseudo-polynomial time algorithm for the min-max version of the global minimum cut problem
cut. We show that To see that, we let which if
where for every
for every be a choice function for Then,
The second inequality follows as is an optimal solution of the min-max problem. We next consider the complexity of the algorithm. The cuts with respect to can be found again in time using the algorithm of Nagamochi et al. [16]. For each one of the approximate cuts produced, we find an optimal choice function using the algorithm of Horowitz and Sahni [9]. The total running time is then where M is the value of the optimal solution. Theorem 11. The OR-version of the min-max problem, with fixed, admits an FPTAS.
global minimum cut
Proof. The proof is identical to the proof of Theorem 10 with the exact algorithm of Horowitz and Sahni [9] replaced by the FPTAS of Jansen and Porkolab [10]. As in Section 2, we can use the algorithm for the min-max version of the problem to solve the decision and optimization versions of the problem. We omit the obvious details.
3.3
A Case That Can be Solved in Polynomial Time
We now discuss a restriction of the min-max problem that can be solved in strongly polynomial time. For simplicity, we consider the bicriteria problem. Theorem 12. Instances of the OR-version of the min-max bicriteria global minimum cut problem in which one of the weight functions assumes only different values can be solved in time.
74
A. Armon and U. Zwick
Proof. Assume, without loss of generality, that assumes only different real values Let for Consider an optimal min-max cut C and an optimal choice function for it. It is easy to see that for every there is a threshold such that if then if and only if (Indeed, if there are two edges such that and then the choice function which reverses the choices of on and is a better choice function. We assume here, for simplicity, that all weights are distinct.) As there are at most essentially different thresholds for each set the total number of choice functions that should be considered is only With a given choice function the problem reduces to an AND-version of the problem with the weights if and otherwise, for As each such problem can be solved in time, the total running time of the resulting algorithm is
4
OR-Versions of Other Multicriteria Problems
In this section we consider the OR-versions of the bicriteria shortest path and minimum spanning tree problems. Our results can probably be extended to any fixed number of criteria.
4.1 Shortest Paths The input to the problem is a directed graph G = (V, E) with two weight functions defined on its edges, two vertices and two bounds The question is whether there is a path P from to in the graph and a choice function such that and (Recall the subway example given in the introduction.) It is easy to see, using a simple reduction from the scheduling on unrelated machines problem, that the OR-version of the bicriteria shortest path problem is NP-hard. We show, however, that it can be solved in pseudo-polynomial time. A FPTAS for the problem is easily obtained by scaling. Theorem 13. The OR-version of the bicriteria shortest path decision problem with integer edge lengths can be solved in time, where Proof. The OR-version of the problem can be easily reduced to the AND-version of the problem by replacing each edge having a weight vector by two parallel edges and having weight vectors and The standard, AND-version, of the problem can be solved using an algorithm of Hansen [7] within the claimed time bound.
4.2 Minimum Spanning Trees Next we consider the OR-version of the bicriteria minimum spanning tree problem. The input is an undirected graph G = (V, E), two weight functions
Multicriteria Global Minimum Cuts
and two bounds and ning tree T and a choice function
75
The question is whether there exist a spansuch that and
The OR-version of the bicriteria minimum spanning tree problem is again easily seen to be NP-hard. We provide a polynomial time algorithm for a special case of the problem, and a pseudo-polynomial time algorithm for the general case. Theorem 14. The OR-version of the minimum spanning tree problem in which one of the weight functions is constant, i.e., for every can be solved by solving a single standard minimum spanning tree problem. Proof. We simply solve the standard minimum spanning tree problem with respect to the weight function and obtain a minimum spanning tree T . For the heaviest edges of T we choose to pay the cost, and for all the others we pay the cost. The correctness of this procedure follows from the well known fact that if the weights of the edges of T are and if is any other spanning tree of the graph G with edge weights then for Theorem 15. The OR-version of the bicriteria minimum spanning tree decision problem with integer edge lengths can be solved in time. Proof. The OR-version of the problem can be easily reduced to the AND-version of the problem by replacing each edge having a weight vector by two parallel edges and having weight vectors and The standard, AND-version, of the problem can be solved using an algorithm of Hong et al. [8] within the claimed time bound.
5
Concluding Remarks
We showed that the standard (i.e., the AND-version) multicriteria global minimum cut problem can be solved in polynomial time for any fixed number of criteria. The running time of our algorithm, which is is fairly high, even for a small number of criteria. Improving this running time is an interesting open problem. We also considered the OR-version of the problem and showed that it is NP-hard even for just two criteria. It can be solved, however, in pseudo-polynomial time, and it also admits an FPTAS, for any fixed number of criteria. Finally, we considered the OR-versions of the bicriteria shortest path and minimum spanning tree problems, and showed that both of them are NPhard but can be solved in pseudo-polynomial time. It will also be interesting to study OR-versions of other multicriteria optimization problems.
76
A. Armon and U. Zwick
References 1. M. Bruglieri, M. Ehrgott, and H.W. Hamacher. Some complexity results for kcardinality minimum cut problems. Technical Report 69/2000, Wirtschaftsmathematik, University of Kaiserslautern, 2000. 2. M. Bruglieri, F. Maffioli, and M. Ehrgott. Cardinality constrained minimum cut problems: Complexity and algorithms. Discrete Applied Mathematics, 137(3):311– 341, 2004. 3. J. Climacao. Multicriteria Analysis. Springer-Verlag, 1997. 4. M. Ehrgott. Multicriteria optimization. Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, 2000. 5. M. R. Garey and D. S. Johnson. Computers and Intractability – A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979. 6. R.E. Gomory and T. C. Hu. Multiterminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961. 7. P. Hansen. Bicriterion path problems. In G. Fandel and T. Gal, editors, Multiple Criteria Decision Making: Theory and Applications, LNEMS 177, pages 109–127. Springer-Verlag, Berlin, 1980. 8. S.P. Hong, S.J. Chung, and B.H. Park. A fully-polynomial bicriteria approximation scheme for the constrained minimum spanning tree problem. Operations Research Letters, 32(3):233–239, 2004. 9. E. Horowitz and S. Sahni. Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23:317–327, 1976. 10. K. Jansen and L. Porkolab. Improved approximation schemes for scheduling unrelated parallel machines. In Proceedings of the thirty-first annual ACM Symposium on Theory of Computing, pages 408–417, 1999. 11. D. R. Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24(2):383–413, 1999. 12. D. R. Karger. Minimum cuts in near-linear time. Journal of the ACM, 47(1):46–76, 2000. 13. D. R. Karger and C. Stein. A new approach to the minimum cut problem. Journal of the ACM, 43(4):601–640, 1996. 14. J.K. Lenstra, D.B. Shmoys, and E. Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46:259–271, 1990. 15. H. Nagamochi and T. Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SI AM Journal on Discrete Mathematics, 5(1):54–66, 1992. 16. H. Nagamochi, K. Nishimura, and T. Ibaraki. Computing all small cuts in an undirected network. SI AM J, Discrete Mathematics, 10(3):469–481, 1997. 17. C. H. Papadimitriou and M. Yannakakis. On the approximability of trade-offs and optimal access of web sources. In IEEE Symposium on Foundations of Computer Science, pages 86–92, 2000. 18. K. Schloegel, G. Karypis, and V. Kumar. A new algorithm for multi-objective graph partitioning. In European Conference on Parallel Processing, pages 322– 331, 1999. 19. M. Stoer and F. Wagner. A simple min-cut algorithm. Journal of the ACM, 44(4):585–591, 1997.
Polyline Fitting of Planar Points Under Min-Sum Criteria Boris Aronov1,*, Tetsuo Asano2,**, Naoki Katoh3, Kurt Mehlhorn4, and Takeshi Tokuyama5 1
Polytechnic University
[email protected] 2
Japan Advanced Institute of Science and Technology
[email protected] 3
Kyoto University
[email protected] 4
Max-Planck-Institut für Informatik
[email protected] 5
Tohoku University
[email protected]
Abstract. Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with joints under the min-sum criteria with respect to and metrics, which are more appropriate measures than uniform and Hausdorff metrics in statistical context. We present efficient algorithms for the 1-joint versions of the problem, and fully polynomial-time approximation schemes for the general versions.
1
Introduction
Curve fitting aims to approximate a given set of points in the plane by a curve of a certain type. This is a fundamental problem in statistics, and has numerous applications. In particular, it is a basic operation in regression analysis. Linear regression approximates a point set by a line, while non-linear regression approximates it by a non-linear function from a given family. In this paper, we consider the case where the points are fitted by a polygonal curve (polyline) with joints, see Figure 1. This is often referred to as polygonal approximation or polygonal fitting problem. It is used widely. For example, it is commonly employed in scientific and business analysis to represent a data set by a polyline with a small number of joints. The best representation is the polyline minimizing the error of approximation. Error is either defined as the maximum (vertical) distance of any * **
Work of B.A. on this paper was supported in part by NSF ITR Grant CCR-00-81964. Part of the work was carried out while B.A. was visiting JAIST. Work of T.A. was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (B).
R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 77–88, 2004. © Springer-Verlag Berlin Heidelberg 2004
78
B. Aronov et al.
Fig. 1. A 4-joint polyline fitting a set of points
input point from the polyline (min-max-optimization) or the sum of vertical distances (min-sum-approximation). In either case, distance is measured in some norm. We follow common practice and restrict ourselves to norms and In this paper, we focus on the and problems when the desired curve is a polyline; in other words, it is a continuous piecewise-linear curve with linear components. We assume that a coordinate system is fixed, and the input points are sorted with respect to their values. To the authors’ knowledge, the computational complexity of the optimal problem under either of these minimization criteria has not been previously investigated. More specifically, it seems that an efficient solution of the problem extending the result of Imai et al. [8] is theoretically challenging even for the 1-joint problem. In this paper, we begin by considering the 1-joint problem. We give algorithms of complexity and time for the and criteria, respectively.1 The fitting algorithm is simple and practical, whereas the algorithm depends on using a semi-dynamic range search data structure and parametric search. For general we present two approximation schemes. Let be the minimum fitting error for a polyline and let be a positive constant. We give a polynomial-time approximation scheme (PTAS) to compute a fitting whose error is at most and we describe a fully polynomial-time approximation scheme (FPTAS) to compute a polyline with fitting error, and consequently show that the problems cannot be strongly NP-hard, although their NP-hardness remains open.
2
Preliminaries
A polyline is an alternating sequence of line segments (links) and joint vertices (joints), where and share the endpoint for and and are infinite rays. We denote the link on line by if the interval of the values of corresponding to the link is understood. A joint is represented by the pair of its coordinate values. Thus, 1
We write
if there exists an absolute constant
such that
Polyline Fitting of Planar Points Under Min-Sum Criteria
79
the connectivity and monotonicity of the polyline can be guaranteed by requiring that for and We now formulate the problem of fitting a polyline to an set. Given a set of points with and an integer and setting and for convenience, find a polyline minimizing one of the following three quantities for and uniform metric fitting, respectively:
For the problems are linear regression problems.The regression is well known as the Gaussian least-squares method. Once we compute and in linear time, we can construct an optimal fitting line by considering the partial derivatives of the objective function and solving a 2 × 2 system of linear equations. The linear regression problem with respect to the uniform error is to find a pair of parallel lines at the minimum vertical distance that contain all the given points between them. This can be done by applying the rotating caliper method that computes antipodal pairs of points on the convex hull of the point set. For an point set this can be done in time [15]. The regression problem is more involved; however, a linear-time algorithm has been devised by Imai et al. [8] based on Megiddo’s prune-and-search paradigm.
3
Fitting a 1-Joint Polyline
We consider the problem of fitting a 1-joint polyline to a set of points. We proceed in two steps. We first assume that the joint vertex lies in a fixed interval and later eliminate this assumption. Let and Our objective polyline consists of two links lying on lines and respectively. We call a tuple feasible if the two lines and meet at a point whose lies in the interval Our goal here is to find a feasible tuple representing a 1-joint polyline minimizing
80
B. Aronov et al.
for and minimizing
respectively. Minimizing (4) is equivalent to, provided subject to
where the last line represents the feasibility condition. Lemma 1. For either or criterion, the 1-joint problem for a fixed reduces to solving two convex programming problems. We omit the proof due to space limitations. From the above lemma, it is clear that the optimal 1-joint polyline can be computed by using linear/quadratic programming. However, we aim to design combinatorial algorithms for these problems. Indeed, we can classify the solution into two types: (1) The joint is either on the line or (2) The joint lies strictly in the interior of the interval We call the solution fixed in the former case and free otherwise. We now have the following simple observation. Lemma 2. If the solution is fixed, the joint is located on either of the two vertical lines If the joint is on the line
we can regard it as a solution for the partition into and Thus, for each partition, we essentially need to solve two subproblems: (1) the free problem and (2) the fixed problem where the joint is on the vertical line This leads to the following generic algorithm: For each partition of S into two intervals and we first consider the free problem ignoring the feasibility constraint, and check whether the resulting solution is feasible or not, i.e., we verify that the intersection point lies in the strip between and If it is feasible, it is the best solution for the partition. Otherwise, we consider the fixed solution adding the constraint that the joint lie on and report the solution for the partition. After processing all possible partitions, we report the solution with the smallest error. If it takes time to process a subproblem for each partition, the total time complexity is For efficiency, we design a dynamic algorithm to process each partition so that is reduced in the amortized sense.
3.1
The
1-Joint Problem
We show how to construct an optimal 1 -joint polyline in linear time. We process the partitions starting from to in order. We maintain the sums, variances, and covariances and incrementally, at constant amortized cost. They also provide us with the corresponding values for if we precompute those values for S, i.e., etc.
Polyline Fitting of Planar Points Under Min-Sum Criteria
81
For the free case, the objective function is separable, in the sense that the optimal solution can be identified by finding minimizing and minimizing independently. Each can be computed in O(1) time from the values of as explained in section 2. The feasibility check of the solution is done in O(1) time by computing the intersection point of the corresponding pair of lines. It remains to solve the subproblems with the additional constraint that the joint is at Put
so that
is the function to be minimized and the joint constraint can be expressed as Now, a standard Lagrange multiplier method solves the problem, and we have a linear equation whose coefficients can be expressed in terms of Thus, we have the following Theorem 1.
3.2
The
1–joint fitting can be computed in linear time. 1-Joint Problem
Semi-dynamic Linear Regression. We start with the problem of computing the optimal linear (i.e., linear regression) of the input point set, i.e., we seek the line minimizing The difficulty with the problem is that, written in linear programming terms (as in (6)), it has variables, in contrast to the least-squares case where the problem is directly solved as a bivariate problem. Nonetheless, Imai et al. [8] devised an optimal linear-time algorithm for computing based on the multidimensional pruneand-search paradigm using the fact that the optimal line bisects the point set. In order to design an efficient algorithm for the 1-joint fitting problem, we consider a semi-dynamic version of the linear regression for a point set P with low amortized time complexity, where we dynamically maintain P with insertions and deletions under an assumption that P is always a subset of a fixed universe S of size that is given from the outset. (In fact, for our application, it is sufficient to be able to start with and handle only insertions, and to start with P = S and handle only deletions. Moreover, the order of insertions and deletions is known in advance. The data structure we describe below is more general.) Consider the dual space, with transformed to the dual line where The line is transformed to the point in the dual space. The kth level of the arrangement of the set S* of dual lines is the trajectory of the kth largest value among We call the level the median level. 2
We use an asterisk to denote geometric dual of a point, line, or a set of lines/points.
82
B. Aronov et al.
Lemma 3 (Imai et al. [8]). If the optimal its dual point is on the median level if and the level if is even.
line is given by is odd, and between the
level
Now, given X-value consider the point for each and let be the sum of the largest values in and be the sum of the smallest values in the same set. Put gives the fitting error of the dual line of any point on the median level (or between the two median levels if is even). Thus, by Lemma 3, is minimized at Lemma 4. is also convex. positive at
is a convex function, while has either slope 0 at
is concave. As a consequence, or its slope changes from negative to
Proof. The convexity follows directly from the fact that, in any line arrangement, the portions of the lines lying on or below (resp. on or above) any fixed level can be decomposed into non-overlapping concave (resp. convex) chains; see, for example, [2]. Suppose a fixed universe S* of lines is given. We need a data structure that maintains a subset and supports the following operations: Median-Location Query. For a query value return the point on the highest line at Slope-Sum Query. For a query point return the sum of the slopes of lines below at Height-Sum Query. For a query value return the sum of the Y -coordinates of the lines below at The height-sum query reduces to a slope-sum query plus a constant-term-sum query. Update. A line in S* is added to or removed from P*. Suppose a data structure supporting such queries on a set of lines in time is available, where Then we can query the slopes of F and G at and hence compute the slope of H at in time. Because of convexity of H, we have the following: Lemma 5. Given time.
we can decide whether
Thus, we can perform binary search to find search strongly polynomial. Once we know location query at
in We show below how to make this we determine by the median-
Semi-dynamic Data Structure for the Queries. We show how to realize semi-dynamic median-location query and sum-queries. As a preliminary step, we describe a semidynamic data structure for vertical ray queries, i.e., queries of the form: Given a vertical upward ray starting at determine the number of lines in P* intersected by the ray, the sum of their slopes, and the sum of their constant terms. A dual line is above iff the primal point is above the line Thus our problems
Polyline Fitting of Planar Points Under Min-Sum Criteria
83
reduce to half-space queries in the primal plane. We use the partition-tree data structure of Matoušek [3,11,13]. It supports half-space queries on sets with points in time linear space, and preprocessing time We build a partition tree on the set S of points dual to the lines in S* (in fact, these are the points to which a line is being fitted). A standard construction proceeds as follows: With each node of the partition tree we associate a point set and a triangle where at any node other than the root and at the root. In addition we also store at v the size of and the sums and of the slopes and constant terms of the corresponding dual lines. Since the point sets over all children of a node in the tree, by definition of a partition tree, partition the set and is at most a fraction of this tree has linear size and logarithmic depth. For our purposes, we modify the partition tree to obtain a new tree where the same as in is associated with every node but stores and instead of the corresponding values for This data structure enables us to execute the half-plane range query in P, and thus the vertical ray query in P*. Our data structure is semi-dynamic. When P changes, with a point being added or removed, what we need to update is just values and for each node where is relevant. Since the sets for all nodes at a fixed level of the partition tree form a partition of S, only one node must be updated at each level; to facilitate the update one might associate with each point a list of length containing the nodes of the tree with Thus, the update can be performed in time. This ends the description of the semi-dynamic vertical ray query data structure. Our sum-queries can be done by using the vertical ray query. We next turn to the median-location query data structure. For a given let be the intersection of the vertical line and the median level of the dual arrangement We can use the vertical query data structure to compare any given with We perform a vertical ray query to find the number of lines above If it is less than otherwise This suggests computing by some kind of binary search. If we had the sorted list of intersections between the vertical line and the lines in S* available, we could perform a binary search on L by using ray queries. However, it takes time to compute the list, which is too expensive since we aim for a sublinear query time. Instead, we construct a data structure which can simulate the binary search without explicitly computing the sorted list. Lemma 6. We can construct a randomized data structure in time such that, given we can compute in time. The query time bound holds for every vertical line with high probability. Proof. We fix a small constant and randomly select lines from to have a set of lines, where is a suitable constant. From the results of Clarkson and Shor [5], if the constant is sufficiently large, with high probability every vertical segment intersecting no line of intersects at most lines of S*. In other words, is the dual of an of S. Similarly, we construct from such that is an of if Thus, we have a filtration
84
B. Aronov et al.
and The number of layers is a function of and only, so the construction takes time. Additionally, we construct a dual range-searching data structure for such that for a query vertical interval I we can report all lines in meeting I in time, where K is the number of reported lines. In primal space a vertical interval corresponds to a strip bounded by two parallel lines and hence we may use partition trees as described above to implement reporting queries. The preprocessing time is Now, our algorithm for finding is as follows: Given we first compute all the intersections between and the lines of sort them, and perform binary search for on them. Each step of the search requires a vertical ray query and hence time As the result of the binary search, we obtain a vertical interval I containing such that no line of crosses the interior of I. By using the dual range-searching data structure, we extract, in time the set of K lines in intersecting I; with high probability. Proceeding recursively, we obtain since at the last level of the filtration we arrive at an interval containing with no line of crossing its interior. The total time is At this point, we have a realization of the semi-dynamic query data structure, i.e., We finally come to the strongly polynomial method for determining We use parametric search [16]. We use a parallel version of the ray-query algorithm, i.e., the parallel traversal of the partition tree, for the guide algorithm (see [9]). Since the depth of a partition tree is the parallel time complexity of the ray query is Thus, the parallel time complexity of sum queries is using processors. Therefore, using standard parametric search paradigm, we can compute the optimal linear fitting in We remark that we do not employ parametric search to compute for a fixed since it is not always possible to use it in a nested fashion, and there are technical difficulties in applying multi-dimensional parametric search paradigm [14] to our problem. To speed up the query time and thus the overall algorithm, we generalize the data structure to allow it to use super-linear storage based on Matoušek’s construction [12]. If we can use space for we first select points from S and construct a dual cutting, i.e., a decomposition of the dual plane into cells, such that each cell C is intersected by at most lines dual to points of S; the number of cells required is and the computation time is Let S(C) be the set of lines intersecting C. We construct a point-location data structure on the cutting. For each cell C, we store the cumulative statistics (the sum of slopes etc.) for the set of lines passing below C, and construct the partition tree for S(C). The query time of each tree is When P changes, we need to update the data stored in each of the cells of the arrangement, and also the partition trees corresponding to sets containing the updated point. Thus, update time is Update time can be sped up by not storing the statistics for each cell explicitly, but rather retrieving them when needed at a cost of This reduces the time needed for an update to and the total time of all updates to we omit the details in this version. If we set the update time and query time are both The space and preprocessing time is The parallel time complexity is not affected by the space-time trade-off.
Polyline Fitting of Planar Points Under Min-Sum Criteria
85
Algorithm for 1-Joint Fitting. Finally, we describe the algorithm to find the 1-joint polyline fitting a set S of points in the plane. Recall that there are two different types of solutions: Type 1. There is an index such that the 1-joint polyline consists of the optimal fitting line of and that of Type 2. There is an index such that the joint lies on the vertical line If the optimal solution is of type 1, we compute an optimal line for and separately, for every by using the semi-dynamic algorithm with S as the universe. If we use quasi-linear space the time complexity is and if we use space, the time complexity is Otherwise, the optimal solution is of type 2. For each we guess the value of the joint vertex Then, we can compute the best line, in the sense of fitting, approximating going through the (for now, fixed) joint by using almost the same strategy as in section 3.2. Indeed, it suffices to determine the slope of this line. In the dual space, we just need to compute a point on the line such that is minimized. We observe that the above function is convex if it is regarded as a function of and hence is monotone and changes the sign at where is the sum of slopes of lines above (resp. below Thus, we can apply binary search by using slope-sum query, and this binary search can be performed in steps by using the filtration as described in Lemma 6. Moreover, because of the convexity of the objective function, once we know the optimal solution for a given we can determine whether the global optimal value is greater than or not by using the height-sum query. Indeed, when we infinitesimally slide the gain (or loss) of the objective function can computed from the slope sums and height sums of dual lines associated with each of the sets of points lying above, below, and on the current polyline (for each of and Thus, we can apply binary search for computing the optimal value of In order to construct a strongly polynomial algorithm, we apply parametric search. Note that given our algorithm has a natural parallel structure inherited from the range-searching algorithms, and runs in polylogarithmic time using processors. Thus, the parallel search paradigm [16] is applicable here. Therefore, for a fixed the second case of the problem can be handled in time. Thus, we have the following: Theorem 2. The optimal 1-joint polyline is computed in time using quasi-linear space, and randomized time using
4
Fitting a
randomized space.
Polyline
The fitting problem is polynomial-time solvable if is a fixed constant. We describe the algorithm in a non-deterministic fashion. We guess the partition of into intervals each of which corresponds to a line segment in the polyline. Also, we guess whether each joint is free or fixed. We decompose the problem at the free joints
86
B. Aronov et al.
and have a set of subproblems. In each subproblem, we add the linear constraints corresponding to the fixed condition (i.e., each joint is located on a guessed vertical line). Thus, each subproblem is a convex programming problem: a linear program for and a quadratic program for We solve each subproblem separately to obtain the solution of the whole problem. Note that this strategy works because of the convexity of each subproblem. There are different choices of the guesses, thus we can be replace guessing by a brute-force search to have a polynomial-time deterministic algorithm if is a constant. For a general we do not know whether the problem is in the class P or not. Thus, we would like to consider approximation algorithms. One possible approach is to relax the requirement that number of joints be exactly We can design a PTAS for it. Theorem3. Let be the optimal constant we can compute a polynomial time.
(or
error of a fitting. Then, for any fitting whose error is at most in
Proof. We ignore continuity and approximate the points by using a piecewise-linear (not necessarily continuous) function with linear pieces. This can be done by preparing the optimal linear regression for each subinterval of consecutive points of S, and then applying dynamic programming. We can restore the continuity by inserting at most steep (nearly vertical) line segments. The resulting polyline has at most joints and error at most We can improve to by applying the 1-joint algorithm instead of linear regression algorithm, and further improve it to by using the algorithm mentioned above for Another approach is to keep the number of joints at and approximate the fitting error. We give a FPTAS for it. We only discuss the case, since the case is analogous. Let be the optimal and we aim to find a polyline whose error is at most We remark that if our solution is exactly the same as the solution for the uniform metric fitting problem, and thus we may assume Recall that the uniform metric fitting problem can be solved in time [6]. The following is a trivial but crucial observation: Lemma 7. Let Then,
be the optimal error for the uniform metric
fitting problem.
Proof. The sum of the errors in the uniform-metric–optimal polyline is at most Hence On the other hand, every polyline has a data point in S such that the vertical distance to the polyline is at least so Our strategy is as follows: We call the vertical lines through our input points the column lines. We give a set of portal points on each column line, and call a polyline a tame polyline if each of its links satisfies the condition that the line containing the link goes through a pair of portal points. On each column line, the distance between its data point and the intersection point with the optimal polyline is at most thus at most Thus, on the column line, we place the portals in the vertical range The portal points are placed symmetrically above and below The jth portal above is located at the
Polyline Fitting of Planar Points Under Min-Sum Criteria
satisfying at heights 2M + 3.
and
87
where and We choose the largest M and hence We also put portals In this way the number of portals in any column is at most
Lemma 8. There exists a tame polyline whose
error is at most
We omit the proof of above lemma in this version. Thus, it suffices to compute the optimal tame polyline. There are portals, and thus lines going through a pair of portals. Let be the set of these lines. We design a dynamic programming algorithm. For the ith column, for each line and each we record the approximation error of the best tame polyline up to the current column whose (rightmost) link covering is on When we proceed to the column, each approximation error is updated. We omit the details of the analysis in this version, and only show the result. Theorem 4. An optimal, for each of the time.
5
and
i.e., a polyline with error problems can be computed in
times the
Concluding Remarks
A major open problem is to determine the complexity class of the problem for and The corresponding or polyline approximation problem where the input is a curve is also interesting. Acknowledgment: The authors would like to thank Jirí Matoušek for a stimulating discussion on convexity.
References 1. A. Aggarwal, B. Schieber, and T. Tokuyama, “Finding a minimum-weight path in graphs with the concave Monge property and applications,” Discrete Comput. Geom., 12 (1994) 263–280. 2. P. Agarwal, B. Aronov, T. Chan, M. Sharir, “On Levels in Arrangements of Lines, Segments, Planes, and Triangles,” Discrete Comput. Geom., 19 (1998) 315–331. 3. P. Agarwal and J. Matoušek, “Ray shooting and parametric search,” SIAM J. Comput., 22 (1993) 794–806. 4. J. Chun, K. Sadakane, and T. Tokuyama, “Linear time algorithm for approximating a curve by a single-peaked curve,” Proc. 14th Internat. Symp. Algorithms Comput. (ISAAC 2003), LNCS 2906, 2003, pp. 6–16. 5. K. L. Clarkson and P. W. Shor, “Application of Random Sampling in Computational Geometry,” Discrete Comput. Geom., 4 (1989) 423–432. 6. M. Goodrich, “Efficient piecewise-linear function approximation using the uniform metric,” Discrete Comput. Geom., 14 (1995) 445–462.
88
B. Aronov et al.
7. S. Hakimi and E. Schmeichel, “Fitting polygonal functions to a set of points in the plane,” Graphical Models and Image Processing, 53 (1991) 132–136. approximation of 8. H. Imai, K. Kato, and P. Yamamoto: “A linear-time algorithm for linear points,” Algorithmica, 4 (1989) 77–96. 9. N. Katoh and T. Tokuyama, “Notes on computing peaks in k-levels and parametric spanning trees,” Proc. 17th ACM Symp. on Computational Geometry, 2001, pp. 241–248. 10. S. Langerman and W. Steiger, “Optimization in arrangements.” Proc. Symp. Theor. Aspects Computer Science (STACS2003), LNCS 2607, 2003, pp. 50–61. 11. J. Matoušek, “Efficient partition trees,” Discrete Comput. Geom., 8 (1992) 315–334. 12. J. Matoušek, “Range searching with efficient hierarchical cutting,” Proc. 8th ACM Symp. on Comput. Geom., (1992) 276–287. 13. J. Matoušek, “Geometric range searching,” ACM Computing Surveys, 26 (1994) 421–461. 14. J. Matoušek and O. Schwarzkopf, “Linear optimization queries,” Proc. 8th Annual ACM Symp. Comput. Geom., 1992, pp. 16–25. 15. F. P. Preparata and M. I. Shamos, Computational Geometry, an Introduction, Springer-Verlag, New York, 1985. 16. J. Salowe, “Parametric Search,” Chapter 37 of Handbook of Discrete and Computational Geometry (eds. J. Goodman and J. O’Rourke), CRC Press, 1997.
A Generalization of Magic Squares with Applications to Digital Halftoning Boris Aronov1,*, Tetsuo Asano2,**, Yosuke Kikuchi3, Subhas C. Nandy4, Shinji Sasahara5, and Takeaki Uno6 1
Polytechnic University, Brooklyn, NY 11201-3840, USA http://cis.poly.edu/~aronov 2
JAIST, Tatsunokuchi, 923-1292 Japan
[email protected]
3
ERATO QCI Project, JST, Tokyo 113-0033, Japan
4
Indian Statistical Institute, Kolkata 700 108, India
5
Fuji Xerox Co., Ltd., Kanagawa 259-0157, Japan
[email protected] [email protected] [email protected] 6
National Institute of Informatics (NII), Tokyo, 101-8430 Japan
[email protected]
Abstract. A semimagic square of order is an matrix containing the integers arranged in such a way that each row and column add up to the same value. We generalize this notion to that of a zero matrix by replacing the requirement that the sum of each row and each column be the same by that of requiring that the sum of the entries in each square contiguous submatrix be the same. We show that such matrices exist if and are both even, and do not if and are are relatively prime. Further, the existence is also guaranteed whenever for some integers We present a space-efficient algorithm for constructing such a matrix. Another class that we call constant-gap matrices arises in this construction. We give a characterization of such matrices. An application to digital halftoning is also mentioned.
1
Introduction
A semimagic square is an matrix filled with the numbers in such a way that the sum of the numbers in each row and each column are the same. Magic squares and related classes of integer matrices have been studied extensively (for an exhaustive bibliography, see [8] and the references therein). This paper generalizes the notion of a semimagic square by replacing the requirement that all row and column sums be the same by the analogous requirement for all contiguoussquare submatrices; we call such matrices zero matrices of order Let be the set of all such matrices. In this paper we prove * **
Part of the work on the paper has been carried out when B.A. was visiting JAIST. Work of B.A. on this paper was supported in part by NSF ITR Grant CCR-00-81964. Work of T. A. was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (B).
R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 89–100, 2004. © Springer-Verlag Berlin Heidelberg 2004
90
B. Aronov et al.
that is non-empty if and are both even, and empty if they are relatively prime. Further, we show by an explicit construction that for any integers Another property plays an important role in the latter construction of zero discrepancy matrices. A characterization of matrices with this property is also given in this paper. Our investigation is motivated by an application described below, but intuitively we seek a matrix filled with distinct integers in an as uniform a manner as possible. The analogous geometric problem of distributing points uniformly in a unit square has been studied extensively in the literature [6,12]. Usually, a family of regions is introduced to evaluate the uniformity of a point distribution. If the points of an set P are uniformly distributed, for any region R in the family the number of points in R should be close to where is the point density of P in the entire square. Thus, the discrepancy of P in a region R is defined as the difference between this value and the actual number of points of P in R. The discrepancy of the point distribution P with respect to the family of regions is defined by the maximum such difference, over all regions. The problem of establishing discrepancy bounds for various classes of regions has been studied extensively [10]. One of the simplest families is that of axis-parallel rectangles for which bound is known [6,12]. In the context of digital halftoning, a family of axis-parallel squares (contiguous square submatrices) over a matrix is appropriate for measuring the uniformity since human eye perception is usually modeled using weighted sum of intensity levels with Gaussian coefficients over square regions around each pixel [3]. Thus, the matrices discussed in this paper can be used as dither matrices in which integers are arranged in an apparently random manner to be used as variable thresholds. Small matrix size tends to generate visible artifacts. In this sense the dither matrix of size 8 × 8 designed by Floyd and Steinberg [7] may be too small. A common way to construct a larger dither matrix is to use local search under some criterion based on spatial frequency distribution of the resulting matrix. Such dither matrices are called blue-noise masks [13, 15, 16, 17]. One disadvantage of a blue-noise mask is its high space complexity. There appears to be no way to avoid storing the entire matrix. The zero matrices of order we construct, on the other hand, are such that we can generate any one element by a simple integer calculation requiring only seed matrices, each of size
2
Problem Statement
Generalizing the notion of a semimagic square, we consider an matrix containing all the integers such that the entries contained in every contiguous submatrix add up to the same value. More formally, for integers let be the class of all integer matrices with entries from the set and let be the set of those matrices which contain every value exactly once. A contiguous submatrix (or region, hereafter) with its upper left corner at is defined by
A Generalization of Magic Squares with Applications to Digital Halftoning
91
where indices are calculated modulo 1 Given a matrix P and a region of size denotes the sum of the elements of P in locations given by Analogously, define a to be the region of a matrix starting at and to be the sum of elements of P in the locations given by We are interested in all regions in an matrix:
The
of an
matrix P for the family
is defined as
In this paper we focus on the existence of matrices with In other words, we are interested in the existence and construction of matrices in all of whose contiguous submatrices have equal sums. Let be the set of all such matrices of order Theorem 1. The set following properties: (a) (b) (c) (d)
of
matrices of order
has the
is non-empty if and are both even. is empty if and are relatively prime. is empty if is odd and is even. is non-empty for any integers and
Proof (Theorem 1, parts (a)–(c)). To prove part (a), it suffices to show if is even since any region can be partitioned into 2 × 2 regions if is even. (More generally, if divides Let be the matrix in which the numbers are arranged in the rowmajor order, that is, We classify matrix elements by their parity and rotate all the elements of odd parity by 180 degrees, i.e., for every with odd, we swap and It is easily checked that the sum of elements in any 2 × 2 region is always An example for is shown in Fig. 1.
Fig. 1. Parity rotation used in the proof of Theorem 1(a)
Turning to part (b), for a contradiction, assume that there exists a matrix in which the sum of elements of P over a region is independent of 1
Throughout this paper, index arithmetic is performed modulo matrix dimensions unless otherwise noted.
92
B. Aronov et al.
In particular,
for some constant c and therefore for all Since and are relatively prime, the last relation implies that in fact is independent of Similar reasoning leads to the conclusion that it is independent of as well. In particular, and therefore, by definition of and we must have contradicting our assumption that all the elements of P are distinct. Finally, we consider part (c) of Theorem 1. Let and let be odd and be even. For a contradiction, assume that the values in any region add up to the same number, say S, which must clearly be an integer. Summing over all and and observing that every entry in P appears precisely times in these sums, we conclude that
and therefore which cannot be an integer if This contradiction concludes the proof of Theorem 1(a)–(c).
3
Construction of a
is even and
is odd.
of Zero
In this section we finish the proof of Theorem 1 by designing a matrix from for any positive integer such that its is zero; in fact we present a proof of a stronger statement, see Theorem 3. We first show that there exists a matrix in whose discrepancy is zero, and then extend the result to matrices. Definition 1. The simple expansion repeating P times, as follows:
Note that the set of numbers.
of
of a
matrix P is the matrix formed by
is zero, as every
region contains the same
Definition 2. A cyclic column shift of a matrix P is the matrix obtained by shifting each column of P to the right (i.e., shifting the jth column to the column) and moving the last column to the first column. A cyclic row shift is similarly defined: It means shifting each row of P down to the next lower row (i.e., shifting ith row to the row) and moving the bottom row to the top row. We denote the matrix obtained by applying cyclic column shift times and cyclic row shift times to a matrix P by That is, element in P moves to position in The cyclic expansion of a matrix P is a matrix defined by
A Generalization of Magic Squares with Applications to Digital Halftoning
An easy calculation shows that, for all
Definition 3. A constant-gap matrix
holds for all choices of
93
with
is one for which
and
Intuitively, this means that for any two columns and the gap between elements in the same row is independent of the row, hence the “constant gap” name. Since (2) can be rewritten as
rows and columns play symmetric roles in the definition. Moreover, a constant-gap matrix has the strong Monge property [1] since the sum of the main diagonal elements is equal to that of the off diagonal elements in any 2 × 2 submatrix. Lemma 1. The constant-gap property is preserved (1) under exchange of any two rows, (2) under exchange of any two columns, and, for square matrices, (3) under mirror reflection across the main diagonal. Proof. Immediate from the definition. The following lemma is a key to our construction of zero discrepancy matrices. Lemma 2. If P is a expansion is zero.
constant-gap matrix, the
of its cyclic
Proof. Recall that and denote and contiguous submatrices of and and the sums of the corresponding elements in respectively. We aim to prove for all Together with which is proven by a symmetric argument, this implies the statement of the theorem. By definition, recall that all indices in are calculated modulo Put and To prove we compare the two columns. As illustrated in Fig. 2, the part above the element and the one above the element in both appear in Differences between and comprise only four elements: By cyclic row and column shifts, the four elements move in as follows:
94
B. Aronov et al.
Fig. 2. Illustration to the proof of Lemma 2
where represents the cyclic shift and indices are calculated modulo When and all four elements and belong to the same submatrix, namely, to Since the constant gap property is preserved by cyclic row and column shifts, we have and thus The cases when and/or are handled by a variant of this argument; we omit the details in this version. This completes the proof of and of the lemma. Lemma 3. Let and be matrices in Combine single matrix in two different ways, namely, put and In other words, for all If P has the constant gap property, then (a) and (b) their In addition,
are in and
and
into a
and is zero. are distinct if
Thus
Proof. The resulting matrices obviously belong to and have zero discrepancy, as linear combinations of matrices of zero discrepancy. It is easy to check that if Thus to prove (b), it suffices to show that the elements of the matrices are all distinct. We focus on the argument for is analogous. Since
A Generalization of Magic Squares with Applications to Digital Halftoning
95
implies and In other words, for a repeated value to occur in there must exist two positions and so that in the same number occurs at and and this also happens in We argues that this is impossible. Indeed, since is defined by just repeating the same matrix (with all entries distinct) times, each element stays in the same relative position in each submatrix. On the other hand, no element in a submatrix of occurs in the same position in any other submatrix. We now prove a stronger version of Theorem 1d. Theorem 2. for any integers Moreover, a zero-discrepancy matrix in can be explicitly computed in time linear in its size using space. Proof. We generalize the construction presented in Lemma 3. A matrix with zero discrepancy is defined using constant-gap matrices of size and one arbitrary matrix of the same size (all in as follows:
For example, when R, Q, P for
and M is constructed as follows, where we have used respectively, to avoid cumbersome notation.
96
B. Aronov et al.
The remainder of the proof proceeds just as in that of Lemma 3; we omit the details. Recall that Thus we can generate every entry of such a matrix without explicitly storing any information besides the matrices the computation requires at most additional working space.
4
The Class of Constant-Gap Matrices
We have described a scheme for constructing matrices with zero A key ingredient in the recipe is a constant-gap matrix in It is easily checked that a different choice of such a matrix produces a different zero-discrepancy matrix. Thus a natural question arises: How many different constant-gap matrices of a given size are there? In this section we, in a sense, completely characterize the class of constant-gap matrices in In fact, we discuss a somewhat more general class of matrices. Let be the set of all integer matrices with entries each used exactly once. A matrix has constant-gap property if, for all It is clear from the definition that this property, as already observed in Lemma 1, is invariant under a number of operations: Lemma 4. The constant-gap property is preserved (1) under an arbitrary permutation of rows of a matrix, (2) under an arbitrary permutation of columns of a matrix, and, for square matrices, (3) under mirror reflection through its main diagonal. Two constant-gap matrices are equivalent if one of them is derived from the other by a sequence of operations listed in the statement of the lemma.2 We are interested in counting the number of these equivalence classes. Lemma 5. Every equivalence class can be represented by a matrix in canonical form, which satisfies the following additional properties: (a) Every row of P is sorted, i.e., for (b) Every column of P is sorted, i.e., if (c) Generally, (d) (e) P is completely specified by
for convenience we define we put
for
and for all
Proof. We argue that all the properties can be satisfied without leaving the equivalence class. Columns can be permuted to sort the top row and then rows can be permuted to sort the leftmost column. Because of the constant-gap property, this sorts all rows and columns. Properties (c) and (d) follow from this ordering. The next property follows from the constant-gap condition, namely 2
To avoid cumbersome wording, we will henceforth not discuss the case of square matrices separately. The reasoning there is entirely analogous, with the exception of an occasional invocation of diagonal symmetry to further reduce the number of equivalence classes. We omit further details.
A Generalization of Magic Squares with Applications to Digital Halftoning
Fig. 3. The only equivalence class of constant-gap matrices for
97
and the three classes for
It is not difficult to see that there exists only one equivalence class (up to diagonal reflection) of constant-gap matrices in when for there are three equivalence classes, refer to Fig. 3. For there exists only one equivalence class, whereas there are many when These observations can be generalized as follows. The set of all constant-gap matrices in in canonical form is denoted by In this section we give a characterization of the sets for all We begin with some additional terminology and then state our characterization. We define another operation on matrices. Given matrices and their expansion product is the matrix defined by In addition, define a simple row of length to be the matrix filled with consecutive numbers in this order. Define a simple column analogously. The following facts are easily verified. Fact 1. consists of a single matrix, which is a simple row of length An analogous statement holds for Both row- and column-major order filled members of have constant-gap property. In particular, for The two matrices have the same canonical form in so for Fact 2. If
and
then
Surprisingly, in the sense made more precise by the following theorem, Facts 1 and 2 describe completely. The remainder of the section is devoted to the proof of this assertion. Theorem 3. (a) A matrix
can be characterized as follows. can be written uniquely as
where is an alternating sequence of simple rows and columns, each of length at least two; if or if and only if In this for (b) case, consists just a simple row or column. A column difference for some is the difference between corresponding entries of two columns; it is independent of the row where the difference is taken, by the constant-gap property. Similarly, a row difference for is the difference between corresponding entries of two rows.
98
B. Aronov et al.
Fig. 4. Partition of a matrix by vertical boundaries of h-runs
Lemma 6. No row difference equals a column difference. In other words, for any and Proof. By the constant-gap property, Their equality would imply in P is repeated.
and contradicting the assumption that no entry
Proof (Theorem 3). We start with the existence proof for part (a). If or we are done, so assume Without loss of generality, assume that so that By induction, it is sufficient to argue that in this case P can be written as a product of a smaller matrix and a simple row of length at least two. Let A horizontal run in P (an h-run, for short) is a maximal sequence of consecutive integers appearing in adjacent entries of a row of P; the length of an h-run is the number of such integers. Each h-run is associated with an interval defined by its first and last column indices. The initial h-run is the one starting at the upper left corner of the matrix; by our assumption its length is at least two. The value must be contained in for it cannot lie in by maximality of the run and it is the smallest value in the matrix outside of the run. Thus we have the row difference Lemma 7. No h-run is longer than the initial run. Proof. If there existed such an h-run, we would have a column difference equal to appear within the run. However, we already identified a row difference of in the matrix. This would contradict Lemma 6. Recall that in P the differences between consecutive elements in the row are equal to the corresponding differences in the top row, so in terms of presence and length of runs, every row behaves exactly the same. Thus P can be partitioned by vertical lines corresponding to boundaries of h-runs, as shown in Fig. 4. Lemma 8. All h-runs have the same length.
A Generalization of Magic Squares with Applications to Digital Halftoning
99
Proof. By Lemma 7, no h-run is longer than the initial h-run of length . For a contradiction, let be the first column at which an h-run of length starts. Such an h-run in the top row is a sequence Where in the matrix is the next integer, namely the value By definition of an h-run, it cannot be located in the same row. So, it must lie before column say in location for some Since all the h-runs located to the left of column are of length the h-run starting at must consist of values However, since the difference between rows zero and one is must have value Moreover, so the value occurs both at and in the run starting at value which is impossible. This property implies the following structure of the matrix P. The number is a divisor of The entire matrix consists of h-runs of length The first element of each run is a multiple of If L is a simple row of length we can easily verify that indeed for the matrix defined by We claim that It is easily checked that while properties (a)–(e) follow from the corresponding properties for P. We now address the question of uniqueness. We have shown that any matrix in can we written as an expansion product of some number of simple rows and columns. Since the expansion product of two simple rows (resp. columns) is a simple row (resp. column), by consolidating products of consecutive rows (resp. columns) we can express P as a product of alternating rows and columns. This representation is unique, since the type and size of the last factor can be “read” directly from the matrix—the factor is a simple row if and a simple column if its length is the length of the initial run, which is horizontal in the former case and vertical in the latter one. It remains to note that a matrix from can always be produced as a product of a simple row of length and a simple column of length thus constant-gap matrices of all orders exist. Reversing the order of multiplication produces a different matrix, provided proving part (b) of the theorem.
5
Concluding Remarks
We have introduced a discrepancy-based measure of uniformity of an square matrix containing as a generalization of a semimagic square. We have succeeded in obtaining matrices of even dimension with zero discrepancy for families of contiguous submatrices. For arbitrary we can construct a matrix of zero. Moreover, such a matrix can be explicitly computed in time linear in its size using only space, which is a great advantage over the heuristic algorithms used for designing blue-noise masks in digital halftoning. This paper serves as a starting point of this type of investigation. A number of issues are still left open. One of the most interesting and attractive problems is to find low-discrepancy matrices, when (dimension of the matrix) and (the dimension of submatrix) are relatively prime to each other.
100
B. Aronov et al.
References 1. A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber: “Geometric Applications of a Matrix Searching Algorithm,” Proc. 2nd ACM Symposium on Computational Geometry, pp. 285–292, 1986. 2. T. Asano, N. Katoh, K. Obokata, and T. Tokuyama, “Combinatorial and Geometric Problems Related to Digital Halftoning,” Theoretical Foundations of Computer Vision: Geometry, Morphology, and Computational Imaging, LNCS 2616, Springer, 2003. 3. T. Asano, “Digital Halftoning: Algorithm Engineering Challenges,” IEICE Trans, on Inf. and Syst., E86-D, 2, 159–178, 2003. 4. T. Asano, K. Obokata, N. Katoh, and T. Tokuyama: “Matrix rounding under the measure and its application to digital halftoning,” Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 896–904, San Francisco, 2002. 5. B.E. Bayer: “An optimum method for two-level rendition of continuous-tone pictures,” Conference Record, IEEE International Conference on Communications, 1, pp. (26-11)–(26-15), 1973. 6. B. Chazelle: The Discrepancy Method: Randomness and Complexity, Cambridge University Press, 2000. 7. R.W. Floyd and L. Steinberg: “An adaptive algorithm for spatial gray scale,” SID 75 Digest, Society for Information Display, pp. 36–37, 1975. 8. H.D. Heinz: “Magic Squares, Magic Stars & Other Patterns” web site, http://www.geocities.com/CapeCanaveral/Launchpad/4057/. 9. R.L. Graham, B.D. Lubachevsky, K.J. Nurmela, P.RJ. Östergård: “Dense packings of congruent circles in a circle,” Discrete Math., 181, 139–154, 1998. 10. D.E. Knuth, The Art of Computer Programming, volume 1, Fundamental Algorithms, 3rd ed. (Reading, Massachusetts: Addison-Wesley, 1997. 11. Kodera Ed.: Practical Design and Evaluation of Halftoned Images, (in Japanese) Trikepps, 2000. 12. J. Matoušek: Geometric Discrepancy, Springer, 1991. 13. T. Mitsa and K.J. Parker: “Digital halftoning technique using a blue-noise mask,” J. Opt. Soc. Am., A/Vol. 9, No. 11, 1920–1929, 1992. 14. K.J. Nurmela and P.RJ. Östergård: “Packing up to 50 Equal Circles in a Square,” Discrete Comput. Geom., 18, 111–120, 1997. 15. R.A. Ulichney: “Dithering with blue noise,” Proc. IEEE, 76, 1, 56–79, 1988. 16. R. Ulichney: “The void-and-cluster method for dither array generation,” IS&T/SPIE Symposium on Electronic Imaging Science and Technology, Proceedings of Conf. Human Vision, Visual Processing and Digital Display IV, (Eds. Allebach, John Wiley), SPIE vol.1913, pp. 332–343, 1993. 17. M. Yao and K.J. Parker: “Modified approach to the construction of a blue noise mask,” J. Electronic Imaging, 3, 92–97, 1994.
Voronoi Diagrams with a Transportation Network on the Euclidean Plane* Sang Won Bae and Kyung-Yong Chwa Division of Computer Science, Department of EECS, Korea Advanced Institute of Science and Technology, Daejeon, Korea {swbae, kychwa}@jupiter.kaist.ac.kr
Abstract. This paper investigates geometric and algorithmic properties of the Voronoi diagram with a transportation network on the Euclidean plane. With a transportation network, the distance is measured as the length of the shortest (time) path. In doing so, we introduce a needle, a generalized Voronoi site. We present an algorithm to compute the Voronoi diagram with a transportation network on the Euclidean plane, where is the number of given sites and is the complexity of the given transportation network.
1
Introduction
With a transportation network, like streets in a city, subway or bus networks, or a highway over a nation, people have become capable to move faster. Finding a shortest (time) path using such transportation is very important due to the tendency of people trying to move with the shortest duration. In this situation, let us imagine a set of sites or service stations, and suppose that one should visit any of them; here, the Voronoi diagram problem arises. This paper considers geometric and algorithmic issues about the Voronoi diagram under the above situation. The Voronoi diagram on the plane with a transportation network has been studied by several researchers. Hurtado et al. [1] and Abellanas et al. [2] discussed a single infinite road network as a straight line on the Euclidean plane; the currently best known results about the Voronoi diagram on the Euclidean plane with a transportation network. In addition, transportation networks on the plane have been dealt with; Abellanas et al. [3] dealt with isothetic and monotone networks and, more generally, Aichholzer et al. [4] introduced the city Voronoi diagram, the Voronoi diagram with an isothetic transportation network on the plane. All the previous work has assumed that every roads in a transportation network have the same speed. But, as mentioned at the beginning, several kinds of transportation networks are established on our surroundings and, hence, transportation networks with diverse speeds need to be considered. This paper is the first result dealing with transportation networks with multiple roads, possibly having arbitrary directions and diverse speeds, on the Euclidean plane. *
This work is supported by grant No.R01-2003-000-11676-0 from KOSEF.
R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 101–112, 2004. © Springer-Verlag Berlin Heidelberg 2004
102
S.W. Bae and K.-Y. Chwa
1.1
The Model
A transportation network consists of several roads as non-intersecting line segments on the plane, which may share a node, or an endpoint, in common. The roads have individual supporting speeds. This structure can be generally represented as a planar straight-line graph G = (V, E) with speed on each road, where V is a set of nodes and E is a set of roads. In our model, one can enter into and exit from G at any point of roads or nodes. Along any road one can move at fixed speed Off the network G, one can move at unit speed in any direction. We assume that for all roads since, if the road does not contribute any shortest paths. Restricting entry points to fixed points on the roads yields an instance of Voronoi diagrams for additively weighted points, easily solvable (mentioned in [4]). Given a transportation network G, the distance with the transportation network G, called is measured as the length (duration) of the shortest (time) path when using roads in G. In fact, induces a metric on as a shortest path metric. We call the metric induced on by the transportation metric with G.
1.2
The Results
We present an algorithm for constructing the Voronoi diagram under the transportation metric with G, for a set S of sites. The algorithm runs in time and requires space, where is the number of roads in G. Throughout this paper, we will denote the number of roads by and the number of sites by As a special case, we can reduce the runtime when the given transportation network is with the constraint that all roads have the same speed and their possible directions are finitely fixed. In this situation, we can compute the diagram in time with linear space. In doing so, we introduce a generalized site, a needle. A needle can be represented as a set of additively weighted points, lying on a line and weighted linearly. A Voronoi diagram for needles with a certain condition, so called non-piercing, on the Euclidean plane can be computed in time and in space. Arguments and details about needles are presented in Section 3. Under the transportation metric, it is not so easy any more to plan a shortest path, even if a source and a destination are determined. We simply state our results about the path planning under the transportation metric in Section 6.
2
Basic Idea
In this section, we describe our basic idea to solve the problem through an observation on the plane with a transportation metric. The transportation metric has some bad properties so that computing Voronoi diagrams under it is not so easy. For example, we can easily construct a cyclic
Voronoi Diagrams with a Transportation Network on the Euclidean Plane
103
bisector with segments between two points; a transportation network with cyclic roads and two sites, one of which is much closer to a road than the other. This violates one of necessary conditions to apply the abstract Voronoi diagram, one of the most popular and useful tools to compute Voronoi diagrams (see Subsection 3.2). Thus, we should find a different approach to solve the problem.
Fig. 1. Illustrations of
sets when G has a single road
To find such a different approach, we have to investigate the plane with a transportation network more carefully. Let us consider a simplest case, a single road transportation network. Given a single road on the Euclidean plane, we know how to find a shortest path by Hurtado et al. [1] and Abellanas et al. [2]. We draw the following observation from their results. Observation 1. To reach the destination as quickly as possible, in accessing a road where 1. The entering or exiting angle with should be [1]. 2. If above is impossible, access the road through the closer node of By Observation 1, we can find the set of under the transportation metric with G, defined as for any point on the plane and We shall denote it by Figure 1 shows four illustrations for the boundary of when G is a single road network. Note that can be represented as a union of one large disk centered at and two needle-shaped regions along the road, each of which is a union of a set of disks whose radii are linearly assigned along the road. This provides an intuition to analyze the transportation metric from a different view. Our strategy is to consider such a needle-shaped region produced from as an independent Voronoi site under the Euclidean metric. In Section 3, we define such a Voronoi site, called a needle. Then, we can compute the distance with more roads by using needles on the roads, if we can compute the distance to a needle from any point under the Euclidean metric. We will show how to compute a set of needles from given sites S, which allows us to properly analyze the given transportation network G, in Section 4 and 5.
104
3
S.W. Bae and K.-Y. Chwa
Needle: A Generalized Site
In this section, we introduce a needle as a more generalized Voronoi site. Needles play a very important role in computing diagrams under the transportation metric. In Subsection 3.1, we define a needle formally and show that the distance from any point to a needle can be computed. In Subsection 3.2, we discuss Voronoi diagrams for needles on the Euclidean plane.
3.1
Definition of a Needle
A needle is generalized from a line segment with an additive weight. Note that a line segment can be viewed as a set P of points on it and the distance to a line segment from any point on the plane is represented by Similarly, a needle is a set of weighted points lying on a line segment. Note that a weighted point with weight can be represented as a pair and the distance to from any point is equal to One necessary condition for a needle is that the weight on a needle is assigned linearly. With this property, a needle is suitable to represent as noted in Section 2. The following is a definition of a needle.
Fig. 2.
sets of a needle
Definition 1. A needle p is a set of all points on a line segment endpoints are and with weight function The weight linearly from to for each and such that and The needle p is represented by a 4-tuple, may use the terms and instead of respectively.
whose is given We and
Figure 2 shows sets of a needle p under the Euclidean metric, when and case by case. As increases from 0, grows from a point at and reaches at along We also define the speed of a needle p as and its direction as direction toward from Note that if is of shape of a disk, and thus we can regard p as a point with weight Throughout this paper, we will draw a needle as an arrow headed in its direction, as shown in Figure 2.
Voronoi Diagrams with a Transportation Network on the Euclidean Plane
105
We now discuss the distance from any point on the plane to a needle under the Euclidean metric. For any point and any needle p, the distance is represented as follows:
where is the weight assigned to of a needle as follows:
can be computed by the definition
for all We define some terms associated with a needle p. Without loss of generality, we assume that p is horizontal and is to the left of Let denote a line, whose slope is tan and which meets and denote a line, whose slope is and which meets where We define to be a line segment associated with p whose endpoints are and the intersection point between and Symmetrically, we define see Figure 3. Next, we let be a set of points above such that, for any point a line, which is perpendicular to and meets intersects In this manner, we also define symmetrically. Note that and decompose into four disjoint and connected regions as shown in Figure 3.
Fig. 3. Plane decomposition around a needle p
Lemma 1. Let p be a needle represented by from any point to p is as follow.
Then, the distance
By the above lemma, we can easily compute the distance from any point to a needle in constant time.
3.2
Voronoi Diagrams for Needles Under the Euclidean Metric
In this subsection, we compute the Voronoi diagram for a set of needles. In order to do so, we recall the abstract Voronoi diagram introduced by Klein [5]. In this model, a system of bisecting curves for S, is given, which is called admissible if the following conditions are fulfilled:
S.W. Bae and K.-Y. Chwa
106
1. is homeomorphic to a line or empty. 2. The intersection of any two bisectors consists of finitely many components. 3. 4. For any subset and is path-connected if it is nonempty.
where
and is the bisecting region between and However, needles violate condition 1 and condition 4, since needles generalize line segments. Note that the bisector between two needles p and q is defined as which is computable in constant time by Lemma 1. We suggest another condition restricting needles so that the bisector system is admissible. We consider the following four cases for each needle p with respect to another needle q. 1. 2.
and
includes either
or
includes both includes neither
and nor
not
both. 3. 4.
and and
We call two needles, p and q, non-piercing if and only if, for each with respect to the other, the fourth case does not occur. Otherwise, we call two needles piercing. Now, we consider only a set of pairwise non-piercing needles that leads to our goal, sufficiently. Note that the non-piercing for needles condition generalizes the disjointness for line segments. Theorem 1. Let S be a set of pairwise non-piercing needles. Then, the system of bisecting curves for S, is admissible. Constructing abstract Voronoi diagrams has been dealt with by several researchers, Klein [5], Mehlhorn et al. [6], Klein et al. [7], and Dehne and Klein [8]. All presented algorithms take an optimal time and an optimal space. Thus, we conclude the following corollary as a result of this section. Corollary 1. Let S be a set of pairwise non-piercing needles. Then, the Voronoi diagram for S on the Euclidean plane can be computed in time and space. In fact, Aichholzer et al.[4] introduced the concept similar to non-piercing needles. The authors discussed their concepts in the wavefront model and they defined a needle as a figure produced by the wavefront of a site while touching road segments. In the wavefront model, each site sends out a wavefront and the interference pattern of these wavefronts contributes the diagram. In contrast with their approach, we define a needle as an independent Voronoi site.
Voronoi Diagrams with a Transportation Network on the Euclidean Plane
4
107
Relation Between a Transportation Network and Needles
In this section, we draw a relation between a given transportation network and a set of needles. Theorem 2. Given a transportation network G and a set of sites S, there exists a set of needles such that induces i.e., for any there exists a site such that Proof. First, a point produces at most two new needles on a road (see Figure 1). These needles are born at a node of or at an intersection point of the road with the line, whose slope is and which meets by Observation 1. One important fact is that the produced needles are also Voronoi sites and thus they possibly produce new needles on other roads. We will call such a newly produced needle a needle produced on a road from a (parent) needle. Note that, generally, a needle produces at most two new needles on a road. Suppose that a needle produces three needles on a road. Then, two of the three should be in the same direction and one of these two needles must be dominated by the original needle or other newly produced ones, since the speeds of the three needles are the same and their neighborhood sets are convex under the Euclidean metric (see Figure 1 and 2). More formally, we define to be a set of needles produced from a needle p on all roads in G. For a set X of needles, In order to obtain all needles produced from a site we apply repeatedly. We let and We then let be and be Moreover, we let be the length of a shortest path from to where the path passes through at most roads. Surely, We claim that which directly implies the theorem. There exists a needle such that and for any point and Let us consider a sequence of needles, such that is produced from and With these needles, we construct a path from to passing through roads. starts and goes to the points on which obeys the rule of Observation 1. Next, passes along the road, on which is produced. Recursively, passes and next to and finally reaches from Since each is produced on a road, passes through roads, which is at most hence, Let us consider a path of length from to and assume that passes through roads, for We then construct needles, inductively, such that and consists of segments on roads, in order, each of which starts at and ends at on road Also, denotes a node of in direction toward from Note that roads indicated by may not be disjoint. We construct as follows: and For convenience, let be
108
S.W. Bae and K.-Y. Chwa
Then, since is a shortest path and it obviously obeys the rule of Observation 1. We are sure that If a sub-path of from to is a shortest path passing through roads. We construct a path of length from to is obtained by adding the path at the beginning of Then, since passes through roads and a sub-path of By induction, implying that Finally, we show that and thus taking this says that, for any there exists a site that
With such
Theorem 2 shows the existence of a set of needles noted at the end of Section 2. But, may not be pairwise non-piercing and further have infinitely many needles by the construction from the proof of Theorem 2. Thus, we should reduce the number of needles and make them pairwise non-piercing. For any we call p effective if otherwise we call p ineffective. Lemma 2. There exists a set non-piercing, such that
of needles, which are effective and pairwise
Proof. First, we remove all ineffective needles from We let be the set of all effective needles in Trivially, We will construct from by making it pairwise non-piercing without any change in its diagram. We can partition into such that and all needles in lie on for if all roads in G are given as For each needle we can find (at most) one needle, the closest needle in the direction of p from p stretches to a node of but the part over does not contribute since both p and q are effective and their speeds are the same as We thus cut p by setting to be and to be We denote the set of these new needles from by and by Since we cut only a useless part of every needle from Now, we show that is pairwise non-piercing. is surely pairwise nonpiercing, since it is a set of points. is also pairwise non-piercing, since all needles in lie on a line including a road and they are disjoint. We assume that p pierces q in and q is produced on a road q is not a needle produced from p, since p and q are non-piercing if q is a needle produced from p. If a needle produced on from p is effective, q cannot dominate any point on over and thus q is not pierced. Hence, no needles on from p are effective. This implies that q dominates two possible starting points of needles produced from p, and thus q dominates all points between the two points. Consequently, p does not pierce q, a contradiction. Therefore, is pairwise non-piercing.
Voronoi Diagrams with a Transportation Network on the Euclidean Plane
5
109
Algorithm
In this section, we consider more algorithmic issues. A simple algorithm for computing from S is presented. The algorithm runs in time.
5.1
Computing
We recall the wavefront model. In the wavefront model, each site starts sending out a wavefront at time 0 and the interference pattern between each wavefront constitutes the Voronoi diagram. A wavefront at time from each site can be interpreted as the set the boundary of under the transportation metric with G. It is too hard to compute from since can include possibly infinitely many needles, as noted earlier. However, the effectiveness of a needle p can be tested only with effective needles already emitting wavefronts at time Thus, we simulate the wavefront model with sweeping the plane with the wavefronts. During simulating the wavefront model, at time we test the effectiveness of p and we do some processes for p, only if p is effective. In this way, we compute directly, not from Lemma 4 reduces the number of applying Lemma 3. Needles produced on from a needle p are at most two of six needles; four needles produced from weighted points or and two needles starting from a node of Lemma 4. Let p be a needle produced on a road from a needle q. For another road if p does not dominate any node of or no needles produced on from p are effective. Our algorithm runs with handling events, defined as certain situations in the wavefront model. Two kinds of events are defined; one occurs when a needle produced on a road from another effective needle starts growing, which we call a birth event; and the other occurs when a wavefront sent out from a needle reaches a node, called a node event. From each event, we can ascertain the occurring time, the occurring place, the associated site, and so on. We will call an event effective if its associated needle dominates the point where the event occurs. To handle these events, we need two types of data structures: is an event queue implemented as a priority queue. The priority of an event is its occurring time. supports inserting, deleting, and extractingminimum in logarithmic time with linear space. are balanced binary search trees, each associated with where the road set E is given as Each stores needles on in order. The precedence is the position of the starting point of a needle and ties are broken by the growing direction. supports inserting and deleting of a needle in logarithmic time, and also a linear scan for needles currently in in linear time with linear space.
110
S.W. Bae and K.-Y. Chwa
At the beginning of the algorithm, we initialize and for We then compute the associating birth events with for all and insert them into And, for each node we compute the node event for the nearest site from insert it into and set the variable to be the node event. Once the initialization is done, we extract the upcoming event from and process it as follows, repeatedly, while is not empty. If a birth event on occurs, we first test the effectiveness of its associated needle p, and then insert it to The effectiveness checking can be accomplished by checking with at most two neighbor needles in More precisely, we find two neighbors around from and test whether two neighbors dominate (Note that this test is necessary but not sufficient, i.e. ineffective needles may pass this test. This however does not increase the asymptotic number of needles; we will discuss about this argument in the next subsection.) Once the effectiveness test is passed, we insert p into and compute node events from p. Note that is the currently earliest node event on in We let be the node event on newly computed from p. Then, only if will occur earlier than we delete from insert into and set as When a node event on a node occurs, we compute where p is the needle associated with Then, from all needles in we compute the associating birth events and insert them into After the event processing, all effective needles are stored in each We then extract them with proper cutting, as described in the proof of Lemma 2. We denote by the resulting set of needles after running the algorithm and by The following lemma guarantees the correctness of the algorithm. Lemma 5. Let piercing and
be a set of effective needles in
Then,
is pairwise non-
Proof. During running the algorithm, all needles inserted into are obtained by applying from any site which implies that The algorithm filters ineffective needles efficiently by Lemma 4 and by the effectiveness testing in processing a birth event, which is necessary. Hence, all needles in are ineffective and Note that all ineffective needles are totally dominated by other effective ones. To effective needles in we can apply an analogue to the proof of Lemma 4. Thus, is pairwise non-piercing.
5.2
Analysis
Our algorithm depends on the number of handled events and on the number of needles in In fact, the number of events is and also
Voronoi Diagrams with a Transportation Network on the Euclidean Plane
111
since the algorithm applies exactly times and for any needle p. This implies the following lemma. Lemma 6.
where
is the number of sites and
is the number of roads in G.
Finally, we conclude a main theorem. Theorem 3. Let G be a transportation network with roads and S be a set of point sites. The Voronoi diagram for S under the transportation metric with G can be computed in time and space. Proof. Handling an event takes time. Thus, computing takes time and this is a bottleneck of the algorithm. For any other processes of the algorithm, time is sufficient. For the space complexity, the algorithm uses only a linear space on the number of handled events and produced needles, which is
Fig. 4. Illustration of a Voronoi diagram with the transportation network on the Euclidean plane. Dashed lines depict Voronoi edges in
112
6
S.W. Bae and K.-Y. Chwa
Concluding Remarks
In previous sections, we consider only a set of point sites but our framework is also applicable to different types of sites, since we handle needles, more generalized sites. We showed that, for points additive weight or for disjoint line segments, our algorithm does work properly with minor modification and no gains for the runtime. As mentioned in the introduction, it is not trivial to plan a shortest path under the transportation metric. We also showed that a shortest path to the nearest site from a given point can be reported in time by point location over where is the path complexity, bounded by And a shortest path between given two points can be reported in time by constructing the shortest path map, in fact, the Voronoi diagram of needles produced from one of the two given points; this is a special case of the weighted region problem by Mitchell and Papadimitriou [9], which is solved in time where N is the complexity of the polygonal partition and L denotes the precision of the problem instance. Our algorithm is easy to implement (We have implemented it in practice; Figure 4 is obtained by our program) but the asymptotical complexity is not optimal. A future work is to improve the algorithm in runtime while retaining the ease of implementation.
References 1. Hurtado, F., Palop, B., Sacristán, V.: Diagramas de voronoi con funciones temporales. VIII Encuetos en Geometria Computacional (1999) 2. Abellanas, M., Hurtado, F., Sacristán, V., Palop, B.: Voronoi diagram for services neighboring a highway. IPL: Information Processing Letters 86 (2003) 3. Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: Proximity problems for time metrics induced by the metric and isothetic networks. IX Encuetros en Geometria Computacional (2001) 4. Aichholzer, O., Aurenhammer, F., Palop, B.: Quickest paths, straight skeletons, and the city voronoi diagram. In: Proceedings of the 8th SoCG, (June, 5-7, 2002), New York, ACM Press (2002) 151–159 5. Klein, R.: Concrete and Abstract Voronoi Diagrams. Number 400 in Lecture Notes in Computer Science, LNCS. Springer-Verlag, Berlin, Germany (1989) 6. Mehlhorn, K., Meiser, S., O’Dunlaing, C.: On the construction of abstract Voronoi diagrams. Discrete Comput. Geom. 6 (1991) 211–224 7. Klein, R., Mehlhorn, K., Meiser, S.: Randomized incremental construction of abstract voronoi diagrams. Computational Geometry: Theory and Applications 3 (1993) 157–184 8. Dehne, F., Klein, R.: “the big sweep”: On the power of the wavefront approach to Voronoi diagrams. Algorithmica 17 (1997) 19–32 9. Mitchell, J.S.B., Papadimitriou, C.H.: The weighted region problem: Finding shortest paths through a weighted planar subdivision. Journal of the ACM 38 (1991) 18–73
Structural Alignment of Two RNA Sequences with Lagrangian Relaxation Markus Bauer and Gunnar W. Klau Institute of Computer Graphics and Algorithms, Vienna University of Technology, Austria {markus, gunnar}@ads.tuwien.ac.at
Abstract. RNA is generally a single-stranded molecule where the bases form hydrogen bonds within the same molecule leading to structure formation. In comparing different homologous RNA molecules it is usually not sufficient to consider only the primary sequence, but it is important to consider both the sequence and the structure of the molecules. Traditional alignment algorithms can only account for the sequence of bases, but not for the base pairings. Considering the structure leads to significant computational problems because of the dependencies introduced by the base pairings and the presence of pseudoknots. In this paper we address the problem of optimally aligning two given RNA sequences either with or without known structure (allowing for pseudoknots). We phrase the problem as an integer linear program and then solve it using Lagrangian relaxation. In our computational experiments we could align large problem instances—18S and 23S ribosomal RNA with up to 1500 bases within minutes while preserving pseudoknots.
1
Introduction
Unlike DNA, an RNA molecule is generally single-stranded and folds in space due to the formation of hydrogen bonds between its bases. While similarity between two nucleic acid chains is usually determined by sequence alignment algorithms, these can only account for the primary structure and thus ignore structural aspects. However, the problem of producing RNA alignments that are structurally correct has emerged as one of the central obstacles for the computational study of functional RNAs. To date, the available tools for computing structural alignments are either based on heuristical approaches and thus produce suboptimal alignments or cannot attack instances of reasonable input size. In this paper we deal with the comparison of two RNA sequences together with their structure. Indeed, we do not necessarily require the actual knowledge of either structure, but will infer a common structure based on the computation of preserved hydrogen bonds. In the presence of pseudoknots, the problem becomes NP-hard even when only two sequences have to be aligned (Evans gives an NP-hardness proof for a special case of this problem in [7]). The computational problem of considering sequence and structure of an RNA molecule simultaneously was first addressed by Sankoff [15] who proposed a dynamic programming algorithm that aligns a set of RNA sequences while at R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 113–123, 2004. © Springer-Verlag Berlin Heidelberg 2004
114
M. Bauer and G.W. Klau
the same time predicting their common fold. Algorithms similar in spirit were proposed later on for the problem of comparing one RNA sequence to one or more of known structure. Corpet and Michot [5] align simultaneously a sequence with a number of other, already aligned, sequences using both primary and secondary structure. Their dynamic programming algorithm requires running time and space is the length of the sequences) and thus can handle only short sequences. They propose an anchor-point heuristic to divide large alignment problems by fixed alignment regions into small subproblems that the dynamic programming algorithm can then be applied to. Bafna et al. [2] improved the dynamic programming algorithm to a running time of which still does not make it applicable to real-life problems. Common motifs among several sequences are searched by Waterman [16]. Eddy and Durbin [6] describe probabilistic models for measuring the secondary structure and primary sequence consensus of RNA sequence families. They present algorithms for analyzing and comparing RNA sequences as well as database search techniques. Since the basic operation in their approach is an expensive dynamic programming algorithm, their algorithms cannot analyze sequences longer than 150-200 nucleotides. Gorodkin et al. [8] and Mathews and Turner [12] published simplified versions of Sankoff’s original algorithm. Hofacker et al. [10] give a different approach to structural alignments: instead of folding and aligning sequences simultaneously, they present a dynamic programming approach to align the corresponding base pair probability matrices, computed by McCaskill’s partition function algorithm [13], and therefore take the structural information into account. Reinert et al. [11] presented a Branch-and-Cut algorithm for aligning an RNA molecule of known sequence and known structure to an RNA molecule of known sequence but unknown structure. The algorithm computes an (optimal) alignment that maximizes sequence and structure consensus simultaneously and is based on the Branch-and-Cut technique. The method can handle pseudoknots and is able to solve already problems up to a size of 1400 bases. However, for problems of that size their implementation starts to require prohibitive time. We start with a similar integer linear programming (ILP) formulation as given by Reinert et al., but instead of using a Branch-and-Cut approach, we resort to Lagrangian relaxation which was already successfully applied by Lancia et al. to the contact map problem [4] which is similar to the RNA alignment problem. The structural alignment of RNA molecules is central to the various RNA similarity or structure prediction problems defined in the above cited papers. If the two molecules are functionally related and have a similar structure, the RNA structural alignment allows, e. g., to draw conclusions about the structure of the unknown molecule. The techniques we will put forward can be modified such that incremental or simultaneous computations of multiple structural sequence alignments are possible. Since the traditional approaches cannot solve middle sized or large instances of the structural RNA alignment problem without using ad hoc heuristics, biologists still have to carry out large structural alignments by hand. Furthermore,
Structural Alignment of Two RNA Sequences with Lagrangian Relaxation
115
most algorithms are not able to integrate tertiary structure interactions like pseudoknots, or need prohibitive ressources. We tested a first version of our proposed algorithm with 23S rRNA sequences from [17] and 18S rRNA sequences from Drosophila melanogaster (1995 bases) and human (1870 bases). We could, for example, optimally align the 23S rRNA sequences of Pyrodictium occultum (1497 bases) and Sulfolobus shibatae (1495 bases). The result was a structural alignment that is a very good approximation of the “hand-made” optimal structural alignment and is, in particular, much better than the purely sequence-based optimal alignment. In the 18S rRNA dataset it is well known that the first 1200 bases contain pseudoknots. We can show that our approach correctly preserves these pseudoknots. To our knowledge, no other algorithm is capable of doing this. The paper is structured as follows: Section 2 gives basic definitions and a mathematical formulation of the problem. In Sect. 3 we study how to relax the ILP in order to make it efficiently solvable, whereas Sect. 4 shows how we solve the original problem by means of Lagrangian relaxation. The results of our computational experiments are given in Sect. 6. Finally, we discuss our results in Sect. 7.
2
Basic Definitions and Mathematical Formulation
Before presenting a graph-theoretic model of aligning two RNA sequences and a corresponding integer linear programming (ILP) formulation we start with some basic definitions: Definition 1. Let S be a sequence of length over the alphabet A paired base is called an interaction, if and and if forms a Watson-Crick-pair. The set P of interactions is called the annotation of sequence S. Two interactions are said to be in conflict, if they share one base. A pair (S, P) is called an annotated sequence. Note that a structure where no pair of interactions is in conflict with each other forms a valid secondary structure of an RNA sequence. We are given two annotated sequences and In graph-theoretic terms the input can be modeled as a graph where the set V denotes the vertices of the graph, in this case the letters of the two sequences, a set A of edges between vertices of the two input sequences (the alignment edges) and I the set of interaction edges between vertices of the same sequence. The left side of Fig. 1 shows such an input graph. Dashed lines are interaction edges, solid lines are alignment edges. Two alignment edges and are said to be in conflict, if or is not satisfied. Visually stated, alignment edges that are in conflict cross or touch each other. A subset of A is called an alignment, if no alignment edges are in conflict. Graph-theoretically, an alignment is a non-crossing matching. Two interaction edges and are said to be realized by an alignment if and only if the alignment edges and
116
M. Bauer and G.W. Klau
Fig. 1. Input graph for structural alignments and realized interaction matches
are realized by The pair is called an interaction match. Note that is an ordered tuple, that is, is distinct from The right side of Fig. 1 shows four interaction matches that are realized by the alignment (indeed it shows a preserved pseudoknot). Each alignment edge and interaction match is assigned a positive weight representing the benefit of realizing this edge or the match. In the case of interaction edges we could choose the score for realizing the interaction match e. g., as the number of hydrogen bonds between the bases or the base pair probability computed by means of McCaskill’s algorithm [13]. Traditional sequence alignments aim at maximizing the score of edges realized by an alignment. A structural alignment, however, takes the structural information (the information contained within the interaction edges) into account as well. The problem of structurally aligning two annotated sequences and calls for an optimal solution of max that is, the score achieved by the weight of the alignment and interaction edges. Three properties, however, have to be satisfied in order to form a valid RNA secondary structure: 1. Every vertex is incident to at most one interaction edge. 2. Each interaction match has to be realized. 3. No alignment edges are in conflict.
Then, an ILP formulation follows directly:
The variable equals one, if alignment edge is part of the alignment, whereas holds, if the alignment edges and realize the interaction
Structural Alignment of Two RNA Sequences with Lagrangian Relaxation
117
match The set contains all subsets of alignment edges, such that all pairs of elements of a specific subset are crossing each other. One can easily verify that all properties for a structural alignment are satisfied: inequalities (3) and (4) guarantee that interaction matches are realized by alignment edges and that every node is incident to at most one interaction edge, whereas (2) guarantees the alignment edges to be non-crossing. The order within the equality constraints (3) denotes an arbitrary order defined on the elements of A (otherwise identical constraints show up twice, that is, and were part of the ILP). Due to the NP-hardness of the problem, we cannot hope to solve the ILP above directly. Therefore, we drop some constraints and show how the relaxed ILP can be solved efficiently.
3
Relaxation and Efficient Solution
We call the ILP (1)-(5) without the constraints (3) the relaxed problem and show how to solve it efficiently. Later we show how to incorporate the dropped constrained again in order to solve our original problem. Our algorithm proceeds in two stages. First, we compute for each the maximal profit that the realization of can possibly yield. Then, we use the maximal profit of each edge to compute a conventional alignment. Lemma 1. The relaxed problem can be solved in time Proof. Suppose the variable then due to (4) all however, the optimal choice for all is given by
as well. For
To put it differently: For each we compute the maximal profit that the alignment edge can possibly realize. The maximum profit consists of its own weight plus the best interaction match that can be realized, if is part of the solution. Let be the maximum profit of alignment edge and let be the realized interaction match. In the second step, we compute the optimal overall profit by solving
118
M. Bauer and G.W. Klau
Let be the solution to the alignment problem above. We claim that the solution of the relaxed problem is given by for all Assume that is not the optimal solution to the relaxed problem, but another solution that does not realize the maximal profit. Then, according to the objective function, there exist and/or that would realize a higher score. There are two possibilities: (a) and (with being the interaction match chosen to be realized by alignment edge This implies that In this case, however, holds and not since the interaction match with the highest score is chosen in the first step of the algorithm. Therefore, there cannot be an whose realization would yield a higher score. (b) This implies that for an element c from the set I (remember that pairs of elements of the same set I are crossing each other) holds because otherwise would have been realized. Again, there cannot be an yielding a higher score in case of For analyzing the running time of the entire algorithm, two things have to be taken into account: First, choosing the interaction match that realizes the maximal profit. Second, computing an alignment, given the single profits If the set of all interaction matches that could possibly be realized by alignment edge is being computed in a preprocessing phase, selecting the best possible interaction match can be accomplished in constant time by means of priority queues (regard the weight of the interaction matches as the priority, then extracting the element with the highest priority can be done in constant time). Computing the alignment dominates the overall running time and can be done in with the Needleman-Wunsch algorithm.
4
Lagrangian Relaxation
We solve the original problem by moving the dropped constraints (3) into the objective function and by penalizing its violation. We assign a Lagrangian multiplier to the constraint. The task is then to find Lagrangian multipliers that provide the best bound to the original problem. The Lagrangian problem is given by:
By setting rewritten as
for
and
to 0, the objective function can be
Structural Alignment of Two RNA Sequences with Lagrangian Relaxation
119
A common and highly efficient way to compute optimal (or near-optimal) Lagrangian multipliers is by employing iterative subgradient optimization. First, compute the subgradients within the iteration:
Then, using these subgradients, a series of
with
is given by
and for all The speed of convergence to the optimal value of the Lagrangian relaxed problem depends heavily on the proper choice of the step size A fundamental result [14] states that for and the value always converges
to the optimal value. The harmonic series with satisfies both conditions; it is not being used in practice, however, since the speed of convergence turns out to be rather poor. Another well-known formula, given in [9] and also applied by Lancia et al. [4], computes the step size of the iteration by
where UB and LB denote the best upper and lower bound computed so far, is a common parameter used within subgradient optimization and are the subgradients evaluated in the iteration.
5
Computing Feasible Solutions
The formula for computing the series of contains the term LB, the best lower bound found so far. In the following, we describe how to derive such a lower bound given given a traditional sequence alignment and a set of interaction edges. Since the set of alignment edges in the alignment is given, we only need to compute the best possible set of interaction edges such that no pair is in conflict. It turns out that this problem can be reduced to the general weighted matching problem. Consider the edges of as nodes and every pair of interaction edges whose endpoints are adjacent to a pair as the edges of the graph. We call the resulting graph the interaction matching graph with edge weights given by the sum of the corresponding interaction edges in G. Figure 2 shows an alignment (dashed lines are interaction edges) with the corresponding interaction matching graph. Lemma 2. A matching of maximum weight in the interaction matching graph corresponds to the structural alignment of maximum weight in the original graph.
120
M. Bauer and G.W. Klau
Fig. 2. Alignment and interaction matching graph
Proof. Recall the definition of a matching of maximum weight. In a matching every node is incident to at most one edge, the sum of the weights of the matching edges is maximal. It is not hard to see that the two properties for a structural alignment are satisfied: 1. Every node in the original graph is incident to (at most) one interaction edge (remember that nodes in the interaction matching graph are in one-to-one correspondence to alignment edges of the original graph). 2. The sum of weights of the interaction edges is maximal.
It is trivial to recover the realized interaction edges from the solution of the matching problem, since each edge in the interaction matching graph corresponds to an interaction match.
6
Computational Results
We implemented our algorithm in C++ using the LEDA library [1] and used a 2.8 GHz Pentium IV with 2 GB of main memory for the computations. Constructing the Input. We adapted the approach of Reinert et al. [11]. For generating the alignment edges we are starting from a conventional sequence alignment with affine gap costs (gap open and gap extension penalty are set to 6 and 2, respectively) and insert all alignment edges realized by any suboptimal alignment scoring better than a fixed threshold below the optimal score. Matches and mismatches have a score of 4 and 1, one single interaction match counts 8. Evaluating the Results. In order to evaluate our approach we made two different kinds of experiments. First, we test our implementation with the same data set
Structural Alignment of Two RNA Sequences with Lagrangian Relaxation
121
as used in [11]. Reinert et al. could align 23S ribosomal RNA sequences of length 1400 with suboptimality 3 alignment edges) in 2 minutes, but with suboptimality 10 alignment edges) they already needed over one hour. Table 1 shows the structural alignment scores that we compute for the same instances with suboptimality 50 alignment edges) in only about 10 minutes which is a significant improvement. Secondly, to test whether our approach can preserve pseudoknots, we use 18 rRNA sequences from Drosophila melanogaster (GenBank: M21017) and human (GenBank: K03432) having 1870 and 1995 bases, respectively. The structure files were obtained from [3]. There are three parts within the sequence that form pseudoknots: (a) bases 4-6 fold with 16-20 and 12-14 with 1198-1200, (b) 601603 with 620-622 and 6 bases between 608-618 with bases from 623-635, and (c) bases 666-667 fold with 1145-1146 and parts of the sequence from 1090-1142 with some bases ranging from 1152-1161. A traditional sequence alignment with affine gap costs was not able to realize the entire conserved structures, that is, some base pairs forming the pseudoknots are not realized. Our algorithm, however, aligned all base pairs forming the pseudoknots. To be precise: the traditional sequence alignment has a structural score of 12031, realizing 366 interaction matches, whereas the Lagrange method computes a score of 12662, realizing 409 interaction matches. Not only could we solve this alignment including several pseudoknots, but the program needed only 15 minutes and very moderate memory MB). Despite the very good computational results we have to remark that in the majority of problem instances—especially instances of 23S rRNA sequences—we could observe gaps between the lower and the upper bound: these gaps range from 2 to several hundred and therefore these instances were not solved to provable optimality (although the comparison with exact techniques like Branch-andCut shows that the scores are optimal or near-optimal). Our approach, however, could be easily integrated into a Branch-and-Bound framework to obtain provable optimal solutions.
122
7
M. Bauer and G.W. Klau
Conclusion
In this paper we gave an ILP formulation of the RNA structural alignment problem and presented an efficient way to solve the problem by means of Lagrangian relaxation in A being the number of alignment edges. Our computational results show that we are able to compute structural alignments with a higher score within much shorter time than previous algorithms. Another advantage of our method is that, unlike most of the dynamic programming formulations, arbitrary pseudoknots can be handled in our framework and therefore the algorithm is able to detect conserved structures containing pseudoknots (as demonstrated in Sect. 6). Furthermore, the approach can be combined with other combinatorial optimization techniques, e. g., Branch-and-Bound or Branch-andCut. Besides this, we plan to extend the method to multiple sequence alignment and to integrate different gap scoring schemes. Last but not least, our formulation is easy to implement (the actual algorithm is just a few hundred lines of code) and does not depend on third-party software like commercial optimization libraries.
References 1. Algorithmic Solutions. The LEDA User Manual Version 4.5, 2004. http://www.algorithmic-solutions.com. 2. V. Bafna, S. Muthukrishnan, and R. Ravi. Computing similarity between RNA strings. In Z. Galil and E. Ukkonen, editors, Proc. of the 6th Annual Symp. on Combinatorial Pattern Matching, number 937 in LNCS, pages 1–16. Springer, 1995. 3. J. J. Cannone, S. Subramanian, M. N. Schnare, J. R. Collett, L. M. D’Souza, Y. Du, B. Feng, N. Lin, L. V. Madabusi, K. M. Muller, N. Pande, Z. Shang, N. Yu, and R. R. Gutell. The comparative RNA web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs. BMC Bioinformatics, 3(1), 2002. 4. A. Caprara and G. Lancia. Structural Alignment of Large-Size Proteins via Lagrangian Relaxation. In Proceedings of the Sixth Annual International Conference on Computational Biology, pages 100–108. ACM Press, 2002. 5. F. Corpet and B. Michot. RNAlign program: alignment of RNA sequences using both primary and secondary structures. CABIOS, 10(4):389–399, 1994. 6. S. Eddy and R. Durbin. RNA sequence analysis using covariance models. Nucleic Acids Research, 22(11):2079–2088, 1994. 7. P. A. Evans. Finding common subsequences with arcs and pseudoknots. In M. Crochemore and M. Patterson, editors, Proc. Combinatorial Pattern Matching (CPM’99), volume 1645 of LNCS, pages 270–280. Springer, 1999. 8. J. Gorodkin, L. J. Heyer, and G. D. Stormo. Finding the most significant common sequence and structure motifs in a set of RNA sequences. Nucl. Acids Res., 25:3724–3732, 1997. 9. M. Held and R. Karp. The traveling-salesman problem and minimum spanning trees: Part II. Mathematical Programming, 1:6–25, 1971. 10. I. L. Hofacker, S. H. F. Bernhart, and P. F. Stadler. Alignment of RNA base pairing probability matrices. Bioinformatics, 2004. In press.
Structural Alignment of Two RNA Sequences with Lagrangian Relaxation
123
11. H.-P. Lenhof, K. Reinert, and M. Vingron. A Polyhedral Approach to RNA Sequence Structure Alignment. Journal of Comp. Biology, 5(3):517–530, 1998. 12. D. H. Mathews and D. H. Turner. Dynalign: An algorithm for finding secondary structures common to two RNA sequences. J. Mol. Biol., 317:191–203, 2002. 13. J. S. McCaskill. The Equilibrium Partition Function and Base Pair Binding Probabilities for RNA Secondary Structure. Biopolymers, 29:1105–1119, 1990. 14. B. Poljak. A general method of solving extremum problems. Soviet Mathematics Doklady, 8:593–597, 1967. 15. D. Sankoff. Simultaneous solution of the RNA folding, alignment, and protosequence problems. SIAM J. Appl. Math., 45:810–825, 1985. 16. M. Waterman. Consensus methods for folding single-stranded nucleic adds. Mathematical Methods for DNA Sequences, pages 185–224, 1989. 17. J. Wuyts, Y. Van de Peer, T. Winkelmans, and R. De Wachter. The European database on small subunit ribosomal RNA. Nucleic Acids Res, 30:183–185, 2002.
Poly-APX- and PTAS-Completeness in Standard and Differential Approximation (Extended Abstract) Cristina Bazgan, Bruno Escoffier, and Vangelis Th. Paschos LAMSADE, Université Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75775 Paris Cedex 16, France {bazgan, escoffier, paschos}@lamsade.dauphine.fr
Abstract. We first prove the existence of natural Poly-APX-complete problems, for both standard and differential approximation paradigms, under already defined and studied suitable approximation preserving reductions. Next, we devise new approximation preserving reductions, called FT and DFT, respectively, and prove that, under these reductions, natural problems are PTAS-complete, always for both standard and differential approximation paradigms. To our knowledge, no natural problem was known to be PTAS-complete and no problem was known to be Poly-APX-complete until now. We also deal with the existence of intermediate problems under FT- and DFT-reductions and we show that such problems exist provided that there exist NPO-intermediate problems under Turing-reduction. Finally, we show that MIN COLORING is APX-complete for the differential approximation.
1
Introduction
Many NP-complete problems are decision versions of natural optimization problems. Since, unless P = NP, such problems cannot be solved in polynomial time, a major question is to find polynomial algorithms producing solutions “close to the optimum” (in some pre-specified sense). Here, we deal with polynomial approximation of NPO problems (see [1] for a formal definition), i.e., of optimization problems the decision versions of which are in NP. As usual, we deal with problems the solution-values (or objective values) of which are integer. For a problem in NPO, we distinguish three different versions of it: in the constructive version denoted also by the goal is to determine the best solution of an instance in the evaluation version we are only interested in determining the value of finally, the decision version is as dealt in [2]. A polynomial approximation algorithm A for an optimization problem is a polynomial time algorithm that produces, for any instance of a feasible solution The quality of is estimated by computing the so-called approximation ratio. Two approximation ratios are commonly used in order to evaluate the approximation capacity of an algorithm: the standard ratio and the differential ratio. Given an instance of an optimization problem let R. Fleischer and G. Trippen (Eds.): ISAAC 2004, LNCS 3341, pp. 124–136, 2004. © Springer-Verlag Berlin Heidelberg 2004
Poly-APX- and PTAS-Completeness
125
be the value of an optimal solution, and be the value of a worst feasible solution. This value is the optimal value of the same optimization problem (with respect to the set of instances and the set of feasible solutions for any instance) defined with the opposite objective (minimize instead of maximize, and vice-versa) with respect to For a feasible solution of denote by its value. The standard approximation ratio of is defined as The differential approximation ratio of is defined as Following the above, standard approximation ratios for minimization problems are greater than, or equal to, 1, while for maximization problems these ratios are smaller than, or equal to 1. On the other hand, differential approximation ratio is always at most 1 for any problem. By means of approximation ratios, NPO problems are classified with respect to their approximability properties. Particularly interesting approximation classes are, for the standard approximation paradigm, the classes Poly-APX (the class of the problems approximated within a ratio that is a polynomial, or the inverse of a polynomial when dealing with maximization problems, on the size of the instance), APX (the class of constant-approximable problems), PTAS (the class of problems admitting polynomial time approximation schemata) and FPTAS (the class of problems admitting fully polynomial time approximation schemata). We are referr