Motivated by the fused lasso approach of [1]} to deal with the graph de-noising problem, [2]} recently proposed a Bayesian fusion estimation method using \(t\) -shrinkage priors. In these two works, the actual graph \(G\)  is first reduced to a linear chain graph via the Depth-First-Search algorithm [3]}. [1]} provided theoretical justifications of reducing an arbitrary graph \(G\)  to a DFS-chain graph \(G_C = (V,E_C)\) , by showing that the total variation of the signal defined over \(G_C\)  achieves an upper bound of at most twice its total variation wrt the \(L_1\) -norm over \(G\) , that is,
\(\sum _{(i,j) \in E_C}|\theta _i - \theta _j| \le 2 \sum _{(i,j) \in E}|\theta _i - \theta _j|.\)  Hence, if the true signal is smooth over the graph \(G\) , so that \(\sum _{(i,j) \in E}|\theta _i - \theta _j| \le \delta \) , then, it is reasonable to perform de-noising over \(G_C\)  as well, in the sense that the total variation over \(G_C\)  would satisfy \(\sum _{(i,j) \in E_C}|\theta _i - \theta _j| \le 2\delta .\)  In addition to this, a similar result holds for the total variation in the \(L_0\) -norm, so that, \(\sum _{(i,j) \in E_C}1\!\mathrm {l}\lbrace \theta _i \ne \theta _j\rbrace  \le 2\sum _{(i,j) \in E}1\!\mathrm {l}\lbrace \theta _i \ne \theta _j\rbrace .\)  A signal defined over a linear chain graph is then identical to the sequence model considered earlier in this paper, upto a permutation of the indices of the signal.
