Analysis of Complex Networks

11.4 Computing Minimum Cost Homomorphisms

Computing minimum cost homomorphisms is much simpler and faster than computing homeomorphisms. This chapter will describe a fast dynamic programming algorithm that finds the minimum cost homomorphism from a tree pattern to an arbitrary text graph and then show how to generalize this algorithm to patterns with the bounded cyclic structure.

Formally, a multisource tree is a directed graph whose underlying undirected graph is a tree. If the pattern is a multisource tree, then the MCH problem can be solved efficiently with the dynamic programming algorithm. The next subsection describes and analyzes the runtime of such algorithm. When the pattern graph is allowed to have cycles in the underlying undirected graph, then the MCH problem becomes NP-complete. An efficient algorithm still exists when the cyclic structure of the pattern is bounded. The complexity of cyclic structure can be measured by the size of the vertex feedback set F(P)⊆ V_P of the pattern P =(V_P, E_P). F(P) covers all cycles of P, so that the subgraph P_V\F of P induced by V \ F is acyclic. Section 11.4.2 shows how to efficiently handle patterns with small vertex feedback sets and prove the following theorem.

Theorem (Cheng, Harrison, and Zelikovsky [14]) The Minimum cost homomorphism problem with the pattern P =(V_P, E_P) and the text T =(V_T, E_T) can be solved in time

O |V_T|^1+|F(P)| (|E_T| + |V_T||V_P|)

Section 11.4.3 further generalizes this result to the case when vertices are allowed ...