TY - GEN
T1 - Counting subgraphs via homomorphisms
AU - Amini, Omid
AU - Fomin, Fedor V.
AU - Saurabh, Saket
PY - 2009/11/12
Y1 - 2009/11/12
N2 - Counting homomorphisms between graphs has applications in variety of areas, including extremal graph theory, properties of graph products, partition functions in statistical physics and property testing of large graphs. In this work we show a new application of counting graph homomorphisms to the areas of exact and parameterized algorithms. We introduce a generic approach for counting subgraphs in a graph. The main idea is to relate counting subgraphs to counting graph homomorphisms. This approach provides new algorithms and unifies several well known results in algorithms and combinatorics including the recent algorithm of Björklund, Husfeldt and Koivisto for computing the chromatic polynomial, the classical algorithm of Kohn, Gottlieb, Kohn, and Karp for counting Hamiltonian cycles, Ryser's formula for counting perfect matchings of a bipartite graph, and color coding based algorithms of Alon, Yuster, and Zwick.
AB - Counting homomorphisms between graphs has applications in variety of areas, including extremal graph theory, properties of graph products, partition functions in statistical physics and property testing of large graphs. In this work we show a new application of counting graph homomorphisms to the areas of exact and parameterized algorithms. We introduce a generic approach for counting subgraphs in a graph. The main idea is to relate counting subgraphs to counting graph homomorphisms. This approach provides new algorithms and unifies several well known results in algorithms and combinatorics including the recent algorithm of Björklund, Husfeldt and Koivisto for computing the chromatic polynomial, the classical algorithm of Kohn, Gottlieb, Kohn, and Karp for counting Hamiltonian cycles, Ryser's formula for counting perfect matchings of a bipartite graph, and color coding based algorithms of Alon, Yuster, and Zwick.
UR - https://www.scopus.com/pages/publications/70449113255
U2 - 10.1007/978-3-642-02927-1_8
DO - 10.1007/978-3-642-02927-1_8
M3 - Conference contribution
AN - SCOPUS:70449113255
SN - 3642029264
SN - 9783642029264
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 71
EP - 82
BT - Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings
T2 - 36th International Colloquium on Automata, Languages and Programming, ICALP 2009
Y2 - 5 July 2009 through 12 July 2009
ER -