EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Polynomial-Time Derivation of Optimal $k$-Tree Topology from Markov Networks

Fereshteh R. Dastjerdi, Liming Cai

Journal of Graph Algorithms and Applications · 26.06.2026 · 30 (1) · 253-272

DOI: 10.7155/jgaa.v30i1.3236 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Algorithms and Applications, online erschienen am 26.06.2026. Verfasst von Fereshteh R. Dastjerdi und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 the approximation of Markov networks of tree-width $k$ with the minimum information loss (termed optimal approximation) closely to the graph-theoretic problem of finding maximum spanning $k$-tree (MS$k$T), 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 MS$k$T problem, for several classes $\beta$ of graphs (i.e., families of subgraphs that are required to be retained, such as Hamiltonian paths), admits $O(n^{k+1})$-time algorithms for fixed $k\geq 1$. These $\beta$-retaining MS$k$T algorithms offer efficient solutions for approximation of Markov networks with $k$-tree topology in situations where certain persistent structural information needs to be preserved.

Zitieren

APA

Dastjerdi, F. R., & Cai, L. (2026). Polynomial-Time Derivation of Optimal $k$-Tree Topology from Markov Networks. Journal of Graph Algorithms and Applications, 30(1), 253-272. https://doi.org/10.7155/jgaa.v30i1.3236

Vancouver

Dastjerdi FR, Cai L. Polynomial-Time Derivation of Optimal $k$-Tree Topology from Markov Networks. Journal of Graph Algorithms and Applications. 2026;30(1):253-272. doi:10.7155/jgaa.v30i1.3236

BibTeX
@article{Dastjerdi2026,
  author = {Dastjerdi, Fereshteh R. and Cai, Liming},
  title = {Polynomial-Time Derivation of Optimal $k$-Tree Topology from Markov Networks},
  journal = {Journal of Graph Algorithms and Applications},
  year = {2026},
  volume = {30},
  number = {1},
  pages = {253--272},
  doi = {10.7155/jgaa.v30i1.3236}
}
Kostenlos starten →