  Holographic algorithms introduced by Valiant are composed of two ingredients:
matchgates, which are gadgets realizing local constraint functions by weighted
planar perfect matchings, and holographic reductions, which show equivalences
among problems with different descriptions via certain basis transformations.
In this paper, we replace matchgates in the paradigm above by the affine type
and the product type constraint functions, which are known to be tractable in
general (not necessarily planar) graphs. More specifically, we present
polynomial-time algorithms to decide if a given counting problem has a
holographic reduction to another problem defined by the affine or product-type
functions. Our algorithms also find a holographic transformation when one
exists. We further present polynomial-time algorithms of the same decision and
search problems for symmetric functions, where the complexity is measured in
terms of the (exponentially more) succinct representations. The algorithm for
the symmetric case also shows that the recent dichotomy theorem for Holant
problems with symmetric constraints is efficiently decidable. Our proof
techniques are mainly algebraic, e.g., using stabilizers and orbits of group
actions.
