  Computational complexity is traditionally measured with respect to input
size. For graphs, this is typically the number of vertices (or edges) of the
graph. However, for large graphs even explicitly representing the graph could
be prohibitively expensive. Instead, graphs with enough structure could admit
more succinct representations. A number of previous works have considered
various succinct representations of graphs, such as small circuits [Galperin,
Wigderson '83].
  We initiate the study of the computational complexity of problems on factored
graphs: graphs that are given as a formula of products and union on smaller
graphs. For any graph problem, we define a parameterized version by the number
of operations used to construct the graph. For different graph problems, we
show that the corresponding parameterized problems have a wide range of
complexities that are also quite different from most parameterized problems. We
give a natural example of a parameterized problem that is unconditionally not
fixed parameter tractable (FPT). On the other hand, we show that subgraph
counting is FPT. Finally, we show that reachability for factored graphs is FPT
if and only if $\mathbf{NL}$ is in some fixed polynomial time.
