Skip to main content
5 votes
Accepted

Undecidable problems in finite graphs

Given a graph class $\mathcal G$, computing the set of forbidden graph minors of $\mathcal G$ is undecidable. A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order ...
Pål GD's user avatar
  • 16.7k
2 votes

Undecidable problems in finite graphs

Given $k$ pairs of source and sink nodes $(s_i,t_i)$, $i=1,\ldots,k$ in a network (directed graph), the multi-commodity flow problem asks whether we can simultaneously transport commodities from $s_i$ ...
Cheuk Ting Li's user avatar
1 vote

Reduce the problem of CFGs with equal languages to the problem of CFGs generating a palindrome

Equality is a stated by a proposition starting with $\forall$, but membership of a string with some property is stated by a proposition starting with $\exists$. In fact, $\mathrm{EQ_{CFG}}$ is $\Pi_1$-...
pcpthm's user avatar
  • 2,727

Only top scored, non community-wiki answers of a minimum length are eligible