Solving the canonical representation and star system problems for proper circular-arc graphs in logspace. (English) Zbl 1355.68124
Summary: We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where canonical means that isomorphic graphs receive identical models. This implies that the recognition and the isomorphism problems for these graphs are solvable in logspace. For the broader class of concave-round graphs, which still possess (not necessarily proper) circular-arc models, we show that a canonical circular-arc model can also be constructed in logspace. As a building block for these results, we design a logspace algorithm for computing canonical circular-arc models of circular-arc hypergraphs. This class of hypergraphs corresponds to matrices with the circular ones property, which play an important role in computational genomics. Our results imply that there is a logspace algorithm that decides whether a given matrix has this property.
Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.
Note that solving a problem in logspace implies that it is solvable by a parallel algorithm of the class \(\mathsf{AC}^{1}\). For the problems under consideration, at most \(\mathsf{AC}^{2}\) algorithms were known earlier.
Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.
Note that solving a problem in logspace implies that it is solvable by a parallel algorithm of the class \(\mathsf{AC}^{1}\). For the problems under consideration, at most \(\mathsf{AC}^{2}\) algorithms were known earlier.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Aigner, M.; Triesch, E., Reconstructing a graph from its neighborhood lists, Comb. Probab. Comput., 2, 103-113 (1993) · Zbl 0792.05104 |
| [2] | Annexstein, F. S.; Swaminathan, R. P., On testing consecutive-ones property in parallel, Discrete Appl. Math., 88, 1-3, 7-28 (1998) · Zbl 0936.68111 |
| [3] | Bang-Jensen, J.; Huang, J.; Yeo, A., Convex-round and concave-round graphs, SIAM J. Discrete Math., 13, 2, 179-193 (2000) · Zbl 0941.05056 |
| [4] | Booth, K.; Lueker, G., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci., 13, 3, 335-379 (1976) · Zbl 0367.68034 |
| [5] | Boros, E.; Gurvich, V.; Zverovich, I. E., Neighborhood hypergraphs of bipartite graphs, J. Graph Theory, 58, 1, 69-95 (2008) · Zbl 1167.05041 |
| [6] | Chen, L., Efficient parallel recognition of some circular arc graphs, I, Algorithmica, 9, 3, 217-238 (1993) · Zbl 0768.68127 |
| [7] | Chen, L., Graph isomorphism and identification matrices: parallel algorithms, IEEE Trans. Parallel Distrib. Syst., 7, 3, 308-319 (1996) |
| [8] | Chen, L., Efficient parallel recognition of some circular arc graphs, II, Algorithmica, 17, 3, 266-280 (1997) · Zbl 0865.68092 |
| [9] | Chen, L.; Yesha, Y., Parallel recognition of the consecutive ones property with applications, J. Algorithms, 12, 3, 375-392 (1991) · Zbl 0726.68034 |
| [10] | Curtis, A. R.; Lin, M. C.; McConnell, R. M.; Nussbaum, Y.; Soulignac, F. J.; Spinrad, J. P.; Szwarcfiter, J. L., Isomorphism of graph classes related to the circular-ones property, Discret. Math. Theor. Comput. Sci., 15, 1, 157-182 (2013) · Zbl 1283.05172 |
| [11] | Deng, X.; Hell, P.; Huang, J., Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs, SIAM J. Comput., 25, 2, 390-403 (1996) · Zbl 0858.05094 |
| [12] | Diestel, R., Graph Theory (2010), Springer: Springer Berlin · Zbl 1204.05001 |
| [13] | Fomin, F. V.; Kratochvíl, J.; Lokshtanov, D.; Mancini, F.; Telle, J. A., On the complexity of reconstructing \(H\)-free graphs from their Star Systems, J. Graph Theory, 68, 2, 113-124 (2011) · Zbl 1230.05215 |
| [14] | Gavril, F.; Pinter, R. Y.; Zaks, S., Intersection representations of matrices by subtrees and unicycles on graphs, J. Discret. Algorithms, 6, 2, 216-228 (2008) · Zbl 1146.05033 |
| [15] | Hell, P.; Huang, J., Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs, J. Algorithms, 20, 3, 361-374 (1995) · Zbl 0835.05064 |
| [16] | Hsu, W. L., \(O(MN)\) algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput., 24, 3, 411-439 (1995) · Zbl 0831.68051 |
| [17] | Hsu, W. L., A simple test for the consecutive ones property, J. Algorithms, 43, 1, 1-16 (2002) · Zbl 1050.68164 |
| [18] | Hsu, W. L.; McConnell, R. M., PC trees and circular-ones arrangements, Theor. Comput. Sci., 296, 1, 99-116 (2003) · Zbl 1044.68125 |
| [19] | Huang, J., On the structure of local tournaments, J. Comb. Theory, 24, 3, 411-439 (1995) |
| [20] | Kaplan, H.; Nussbaum, Y., Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs, Discrete Appl. Math., 157, 15, 3216-3230 (2009) · Zbl 1213.05248 |
| [21] | Köbler, J.; Kuhnert, S.; Laubner, B.; Verbitsky, O., Interval graphs: canonical representations in logspace, SIAM J. Comput., 40, 5, 1292-1315 (2011) · Zbl 1235.05140 |
| [22] | Köbler, J.; Kuhnert, S.; Verbitsky, O., Around and beyond the isomorphism problem for interval graphs, Bull. Eur. Assoc. Theor. Comput. Sci., 107, 44-71 (2012) · Zbl 1394.68187 |
| [23] | Köbler, J.; Kuhnert, S.; Verbitsky, O., Solving the canonical representation and star system problems for proper circular-arc graphs in logspace, (Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 18 (2012), Leibniz-Zentrum für Informatik, Dagstuhl), 387-399 · Zbl 1354.68125 |
| [24] | Köbler, J.; Kuhnert, S.; Verbitsky, O., Circular-arc hypergraphs: rigidity via connectedness (2013), E-print: |
| [25] | Lalonde, F., Le probleme d’etoiles pour graphes est NP-complet, Discrete Math., 33, 3, 271-280 (1981) · Zbl 0458.68025 |
| [26] | Liang, Y. D.; Blum, N., Circular convex bipartite graphs: maximum matching and Hamiltonian circuits, Inf. Process. Lett., 56, 4, 215-219 (1995) · Zbl 0875.68698 |
| [27] | Lin, M. C.; Soulignac, F. J.; Szwarcfiter, J. L., A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs, (Gudmundsson, J., Proceedings of the 11th Scandinavian Workshop on Algorithm Theory. Proceedings of the 11th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, vol. 5124 (2008), Springer), 355-366 · Zbl 1155.05339 |
| [28] | Lin, M. C.; Szwarcfiter, J. L., Unit circular-arc graph representations and feasible circulations, SIAM J. Discrete Math., 22, 1, 409-423 (2008) · Zbl 1232.05145 |
| [29] | Lueker, G.; Booth, K., A linear time algorithm for deciding interval graph isomorphism, J. ACM, 26, 2, 183-195 (1979) · Zbl 0402.68050 |
| [30] | McConnell, R. M., Linear-time recognition of circular-arc graphs, Algorithmica, 37, 2, 93-147 (2003) · Zbl 1060.68088 |
| [31] | Ouangraoua, A.; Bergeron, A.; Swenson, K. M., Theory and practice of ultra-perfection, J. Comput. Biol., 18, 9, 1219-1230 (2011) |
| [32] | Reingold, O., Undirected connectivity in log-space, J. ACM, 55, 4 (2008) · Zbl 1315.68156 |
| [33] | Roberts, F. S., On the compatibility between a graph and a simple order, J. Comb. Theory, Ser. B, 11, 1, 28-38 (1971) · Zbl 0177.27003 |
| [34] | Skrien, D. J., A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs, J. Graph Theory, 6, 3, 309-316 (1982) · Zbl 0495.05027 |
| [35] | Soulignac, F. J., Minimal and short representations of unit interval and unit circular-arc graphs (2014), E-print: |
| [36] | Soulignac, F. J., Fully dynamic recognition of proper circular-arc graphs, Algorithmica, 71, 4, 904-968 (2015) · Zbl 1323.05125 |
| [37] | Spinrad, J. P., Efficient Graph Representations, Field Institute Monographs, vol. 19 (2003), AMS · Zbl 1033.05001 |
| [38] | Tucker, A., Matrix characterizations of circular-arc graphs, Pac. J. Math., 39, 535-545 (1971) · Zbl 0226.05125 |
| [39] | Tucker, A., Structure theorems for some circular-arc graphs, Discrete Math., 7, 167-195 (1974) · Zbl 0269.05119 |
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.
