Skip to main content

Research Repository

Advanced Search

Comparing universal covers in polynomial time

Fiala, J.; Paulusma, D.

Authors

J. Fiala



Contributors

Edward A. Hirsch
Editor

Alexander A. Razboro
Editor

Alexei Semenov
Editor

Anatol Slissenko
Editor

Abstract

The universal cover T G of a connected graph G is the unique (possible infinite) tree covering G, i.e., that allows a locally bijective homomorphism from T G to G. Universal covers have major applications in the area of distributed computing. It is well-known that if a graph G covers a graph H then their universal covers are isomorphic, and that the latter can be tested in polynomial time by checking if G and H share the same degree refinement matrix. We extend this result to locally injective and locally surjective homomorphisms by following a very different approach. Using linear programming techniques we design two polynomial time algorithms that check if there exists a locally injective or a locally surjective homomorphism, respectively, from a universal cover T G to a universal cover T H . This way we obtain two heuristics for testing the corresponding locally constrained graph homomorphisms. As a consequence, we have obtained a new polynomial time algorithm for testing (subgraph) isomorphism between universal covers, and for checking if there exists a role assignment (locally surjective homomorphism) from a given tree to an arbitrary fixed graph H.

Citation

Fiala, J., & Paulusma, D. (2008). Comparing universal covers in polynomial time. In E. A. Hirsch, A. A. Razboro, A. Semenov, & A. Slissenko (Eds.), Computer science – theory and applications, Third International Computer Science Symposium in Russia, CSR 2008, 7-12 June 2008, Moscow, Russia ; proceedings (158-167). https://doi.org/10.1007/978-3-540-79709-8_18

Conference Name 3rd International Computer Science Symposium in Russia
Conference Location Moscow, Russia
Publication Date Jan 1, 2008
Deposit Date Oct 6, 2010
Publisher Springer Verlag
Pages 158-167
Series Title Lecture notes in computer science
Series Number 5010
Edition 3rd
Book Title Computer science – theory and applications, Third International Computer Science Symposium in Russia, CSR 2008, 7-12 June 2008, Moscow, Russia ; proceedings.
DOI https://doi.org/10.1007/978-3-540-79709-8_18
Public URL https://durham-repository.worktribe.com/output/1159609