No article text was recorded for this version.
treewidth-dependent complexity
Version 1 of 1136 papers158 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Efficient Principled Learning of Thin Junction Trees
- Blog: An Improved Isomorphism Test for Bounded-Tree-Width Graphs
- Blog: Computing Divergences between Discrete Decomposable Models
- Blog: Solving Infinite-Domain CSPs Using the Patchwork Property
- Blog: k-Support and Ordered Weighted Sparsity for Overlapping Groups: Hardness and Algorithms
- Blog: Approximate Inference in Structured Instances with Noisy Categorical Observations
- Blog: DPSampler: Exact Weighted Sampling Using Dynamic Programming
- Blog: A Complete Anytime Algorithm for Treewidth
- Blog: An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
- Blog: A heuristic algorithm using tree decompositions for the maximum happy vertices problem
- Blog: Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
- Blog: Unbreakable Decomposition in Close-to-Linear Time
- Blog: Randomized contractions meet lean decompositions
- Blog: Solving M-Modes in Loopy Graphs Using Tree Decompositions
- Blog: A heuristic algorithm for the maximum happy vertices problem using tree decompositions
- Blog: Multi-Multiway Cut Problem on Graphs of Bounded Branch Width
- Blog: Order Statistics for Probabilistic Graphical Models
- Blog: A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
- Blog: QBF as an Alternative to Courcelle's Theorem
- Blog: Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
- Blog: Grounding for Model Expansion in k-Guarded Formulas with Inductive Definitions
- Blog: Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
- Blog: An efficient tree decomposition method for permanents and mixed discriminants
- Blog: Computing the Tutte polynomial in vertex-exponential time
- Blog: Popular Matchings and Limits to Tractability
- Blog: Diagnosing Tree-Decomposable Circuits
- Blog: Solving Factored MDPs with Hybrid State and Action Variables
- Blog: Structural Decompositions of Epistemic Logic Programs
- Blog: Towards Structural Tractability in Hedonic Games
- Blog: On the parameterized complexity of symmetric directed multicut
- Blog: Parameterized Algorithms for Graph Partitioning Problems
- Blog: Learning Thin Junction Trees via Graph Cuts
- Blog: An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
- Blog: Strong-diameter decompositions of minor free graphs
- Blog: Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
- Blog: Efficient Search-Based Weighted Model Integration
- Blog: Large-Treewidth Graph Decompositions and Applications
- Blog: A Fixed-Parameter Algorithm for #SAT with Parameter Incidence Treewidth
- Blog: Solving Factored MDPs with Hybrid State and Action Variables
- Blog: An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
- Blog: Structural Tractability of Shapley and Banzhaf Values in Allocation Games
- Blog: An MCMC Approach to Solving Hybrid Factored MDPs
- Blog: Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth
- Blog: Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables
- Blog: Convex Relaxations for Learning Bounded-Treewidth Decomposable Graphs
- Blog: Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability
- Blog: Latent Tree Decomposition Parsers for AMR-to-Text Generation
- Blog: Quantitative Verification on Product Graphs of Small Treewidth
- Blog: Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number
- Blog: Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth
- Blog: Directed Subset Feedback Vertex Set is Fixed-Parameter Tractable
- Blog: The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
- Blog: Anti-factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
- Blog: Improved FPT Algorithms for Deletion to Forest-like Structures
- Blog: Parallel Planar Subgraph Isomorphism and Vertex Connectivity
- Blog: H-DPOP: Using Hard Constraints for Search Space Pruning in DCOP
- Blog: Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- Blog: A Fixed-Parameter Tractable Algorithm for Counting Markov Equivalence Classes with the Same Skeleton
- Blog: Refined Vertex Sparsifiers of Planar Graphs
- Blog: Junction Tree Variational Autoencoder for Molecular Graph Generation
Showing 60 of 136 papers.
History & citation
Current · Permanent link
Cite this direction
Latest version (a living page):
@misc{lacuna_treewidth_dependent_complexity_f84928fb,
title = {treewidth-dependent complexity},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/treewidth-dependent-complexity/rdr_f84928fb23a54c1d88bb5db2b30cdb59},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}This exact version (version 1, frozen text):
@misc{lacuna_treewidth_dependent_complexity_f84928fb_v1,
title = {treewidth-dependent complexity},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/treewidth-dependent-complexity/rdr_f84928fb23a54c1d88bb5db2b30cdb59/v/1},
note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}