# zbMATH — the first resource for mathematics

Comparing universal covers in polynomial time. (English) Zbl 1142.68456
Hirsch, Edward A. (ed.) et al., Computer science – theory and applications. Third international computer science symposium in Russia, CSR 2008 Moscow, Russia, June 7–12, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79708-1/pbk). Lecture Notes in Computer Science 5010, 158-167 (2008).
Summary: 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$$.
For the entire collection see [Zbl 1136.68005].

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C85 Graph algorithms (graph-theoretic aspects) 90C59 Approximation methods and heuristics in mathematical programming
Full Text: