  Characterization of joint probability distribution for large networks of
random variables remains a challenging task in data science. Probabilistic
graph approximation with simple topologies has practically been resorted to;
typically the tree topology makes joint probability computation much simpler
and can be effective for statistical inference on insufficient data. However,
to characterize network components where multiple variables cooperate closely
to influence others, model topologies beyond a tree are needed, which
unfortunately are infeasible to acquire. In particular, our previous work has
related optimal approximation of Markov networks of tree-width k >=2 closely to
the graph-theoretic problem of finding maximum spanning k-tree (MSkT), which is
a provably intractable task.
  This paper investigates optimal approximation of Markov networks with k-tree
topology that retains some designated underlying subgraph. Such a subgraph may
encode certain background information that arises in scientific applications,
for example, about a known significant pathway in gene networks or the
indispensable backbone connectivity in the residue interaction graphs for a
biomolecule 3D structure. In particular, it is proved that the \beta-retaining
MSkT problem, for a number of classes \beta of graphs, admit O(n^{k+1})-time
algorithms for every fixed k>= 1. These \beta-retaining MSkT algorithms offer
efficient solutions for approximation of Markov networks with k-tree topology
in the situation where certain persistent information needs to be retained.
