Log-space algorithms for paths and matchings in \(k\)-trees. (English) Zbl 1281.68132
Summary: Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2. In this paper, we improve these bounds for \(k\)-trees, where \(k\) is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed \(k\)-trees, and for computation of shortest and longest paths in directed acyclic \(k\)-trees.
Besides the path problems mentioned above, we also consider the problem of deciding whether a \(k\)-tree has a perfect matching (decision version), and if so, finding a perfect matching (search version), and prove that these two problems are L-complete. These problems are known to be in P and in RNC for general graphs, and in SPL for planar bipartite graphs, as shown in [S. Datta et al., Theory Comput. Syst. 47, No. 3, 737–757 (2010; Zbl 1206.68231)].
Our results settle the complexity of these problems for the class of \(k\)-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of the divide-and-conquer approach in log-space, along with some ideas from [A. Jakoby and T. Tantau, “Logspace algorithms for computing shortest and longest paths in series-parallel graphs”, in: Proceedings of the 27th annual conference on foundations of software technology and theoretical computer science, of FSTTCS 2007. Berlin: Springer. 216–227 (2007); N. Limaye et al., Theory Comput. Syst. 46, No. 3, 499–522 (2010; Zbl 1204.68098)].
Besides the path problems mentioned above, we also consider the problem of deciding whether a \(k\)-tree has a perfect matching (decision version), and if so, finding a perfect matching (search version), and prove that these two problems are L-complete. These problems are known to be in P and in RNC for general graphs, and in SPL for planar bipartite graphs, as shown in [S. Datta et al., Theory Comput. Syst. 47, No. 3, 737–757 (2010; Zbl 1206.68231)].
Our results settle the complexity of these problems for the class of \(k\)-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of the divide-and-conquer approach in log-space, along with some ideas from [A. Jakoby and T. Tantau, “Logspace algorithms for computing shortest and longest paths in series-parallel graphs”, in: Proceedings of the 27th annual conference on foundations of software technology and theoretical computer science, of FSTTCS 2007. Berlin: Springer. 216–227 (2007); N. Limaye et al., Theory Comput. Syst. 46, No. 3, 499–522 (2010; Zbl 1204.68098)].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C05 | Trees |
References:
| [1] | Allender, E.: Making computation count: arithmetic circuits in the nineties. SIGACT News 28(4), 2-15 (1997) · doi:10.1145/270563.270564 |
| [2] | Allender, E., Barrington, D.A.M., Chakraborty, T., Datta, S., Roy, S.: Planar and grid graph reachability problems. Theory Comput. Syst. 45(4), 675-723 (2009) · Zbl 1183.68409 · doi:10.1007/s00224-009-9172-z |
| [3] | Arvind, V.; Das, B.; Köbler, J., The space complexity of k-tree isomorphism, No. 4835, 822-833 (2007), Berlin · Zbl 1193.68124 · doi:10.1007/978-3-540-77120-3_71 |
| [4] | Ben-Or, M., Cleve, R.: Computing algebraic formulas using a constant number of registers. SIAM J. Comput. 21(1), 54-58 (1992) · Zbl 0743.68062 · doi:10.1137/0221006 |
| [5] | Braunmühl, B. V.; Verbeek, R., Input driven languages are recognized in logn space, No. 102, 1-19 (1985), Amsterdam · Zbl 0555.68046 |
| [6] | Braverman, M.; Kulkarni, R.; Roy, S., Parity problems in planar graphs, 222-235 (2007) |
| [7] | Buss, S., Cook, S., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM J. Comput. 21(4), 755-780 (1992) · Zbl 0825.68424 · doi:10.1137/0221046 |
| [8] | Chandrasekharan, N.; Hannenhalli, S., Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs, 42-45 (1992) · doi:10.1109/ICCI.1992.227709 |
| [9] | Chiu, A., Davida, G., Litow, B.: Division in logspace-uniform NC1. RAIRO Theor. Inform. Appl. 35, 259-275 (2001) · Zbl 1014.68062 · doi:10.1051/ita:2001119 |
| [10] | Datta, S., Roy, S.: A note on matching problems complete for logspace classes (2005, unpublished short) · Zbl 0157.54903 |
| [11] | Datta, S.; Kulkarni, R.; Limaye, N.; Mahajan, M., Planarity, determinants, permanents, and (unique) matchings, No. 4649, 115-126 (2007), Berlin · Zbl 1188.68151 |
| [12] | Datta, S., Kulkarni, R., Roy, S.: Deterministically isolating a perfect matching in bipartite planar graphs. Theory Comput. Syst. 47, 737-757 (2010) · Zbl 1206.68231 · doi:10.1007/s00224-009-9204-8 |
| [13] | Elberfeld, M.; Jakoby, A.; Tantau, T., Logspace versions of the theorems of Bodlaender and Courcelle, 143-152 (2010) · doi:10.1109/FOCS.2010.21 |
| [14] | Etessami, K.: Counting quantifiers, successor relations, and logarithmic space. J. Comput. Syst. Sci. 54(3), 400-411 (1997) · Zbl 0882.68074 · doi:10.1006/jcss.1997.1485 |
| [15] | Flarup, U.; Koiran, P.; Lyaudet, L., On the expressive power of planar perfect matching and permanents of bounded treewidth matrices, 124-136 (2007), Berlin · Zbl 1141.68418 · doi:10.1007/978-3-540-77120-3_13 |
| [16] | Greco, J.G.D., Chandrasekharan, N., Sridhar, R.: Fast parallel reordering and isomorphism testing of k-trees. Algorithmica 32(1), 61-72 (2002) · Zbl 0995.68194 · doi:10.1007/s00453-001-0052-4 |
| [17] | Gupta, A., Nishimura, N., Proskurowski, A., Ragde, P.: Embeddings of k-connected graphs of pathwidth k. Discrete Appl. Math. 145(2), 242-265 (2005) · Zbl 1055.05143 · doi:10.1016/j.dam.2002.12.005 |
| [18] | Harary, F., Palmer, E.M.: On acyclic simplicial complexes. Mathematika 15, 115-122 (1968) · Zbl 0157.54903 · doi:10.1112/S002557930000245X |
| [19] | Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65(4), 695-716 (2002) · Zbl 1059.68044 · doi:10.1016/S0022-0000(02)00025-9 |
| [20] | Hoang, T. M.; Mahajan, M.; Thierauf, T., On the bipartite unique perfect matching problem, 453-464 (2006), Berlin · Zbl 1223.68057 · doi:10.1007/11786986_40 |
| [21] | Jakoby, A.; Tantau, T., Logspace algorithms for computing shortest and longest paths in series-parallel graphs, No. 4855, 216-227 (2007), Berlin · Zbl 1135.68518 |
| [22] | Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica 6(1), 35-48 (1986) · Zbl 0646.05051 · doi:10.1007/BF02579407 |
| [23] | Köbler, J.; Kuhnert, S., The isomorphism problem for k-trees is complete for logspace, No. 5734, 537-548 (2009), Berlin · Zbl 1250.68120 |
| [24] | Limaye, N., Mahajan, M., Nimbhorkar, P.: Longest paths in planar DAGs in unambiguous log-space. Chic. J. Theor. Comput. Sci. 2010(8), 1-16 (2010). CATS 2009 special issue · Zbl 1286.68240 · doi:10.4086/cjtcs.2010.008 |
| [25] | Limaye, N., Mahajan, M., Rao, B.V.R.: Arithmetizing classes around NC1 and L. Theory Comput. Syst. 46(3), 499-522 (2010). Special issue for STACS 2007 · Zbl 1204.68098 · doi:10.1007/s00224-009-9233-3 |
| [26] | Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105-113 (1987) · Zbl 0632.68041 · doi:10.1007/BF02579206 |
| [27] | Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17 (2008) · Zbl 1315.68156 · doi:10.1145/1391289.1391291 |
| [28] | Reinhardt, K., Allender, E.: Making nondeterminism unambiguous. SIAM J. Comput. 29(4), 1118-1131 (2000) · Zbl 0947.68063 · doi:10.1137/S0097539798339041 |
| [29] | Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory, Ser. B 36(1), 49-64 (1984) · Zbl 0548.05025 · doi:10.1016/0095-8956(84)90013-3 |
| [30] | Thierauf, T.; Wagner, F., Reachability in K3,3-free graphs and K5-free graphs is in unambiguous log-space, No. 5699, 323-334 (2009), Berlin · Zbl 1252.68214 · doi:10.1007/978-3-642-03409-1_29 |
| [31] | Wanke, E.: Bounded tree-width and LOGCFL. J. Algorithms 16(3), 470-491 (1994) · Zbl 0804.68048 · doi:10.1006/jagm.1994.1022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
