2012/10/19 by Mark Hopkins, Hopkins, Mark
Computer Science · #Advanced Algebra and Logic #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge #cs.AI #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1212.2479
Appears in Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI2003)
arxiv created 2012/10/19 · openalex publication_date 2012/10/19 · arxiv updated 2012/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We analyze a new property of directed acyclic graphs (DAGs), called layerwidth, arising from a class of DAGs proposed by Eiter and Lukasiewicz. This class of DAGs permits certain problems of structural model-based causality and explanation to be tractably solved. In this paper, we first address an open question raised by Eiter and Lukasiewicz - the computational complexity of deciding whether a given graph has a bounded layerwidth. After proving that this problem is NP-complete, we proceed by proving numerous important properties of layerwidth that are helpful in efficiently computing the optimal layerwidth. Finally, we compare this new DAG property to two other important DAG properties: treewidth and bandwidth.