×

Computation in causal graphs. (English) Zbl 1411.05244

Summary: The goal of this paper is to introduce some of the important concepts in causal graph theory and examine them from combinatorial and computational perspectives. Of fundamental importance in applications of causal models that use graphs are dependence-separators or, simply, \(d\)-separators. A vertex set \(Z\) is a \(d\)-separator for a pair of disjoint vertex sets \((X,Y)\) if \(X\) and \(Y\) are independent conditioned on \(Z\). For the case of a single-setpair it is known that \(d\)-separators can be found efficiently by elegant network flow techniques. In this paper, we consider \(d\)-separators for a collection \(\{(X_1,Y_1),(X_2,Y_2),\dots,(X_k,Y_k)\}\) of setpairs. We focus on two classes of combinatorial objects in this multiple-setpair framework: \(d\)-separators and \(d\)-super-separators. We say that \(Z\) is a \(d\)-separator for multiple setpairs if, for each \(i\), \(X_i\) and \(Y_i\) are independent conditioned on \(Z\); we say that \(Z\) is a \(d\)-super-separator if, for each \(i\), there exists \(Z_i\subseteq Z\), such that \(X_i\) and \(Y_i\) are independent conditioned on \(Z_i\). For the latter object, we give an \(O(\log^2k)\)-approximation algorithm for the problem of finding a minimum cost \(d\)-super-separator. The focus on approximation algorithms is necessary as we show this problem is NP-complete. For the former object, we show it is hard to determine whether a \(d\)-separator exists, even when there are just five setpairs. This problem remains hard even if each setpair consists of singleton vertices, provided the number of setpairs is large. On the positive side, we show that if there are a fixed number of singleton setpairs then a \(d\)-separator for multiple setpairs can be found in polynomial time, if one exists.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Appel and W. Haken.Every planar map is four colorable Part I: discharging.Illinois Journal of Mathematics, 21:429-490, 1977. · Zbl 0387.05009
[2] K. Appel, W. Haken, and J. Koch. Every planar map is four colorable Part II: reducibility. Illinois Journal of Mathematics, 21:491-567, 1977. · Zbl 0387.05010
[3] J. Berkson. Limitations of the application of fourfold table analysis to hospital data. Biometrics Bulletin, 2:47-53, 1946.
[4] V. Chvatal. Star-cutsets and perfect graphs. Journal of Combinatorial Theory, Series B, 39(3):89-199, 1985. · Zbl 0674.05058
[5] G. Dirac. On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universit¨at Hamburg, 25:71-76, 1961. · Zbl 0098.14703
[6] J. Fukuyama. NP-completeness of the planar separator problems. Journal of Graph Algorithms and Applications, 10(2):317-328, 2006. · Zbl 1178.68378
[7] N. Garg, V. Vazirani, and M. Yannakakis. Approximate max-flow min(multi)cut theorems and their applications. Algorithmica, 18(3):3-20, 1996. · Zbl 1310.05198
[8] S. Greenland, J. Pearl, and J. Robins. Causal diagrams for epidemiological research. Epidemiology, 10:37-48, 1999.
[9] M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 2nd edition, 1993. · Zbl 0837.05001
[10] K. Hoover. Causality in economics and econometrics. In S. Durlauf and L. Blume, editors, The New Palgrave Dictionary of Economics. Palgrave Macmillan, 2009.
[11] N. Jewell. Statistics for Epidemiology. Chapman and Hall/CRC, 2004.
[12] S. Lauritzen, A. Dawid, B. Larsen, and H. Leimer. Independence properties of directed markov fields. Networks, 20:491-505, 1990. · Zbl 0743.05065
[13] S. Lauritzen and D. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society, Series B, 50(2):157-224, 1988. · Zbl 0684.68106
[14] D. Lichtenstein. Planar formulae and their uses. SIAM Journal on Computing, 11:329-343, 1982. · Zbl 0478.68043
[15] R. Lipton and R. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. · Zbl 0432.05022
[16] D. Marx. Parameterized graph separation problems. Theoretical Computer Science, 351(3):394-406, 2006. · Zbl 1086.68104
[17] K. Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10:96-115, 1927. · JFM 53.0561.01
[18] N. Narayanaswamy and N. Sadagopan. Connected (s,t)-vertex separator parameterized by chordality. Journal of Graph Algorithms and Applications, 19(1):549-565, 2015. · Zbl 1326.05154
[19] O. Oellerman. The connected cutset connectivity of a graph. Discrete Mathematics, 69(3):301-308, 1988. · Zbl 0643.05044
[20] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Cambridge University Press, 1988. · Zbl 0746.68089
[21] J. Pearl. Causal inference in statistics: an overview. Statistics Surveys, 3:96-146, 2009. · Zbl 1300.62013
[22] J. Pearl. Causality: Models, Reasoning, and Inference. Morgan and Kaufman, 2nd edition, 2009. · Zbl 1188.68291
[23] J. Pearl and P. Meshkat. Testing regression models with fewer regressors. In D. Heckerman and J. Whittaker, editors, Artificial Intelligence and Statistics, pages 255-259. 1999.
[24] B. Shipley. Cause and Correlation in Biology. Cambridge University Press, 2002.
[25] P. Sprites, C. Glymour, and R. Scheines.Causation, Prediction, and Search. MIT Press, 2nd edition, 2000. · Zbl 0806.62001
[26] J. Tian, A. Paz, and J. Pearl. Finding minimal d-separators. Technical report, Cognitive Systems Laboratory, Los Angeles, 1988.
[27] A. Tucker. Coloring graphs with stable cutsets. Journal of Combinatorial Theory, Series B, 34:258-267, 1983. · Zbl 0498.05028
[28] V. Vazirani. Approximation Algorithms. Springer, 2001. · Zbl 0999.68546
[29] H. Whitney. A theorem on graphs. Annals of Mathematics, 32:378-390, 1931. · Zbl 0002.16101
[30] D. Williamson and D. Schmoys. The Design of Approximation Algorithms. Cambridge, 2011.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.