Complexity Analysis of someProblems in Planar Graphs, Bounded Tree-Width Graphs, and Planar Point Sets[HBNI Th27]

Prajakta Nimbhorkar

Complexity Analysis of someProblems in Planar Graphs, Bounded Tree-Width Graphs, and Planar Point Sets[HBNI Th27]

Prajakta Nimbhorkar

Advisor: Meena Mahajan

Degree: Ph.D

Main Subject: Computer Science

Institution: HBNI

Year: 2010

Pages: 102p.

URI: https://dspace.imsc.res.in/xmlui/handle/123456789/252

Date: 2011

xmlui.dri2xhtml.METS-1.0.item-relation-isbasedon: [1] Manindra Agrawal and V. Arvind. A note on decision versus search for graph automorphism. Information and Computation, 131(2):179–189, 1996. [2] Eric Allender. Making computation count: Arithmetic circuits in the nineties. In L. Hemaspaandra, editor, SIGACT News Complexity Theory Column, volume 28. ACM SIGACT,1997. [3] Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambuddha Roy. Planar and grid graph reachability problems. Theory of Computing Systems, 45:675– 723, 2009. [4] Eric Allender, Samir Datta, and Sambuddha Roy. The directed planar reachability problem. In Proc. 25th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 3821 of LNCS, pages 238–249., 2005. [5] Eric Allender and Meena Mahajan. The complexity of planarity testing. Information and Computation, 189(1):117–134, 2004. [6] Eric Allender, Klaus Reinhardt, and Shiyu Zhou. Isolation, matching and counting uniform and nonuniform upper bounds. Journal of Computer and System Sciences, 59(2):164–181, 1999. [7] Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. NP-hardness of Euclidean Sum-of-Squares Clustering. In Machine Learning, volume 75, pages 245–248, 2009. [8] S. Arora. Polynomial time approximation schemes for Euclidean tsp and other geometric problems. In FOCS ’96: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, page 2, 1996. [9] David Arthur and Sergei Vassilvitskii. How slow is the k-means method? In Proceedings of the 22nd anual Symposium on Computational Geometry (SoCG), pages 144–153, 2006. [10] David Arthur and Sergei Vassilvitskii. Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), pages 153–164, 2006. [11] David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1027–1035, 2007. [12] Michael Artin. Algebra. Prentice Hall, India, New Delhi, 1996. [13] V. Arvind, Bireswar Das, and Johannes Köbler. The Space Complexity of k-Tree Isomorphism. In Algorithms and Computation, 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007, Proceedings, volume 4835 of Lecture Notes in Computer Science, pages 822–833. Springer, 2007. [14] V. Arvind, Bireswar Das, and Johannes Köbler. A logspace algorithm for partial 2-tree canonization. In Computer Science Symposium in Russia (CSR), pages 40–51, 2008. [15] V. Arvind and Nikhil Devanur. Symmetry breaking in trees and planar graphs by vertex coloring. In The Nordic Combinatorial Conference (NORCOM), 2004. [16] V. Arvind and Piyush P. Kurur. Graph isomorphism is in SPP. Information and Computation, 204(5):835–852, 2006. [17] V. Arvind, Piyush P. Kurur, and T. C. Vijayaraghavan. Bounded color multiplicity graph isomorphism is in the #l hierarchy. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC), pages 13–27, 2005. [18] László Babai. Moderately exponential bound for graph isomorphism. In FCT ’81: Proceedings of the 1981 International FCT-Conference on Fundamentals of Computation Theory, pages 34–50. Springer-Verlag, 1981. [19] László Babai. Automorphism groups, isomorphism, reconstruction. Handbook of combinatorics, 2:1447–1540, 1995. [20] László Babai, Paul Erdös, and Stanley M. Selkow. Random graph isomorphism. SIAM J. Comput., 9(3):628–635, 1980. [21] Laszlo Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In SFCS ’79: Proceedings of the 20th Annual Symposium on Foundations of Computer Science, pages 39–46, 1979. [22] László Babai and Eugene M. Luks. Canonical labeling of graphs. In Proceedings of the fifteenth annual ACM Symposium on Theory of Computing (STOC), pages 171–183, 1983. [23] Michael Ben-or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. Comput., 21(1):54–58, 1992. [24] Ravi B. Boppana, Johan Hastad, and Stathis Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25(2):127–132, 1987. [25] Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Transactions on Computation Theory, 1(1):1–17, 2009. [26] Burchard von Braunmühl and Rutger Verbeek. Input driven languages are recognized in log n space. In Selected papers of the international conference on "foundations of computation theory" on Topics in the theory of computation, pages 1–19, 1985. [27] Gerhard Buntrock, Birgit Jenner, Klaus-Jörn Lange, and Peter Rossmanith. Unambiguity and fewness for logarithmic space. In Proc. 8th International Symposium on Fundamentals of Computation Theory (FCT), volume 529 of LNCS, pages 168–179, 1991. [28] S. Buss, S. Cook, A. Gupta, and V. Ramachandran. An optimal parallel algorithm for formula evaluation. SIAM J. Comput., 21(4):755–780, 1992. [29] Samuel R. Buss. Alogtime algorithms for tree isomorphism, comparison, and canonization. In Proceedings of the 5th Kurt Gödel Colloquium on Computational Logic and Proof Theory, pages 18–33, 1997. [30] A. Chiu, G. Davida, and B. Litow. Division in logspace-uniform NC1. Theoretical Informatics and Applications, 35:259–275, 2001. [31] Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted space algorithms for isomorphism on bounded treewidth graphs. In Proceedings of 27th International Symposium on Theoretical Aspects of Computer Science (To appear), 2010. [32] Sanjoy Dasgupta. The hardness of k-means clustering. Technical Report CS2007-0890, University of California, San Diego, 2007. [33] Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Graph isomorphism for K3,3-free and K5-free graphs is in log-space. In Proc. of 29th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 4 of Leibniz International Proceedings in Informatics (LIPIcs), pages 145–156, 2009. [34] W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In Proceedings of the 35th annual ACM Symposium on Theory of Computing (STOC), pages 50–58, 2003. [35] Petros Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, and V. Vinay. Clustering large graphs via the singular value decomposition. In Machine Learning, volume 56, pages 9–33, 2004. [36] Kousha Etessami. Counting quantifiers, successor relations, and logarithmic space. Journal of Computer and System Sciences, 54(3):400–411, 1997. [37] Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi Varadarajan. On clustering to minimize the sum of radii. In Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 819–825, 2008. [38] John G. Del Greco, N. Chandrasekharan, and R. Sridhar. Fast parallel reordering and isomorphism testing of k-trees. Algorithmica, 32(1):61–72, 2002. [39] Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In 33rd International Colloquium on Automata, Languages and Programming (ICALP), volume 4051 of LNCS, pages 3–14, 2006. [40] Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski, and Prabhakar Ragde. Embeddings of k -connected graphs of pathwidth k. Discrete Applied Mathematics, 145(2):242– 265, 2005. [41] Sariel Har-Peled and Bardia Sadri. How fast is the k-means method? In Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 877–885, 2005. [42] Frank Harary and E. M. Palmer. On acyclic simplicial complexes. Mathematica, 15:115– 122, 1968. [43] William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65(4):695–716, 2002. [44] John E. Hopcroft and Robert Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549–568, 1974. [45] John E. Hopcroft and Robert E. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing, 2(3):135–158, 1973. [46] John E. Hopcroft and J.K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the 6th annual ACM Symposium on Theory of Computing (STOC), pages 172–184, 1974. [47] Mary Inaba, Naoki Katoh, and Hiroshi Imai. Applications of weighted Voronoi diagrams and randomization to variance-based clustering. In Proceedings of the 10th annual Symposium on Computational Geometry (SCG), pages 332–339, 1994. [48] Andreas Jakoby and Till Tantau. Computing shortest paths in series-parallel graphs in logarithmic space. In Complexity of Boolean Functions, number 06111 in Dagstuhl Seminar Proceedings, 2006. http://drops.dagstuhl.de/opus/volltexte/2006/618. [49] Andreas Jakoby and Till Tantau. Logspace algorithms for computing shortest and longest paths in series-parallel graphs. In Proc. 27th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 4855 of LNCS, pages 216–227, 2007. see also [48]. [50] Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán. Completeness results for graph isomorphism. Journal of Computing and System Sciences, 66(3):549–566, 2003. [51] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. In Proceedings of the 18th annual Symposium on Computational Geometry (SCG), volume 28, pages 89–112, 2004. [52] M. M. Klawe, D. G. Corneil, and A. Proskurowski. Isomorphism testing in hookup classes. SIAM Journal on Algebraic and Discrete Methods, 3(2):260–274, 1982. [53] Johannes Köbler and Sebastian Kuhnert. The isomorphism problem for k-trees is complete for logspace. In Proceedings of Mathematical Foundations of Computer Science (MFCS), volume 5734 of LNCS, pages 537–548, 2009. [54] Johannes Köbler, Uwe Schöning, and Jacobo Torán. The Graph Isomorphism Problem: its structural complexity. Birkhäuser, 1993. [55] Michal Koucký. Universal traversal sequences with backtracking. Journal of Computing and System Sciences,65(4):717–726, 2002. [56] Jacek P. Kukluk, Lawrence B. Holder, and Diane J. Cook. Algorithm and experiments in testing planar graphs for isomorphism. Journal of Graph Algorithms and Applications, 8(2):313–356, 2004. [57] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A simple linear time (1 + ϵ) approximation algorithm for k-means clustering in any dimensions. In Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 454–462, 2004. [58] Klaus-Jörn Lange. Complexity and structure in formal language theory. Fundamenta Informaticae, 25(3-4):327–352, 1996. [59] Charles E. Leiserson. Area-efficient graph layouts (for VLSI). In Proceedings of the 21st annual IEEE Symposium on Foundations of Computer Science (SFCS), pages 270–281, 1980. [60] David Lichtenstein. Planar formulae and their uses. SIAM Journal on Computing, 11:329– 343, 1982. [61] Nutan Limaye, Meena Mahajan, and B. V. Raghavendra Rao. Arithmetizing classes around NC1 and L. Theory of Computing Systems, special issue for STACS 2007, 46(3):499–522, 2010. [62] Steven Lindell. A logspace algorithm for tree canonization (extended abstract). In Proceedings of the 24th annual ACM Symposium on Theory of Computing (STOC), pages 400–404, 1992. [63] Stuart P. Lloyd. Least squares quantization in pcm. In IEEE Transactions on Information Theory, volume 28, pages 129–136, 1982. [64] László Lovász. An algorithmic theory of numbers, graphs, and convexity. CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, 1986. [65] Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25:42–65, 1982. [66] Eugene M. Luks. Parallel algorithms for permutation groups and graph isomorphism. In SFCS ’86: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 292–302, 1986. [67] Saunders Maclane. A structural characterization of planar combinatorial graphs. Duke Mathematical Journal, 3:460–472, 1937. [68] R. Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8:131–132, 1979. [69] Pierre McKenzie, Birgit Jenner, and Jacobo Torán. A note on the hardness of tree isomorphism. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity (CCC), page 101, 1998. [70] Nimrod Megiddo and Kenneth J. Supowit. On the complexity of some common geometric location problems. SIAM Journal on Computing, 13:182–196, 1984. [71] Gary Miller. Isomorphism testing for graphs of bounded genus. In STOC ’80: Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 225–235, 1980. [72] Gary L. Miller and John H. Reif. Parallel tree contraction part 2: further applications. SIAM Journal on Computing, 20(6):1128–1147, 1991. [73] Noam Nisan and Amnon Ta-Shma. Symmetric logspace is closed under complement. Chicago Journal of Theoretical Computer Science, 1995. [74] Rafail Ostrovsky, Yuval Rabani, Leonard Schulman, and Chaitanya Swamy. The effectiveness of Lloyd-type methods for the k-means problem. In Proceedings of the 47th annual IEEE Symposium on Foundations of Computer Science, pages 165–176, 2006. [75] Ilia N. Ponomarenko. The isomorphism problem for classes of graphs closed under contraction. Journal of Mathematical Sciences (JSM, formerly Journal of Soviet Mathematics), 55, 1991. [76] Vijaya Ramachandran and John H. Reif. Planarity testing in parallel. Journal of Computer and System Sciences, 49:517–561, 1994. [77] Omer Reingold. Undirected connectivity in log-space. Journal of ACM, 55(4), 2008. [78] Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM Journal of Computing, 29(4):1118–1131, 2000. [79] Neil Robertson and P. D. Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49 – 64, 1984. [80] Uwe Schöning. Graph isomorphism is in the low hierarchy. Journal on Computing and System Sciences, 37(3):312–323, 1988. [81] Derrick Stolee, Chris Bourke, and N. V. Vinodchandran. A log-space algorithm for reachability in planar DAGs with few sources. In Proceedings of the 25th Conference on Computational Complexity, 2010 (To appear). [82] I. Sudborough. On the tape complexity of deterministic context-free language. Journal of Association of Computing Machinery, 25(3):405–414, 1978. [83] Till Tantau. Logspace optimization problems and their approximability properties. Theory of Computing Systems, 41(2):327–350, 2007. [84] Thomas Thierauf and Fabian Wagner. The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. In Proc. Symposium on Theoretical Aspects of Computer Science (STACS), volume 08001 of Dagstuhl Seminar Proceedings, pages 633–644, 2008. [85] Thomas Thierauf and Fabian Wagner. Reachability in K3;3-free graphs and K5-free graphs is in unambiguous log-space. In Fundamentals of Computation Theory (FCT), volume 5699 of LNCS, pages 323–334, 2009. [86] Jacobo Torán. On the hardness of graph isomorphism. SIAM Journal on Computing, 33(5):1093–1108, 2004. [87] Leslie G. Valiant. Universality considerations in vlsi circuits. In IEEE Transactions on Computers, volume 30, pages 135–140, 1981. [88] Andrea Vattani. The hardness of k-means clustering in the plane. manuscript, 2009. [89] Oleg Verbitsky. Planar graphs: Logical complexity and parallel isomorphism tests. In 24th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 682–693, 2007. [90] FabianWagner. Hardness results for tournament isomorphism and automorphism. In 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 572–583, 2007. [91] Egon Wanke. Bounded tree-width and LOGCFL. Journal of Algorithms, 16(3):470–491, 1994. [92] Louis Weinberg. A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. Circuit Theory, 13:142–148, 1966. [93] Hassler Whitney. A set of topological invariants for graphs. American Journal of Mathematics, 55:235–321, 1933. 102

Abstract:

The focus of this thesis is on the complexity analysis of some computational problems in restricted graph-classes. The problems considered include graph isomorphism, various path problems like reachability, shortest path, and longest path computations. We investigate the space complexity of the graph isomorphism problem for planar graphs. The space complexity of path problems is considered for planar graphs, and k-trees. Another problem studied in the thesis is the clustering problem. One of the main results on graph isomorphism included in the thesis is a log-space algorithm for isomorphism of planar graphs. This settles the complexity of planar graph isomorphism, since hardness for log-space is already known. A log-space algorithm is first described for isomorphism of 3-connected planar graphs, which is then used in the algorithm for planar graph isomorphism. The results on path problems include an improved upper bound for computing the length of a longest path between two designated nodes in a planar DAG. We also present new upper bounds for counting the number of paths between two designated nodes in a planar DAG and in a single-sink DAG, under the promise that these numbers are bounded by a polynomial in the size of the graph. Reachability problem is also studied for directed k-trees and a log-space algorithm is given. Complexity of the shortest and longest path problems for directed acyclic k-trees has been analysed and log-space algorithms are described for these problems. We also give matching log-space hardness results, thereby settling the complexity of these problems for directed k-trees and directed acyclic k-trees respectively. These algorithms are applicable for partial k-trees, which are also known as graphs of tree-width at most k, provided a tree-decomposition for partial k-trees is given as input. The tree-decomposition for k-trees is known to be computable in log-space, but is not known for partial k-trees. Another problem studied in this thesis is the k-means problem. It is a variant of the clustering problem. We prove that the k-means problem is NP-hard when the input is a set of points in two dimensions, and k is part of input. Earlier the hardness was known only for those instances where the number of dimensions is a part of input.

Show full item record