For a given linear transform A over a given vector space Q starting at point x, the orbit of x under A is an infinite sequence (x, Ax, A2x, ..., Ajx). A natural concern in the context of optimality search is whether (and when) the orbit of x will hit a particular target set V. In this paper, the authors study the complexity of such a problem where V is a subgraph H of a given graph G.
This is a very formal, mathematical paper. The authors explore the H-subgraph hitting problem and its motivation, and then describe the techniques they used to arrive at their results. After several theorems, lemmas, and claims (along with their proofs), the paper presents a general algorithm for H-subgraph hitting and a set of claims regarding the availability of a recursive search procedure of a finite graph.
Using a lemma based on this claim, the authors formulate a dynamic programming algorithm using leaf node, introduce node, forget node, and join node. They conclude that the treewidth parameterization of H-subgraph hitting is highly involved, although the described algorithm can be used in certain cases.
I think the paper with its 18 references is of interest to researchers in this particular area. It is a difficult paper to read.
