|
9
|
|
edited Dec 2 2010 at 15:20 |
As others have mentioned, the answer to your title question is strictly speaking no. With regards to your other questions, it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.
I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor-closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:
M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.
B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.
|
|
|
|
|
8
|
|
edited Dec 2 2010 at 15:01 |
As others have mentioned, the answer to your title question is strictly speaking no. With regards to your other questions, it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.
I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor-closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:
M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.
B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.
|
|
|
|
|
7
|
|
edited Dec 2 2010 at 14:23 |
As others have mentioned, the answer to your title question is strictly speaking no. HoweverWith regards to your other questions, I will remark that it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.
I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor-closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:
M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.
B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.
|
|
|
|
6
|
|
edited Dec 2 2010 at 13:16 |
As others have mentioned, the answer to your question is strictly speaking no. However, I will remark that it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.
I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor closed minor-closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:
M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.
B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.
|
|
|
|
|
5
|
|
edited Dec 2 2010 at 11:26 |
I would say that a reasonable As others have mentioned, the answer to your question is yesstrictly speaking no. However, in the sense I will remark that it has been proven that it is undecidable to compute the excluded minors for a minor-closed class $\mathcal{C}$, unless $\mathcal{C}$ is presented to you in a silly way. Of course, there is no paradox, because this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.
I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:
M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.
B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.
|
|
|
|
|
4
|
|
edited Dec 2 2010 at 11:14 |
I would say that a reasonable answer to your question is yes, in the sense that it is undecidable to compute the excluded minors for a minor closed minor-closed class , $\mathcal{C}$, unless the class $\mathcal{C}$ is presented to you in a silly way.
In particularOf course, this does not imply that the related problem of determining if an input graph $G$ is in $\mathcal{C}$ is undecidable. Indeed, as you mention by the Robertson-Seymour theory, this second problem is not only decidable, but is in P.
I guess I should quantify what I mean by non-silly representations of minor-closed families. Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$. Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above, the references are:
M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.
B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.
|
|
|
|
|
3
|
|
edited Dec 2 2010 at 10:28 |
I would say that a reasonable answer to your question is yes, in the sense that it is undecidable to compute the excluded minors for a minor closed class, unless the class is presented to you in a silly way.
In particular, Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$.
Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$. For the undecidability results that I mentioned above the references are:
M.R. Fellows and M.A. Langston. On search, decision and the efficiency of polynomial-time algorithms (extended abstract). In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 501–512, 1989.
B. Courcelle, R.G. Downey, and M.R. Fellows. A note on the computability of graph minor obstruction sets for monadic second order ideals. Journal of Universal Computer Science, 3:1194–1198, 1997.
|
|
|
|
|
2
|
|
edited Dec 2 2010 at 10:20 |
I would say that a reasonable answer to your question is yes, in the sense that it is undecidable to compute the excluded minors for a minor closed class, unless the class is presented to you in a silly way.
In particular, Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$.
Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$.
|
|
|
|
|
1
|
|
answered Dec 2 2010 at 10:14 |
I would say that a reasonable answer to your question is yes, in the sense that it is undecidable to compute the excluded minors for a minor closed class, unless the class is presented to you in a silly way.
In particular, Fellows and Langston proved that
if your minor-closed class $\mathcal{C}$ is given by a Turing machine $M$, then it is undecidable to compute an excluded minor characterization of $\mathcal{C}$.
Courcelle, Downey, and Fellows proved that if $\mathcal{C}$ is instead given by a monadic second-order logic formula $\phi$, then it is also undecidable to compute an excluded minor characterization of $\mathcal{C}$.
There are positive results for certain minor closed families. For example, this paper by Adler, Grohe, and Kreutzer shows that for any fixed $k$, they can compute the excluded minors for the class of graphs of tree-width at most $k$.
|
|
|
