Are there any natural questions in finite graphs (or digraphs) that are undecidable?
4 Answers
Given a graph class G, computing the set of forbidden graph minors of G is undecidable.
A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals, Bruno Courcelle, Rodney G. Downey, Michael R. Fellows, 1997.
-
1This seems less like an undecidable problem about finite graphs and more an undecidable problem about monadic second-order logic. The input to this problem is a monadic second-order formula describing properties of a family of infinitely many graphs, rather than a single finite graph. Commented May 30 at 5:34
Given k pairs of source and sink nodes (si,ti), i=1,…,k in a network (directed graph), the multi-commodity flow problem asks whether we can simultaneously transport commodities from si to ti at a specified rate for all i=1,…,k through the network, subject to a capacity constraint on each edge. This problem is polynomial time solvable using linear programming [1], and hence decidable.
However, this problem becomes significantly harder when the nodes are sending information instead of commodities, i.e., si wants to send a message to ti at a specified rate, and each intermediate node can re-code their incoming packets to produce outgoing packets. This problem is known as network coding [2,3] (more specifically, this is the special case of multiple unicast networks [4,5]), and has been shown to be undecidable for vector linear codes [6], and for general codes [7]. It is perhaps surprising how fundamentally different information is compared to commodities.
[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press and McGraw-Hill, 2009.
[2] R. Ahlswede, N. Cai, S.-Y. Li, and R. W. Yeung, "Network information flow," IEEE Transactions on Information Theory, vol. 46, no. 4, pp. 1204-1216, 2000.
[3] S.-Y. Li, R. W. Yeung, and N. Cai, "Linear network coding," IEEE Transactions on Information Theory, vol. 49, no. 2, pp. 371-381, 2003.
[4] Z. Li and B. Li, "Network coding: The case of multiple unicast sessions," Allerton Conference on Communications, vol. 16, no. 8, 2004.
[5] R. Dougherty and K. Zeger, "Nonreversibility and equivalent constructions of multiple-unicast networks," IEEE Transactions on Information Theory, vol. 52, no. 11, pp. 5067–5077, 2006.
[6] L. Kühne and G. Yashfe, "Representability of Matroids by c-Arrangements is Undecidable," Israel Journal of Mathematics, vol. 252, pp. 95-147, 2022.
[7] C. T. Li, "Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication," IEEE Transactions on Information Theory, vol. 69, no. 6, pp. 3493-3510, 2023. (Full disclosure: I wrote this paper.)
this is going to be far from a rigerous answer, but it's not too hard to imagine encoding turing machines as graphs (the easiest encoding would be encoding a star graph with n nodes as the Internet n, and decoding that integer as ascii text), at which point any health problem can be reformulated into a graph problem.
-
2You could also encode combinatorial finite undecidable problems as finite graphs. (e.g. Post correspondence problem, Wang tiles) But, just like encoding Turing machines, I don't think those would be natural problems on finite graphs.– Discrete lizard ♦Commented May 30 at 10:45
Many problems in program analysis and model checking take in directed weighted graphs that are finite in size, but are undecidable. For instance several problems related to Dyck reachability are undecidable [1] [2]
[1]: Kjelstrom and Pavlogiannis, The Decidability and Complexity of Interleaved Bidirected Dyck Reachability, POPL 2022. (https://arxiv.org/pdf/2111.05923)
[2]: Thomas Reps. Undecidability of context-sensitive data-dependence analysis. ACM Transactions on Programming Languages and Systems (TOPLAS) 22, 1 (https://dl.acm.org/doi/10.1145/345099.345137).