Maximum Exploratory Equivalence in Trees

• Autorzy: Luka Fürst , Uroš Cibej , Jurij Mihelicˇ
• Języki publikacji: EN

Abstrakty

EN

Many practical problems are modeled with networks and graphs. Their exploration is of significant importance, and several graph-exploration algorithms already exist. In this paper, we focus on a type of vertex equivalence, called exploratory equivalence, which has a great potential to speed up such algorithms. It is an equivalence based on graph automorphisms and can, for example, help us in solving the subgraph isomorphism problem, which is a well-known NP-hard problem. In particular, if a given pattern graph has nontrivial automorphisms, then each of its nontrivial exploratory equivalent classes gives rise to a set of constraints to prune the search space of solutions. In the paper, we define the maximum exploratory equivalence problem. We show that the defined problem is at least as hard the graph isomorphism problem. Additionally, we present a polynomial-time algorithm for solving the problem when the input is restricted to tree graphs. Furthermore, we show that for trees, a maximum exploratory equivalent partition leads to a globally optimal set of subgraph isomorphism constraints, whereas this is not necessarily the case for general graphs. (original abstract)

Słowa kluczowe

EN

Algorithms; Isomorphism

PL

Algorytmy; Izomorfizm

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 507--518

Twórcy

autor

Luka Fürst

• University of Ljubljana, Slovenia

autor

Uroš Cibej

• University of Ljubljana, Slovenia

autor

Jurij Mihelicˇ

• University of Ljubljana, Slovenia

Bibliografia

• J. Leskovec and E. Horvitz, "Geospatial structure of a planetary-scale social network," IEEE Transactions on Computational Social Systems, vol. 1, no. 3, pp. 156-163, 2014. doi: 10.1109/TCSS.2014.2377789
• D. K. Agrafiotis, V. S. Lobanov, M. Shemanarev, D. N. Rassokhin, S. Izrailev, E. P. Jaeger, S. Alex, and M. Farnum, "Efficient Substructure Searching of Large Chemical Libraries: The ABCD Chemical Cartridge," Journal of Chemical Information and Modeling, pp. 3113-3130, 2011. doi: 10.1021/ci200413e
• J. M. Barnard, "Substructure searching methods: Old and new," Journal of Chemical Information and Computer Sciences, vol. 33, no. 4, pp. 532-538, 1993. doi: 10.1021/ci00014a001
• M. O. Jackson, Social and Economic Networks. Princeton, NJ, USA: Princeton University Press, 2008. ISBN 0691134405, 9780691134406
• D. Knoke, Political Networks: The Structural Perspective, ser. Structural Analysis in the Social Sciences. Cambridge University Press, 1994. ISBN 9780521477628. [Online]. Available: http://books. google.si/books?id=9djTlBLaOccC
• B. Hopkins, "Kevin Bacon and graph theory," Problems, Resources, and Issues in Mathematics Undergraduate Studies (PRIMUS), vol. 14, no. 1, pp. 5-11, 2004. doi: 10.1080/10511970408984072
• L. D. Sailer, "Structural equivalence: Meaning and definition, computation and application," Social Networks, vol. 1, pp. 73-90, 1978. doi: 10.1016/0378-8733(78)90014-X
• M. G. Everett and S. P. Borgatti, "Regular equivalence: General theory," Journal of mathematical sociology, vol. 19, no. 1, pp. 29-52, 1994. doi: 10.1080/0022250X.1994.9990134
• J. Mihelic, L. Fürst, and U. Cibej, "Exploratory equivalence in graphs: ˇ Definition and algorithms," in Proceedings of the 2014 Federated Conference on Computer Science and Information Systems (FedCSIS), Warsaw, Poland, September 7-10, 2014, 2014. doi: 10.15439/2014F352 pp. 447-456.
• F. Margot, "Pruning by isomorphism in branch-and-cut," Mathematical Programming, vol. 94, pp. 71-90, 2002. doi: 10.1007/s10107-002-0358-2
• J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio, "Orbital branching," in Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings, 2007. doi: 10.1007/978-3-540-72792-7_9 pp. 104-118.
• D. Erwin and F. Harary, "Destroying automorphisms by fixing nodes," Discrete mathematics, vol. 306, pp. 3244-3252, 2006. doi: 10.1016/j.disc.2006.06.004
• R. Ladner, "On the structure of polynomial time reducibility," Journal of the ACM, vol. 22, pp. 155-171, 1975. doi: 10.1145/321864.321877
• B. D. McKay, "Practical graph isomorphism," in Congressus Numerantium 30: 10th Manitoba Conference on Numerical Mathematics and Computing, Winnipeg, Canada, 1980, 1981, p. 45-87.
• B. D. McKay and A. Piperno, "Practical graph isomorphism, II," Journal of Symbolic Computation, vol. 60, pp. 94-112, 2013. doi: 10.1016/j.jsc.2013.09.003
• T. Junttila and P. Kaski, "Engineering an efficient canonical labeling tool for large and sparse graphs," in Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, LA, USA, January 6, 2007, 2007. doi: 10.1137/1.9781611972870.13
• "Conflict propagation and component recursion for canonical labeling," in Theory and Practice of Algorithms in (Computer) Systems - First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011, Proceedings, ser. LNCS 6595. Springer, 2011. doi: 10.1007/978-3-642-19754-3_16 pp. 151-162.
• P. T. Darga, M. H. Liffiton, K. A. Sakallah, and I. L. Markov, "Exploiting structure in symmetry detection for CNF," in Proceedings of the 41st Design Automation Conference, DAC 2004, San Diego, CA, USA, June 7-11, 2004, 2004. doi: 10.1145/996566.996712 pp. 530-534.
• P. T. Darga, K. A. Sakallah, and I. L. Markov, "Faster symmetry discovery using sparsity of symmetries," in Proceedings of the 45th Design Automation Conference, DAC 2008, Anaheim, CA, USA, June 8-13, 2008, 2008. doi: 10.1145/1391469.1391509 pp. 149-154.
• H. Katebi, K. A. Sakallah, and I. L. Markov, "Symmetry and satisfiability: An update," in Theory and Applications of Satisfiability Testing - SAT 2010, 13th International Conference, Edinburgh, UK, July 11-14, 2010, Proceedings, ser. LNCS 6175. Springer, 2010. doi: 10.1007/978- 3-642-14186-7_11 pp. 113-127.
• M. N. Velev and R. E. Bryant, "Effective use of boolean satisfiability procedures in the formal verification of superscalar and VLIW microprocessors," in Proceedings of the 38th Design Automation Conference, DAC 2001, Las Vegas, NV, USA, June 18-22, 2001, 2001. doi: 10.1145/378239.378469 pp. 226-231.
• A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. ISBN 978-0201000290
• S. A. Cook, "The complexity of theorem-proving procedures," in Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (STOC), Shaker Heights, Ohio, USA, May 3-5, 1971, 1971. doi: 10.1145/800157.805047 pp. 151-158.
• S. Arora and B. Barak, Computational complexity: a modern approach. Cambridge University Press, 2009. ISBN 9780521424264
• F. V. Fomin and D. Kratsch, Exact Exponential Algorithms. Springer, 2011. ISBN 978-3-642-16532-0
• J. R. Ullmann, "An Algorithm for Subgraph Isomorphism," Journal of the ACM, vol. 23, pp. 31-42, 1976. doi: 10.1145/321921.321925
• L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, "A (sub)graph isomorphism algorithm for matching large graphs." IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367- 1372, 2004. doi: 10.1109/TPAMI.2004.75
• T. Hocevar and J. Demšar, "A combinatorial approach to graphlet ˇ counting," Bioinformatics, vol. 30, no. 4, pp. 559-565, 2014. doi: 10.1093/bioinformatics/btt717

Identyfikatory

DOI

10.15439/2015F329