patternModerate
Decision problems in $\mathsf{P}$ without fast algorithms
Viewed 0 times
fastwithoutmathsfalgorithmsdecisionproblems
Problem
What are some examples of difficult decision problems that can be solved in polynomial time? I'm looking for problems for which the optimal algorithm is "slow", or problems for which the fastest known algorithm is "slow".
Here are two examples:
-
Recognition of perfect graphs. In their FOCS'03 paper [1] Cornuéjols, Liu and Vuskovic gave an $O(n^{10})$ time algorithm for the problem, where $n$ is the number of vertices. I'm not sure if this bound has been improved upon, but as I understand it, more or less a breakthrough is needed to obtain a faster algorithm. (The authors give an $O(n^9)$ time algorithm in the journal version of [1], see here).
-
Recognition of map graphs. Thorup [2] gave a rather complex algorithm with the exponent being (about?) $120$. Perhaps this has been even dramatically improved upon, but I don't have a good reference.
I'm especially interested in problems that have practical importance, and obtaining a "fast" (or even a practical) algorithm has been open for several years.
[1] Cornuéjols, Gérard, Xinming Liu, and Kristina Vuskovic. "A polynomial algorithm for recognizing perfect graphs." Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on. IEEE, 2003.
[2] Thorup, Mikkel. "Map graphs in polynomial time." Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on. IEEE, 1998.
Here are two examples:
-
Recognition of perfect graphs. In their FOCS'03 paper [1] Cornuéjols, Liu and Vuskovic gave an $O(n^{10})$ time algorithm for the problem, where $n$ is the number of vertices. I'm not sure if this bound has been improved upon, but as I understand it, more or less a breakthrough is needed to obtain a faster algorithm. (The authors give an $O(n^9)$ time algorithm in the journal version of [1], see here).
-
Recognition of map graphs. Thorup [2] gave a rather complex algorithm with the exponent being (about?) $120$. Perhaps this has been even dramatically improved upon, but I don't have a good reference.
I'm especially interested in problems that have practical importance, and obtaining a "fast" (or even a practical) algorithm has been open for several years.
[1] Cornuéjols, Gérard, Xinming Liu, and Kristina Vuskovic. "A polynomial algorithm for recognizing perfect graphs." Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on. IEEE, 2003.
[2] Thorup, Mikkel. "Map graphs in polynomial time." Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on. IEEE, 1998.
Solution
Perhaps the following problems fit into your examples:
-
(The decision version of) Coloring, Clique, Stable Set, Clique Covering in perfect graphs. So far, the only known polynomial time algorithms
for these problems are based on the ellipsoid method, which is ''slow'' (and numerically unstable).
-
AKS-primality test in $O((\log n)^{12})$ time.
Though many improvements (currently $O((\log n)^{7.5})$), the AKS-algorithm is still too slow in practice.
-
(The decision version of) Coloring, Clique, Stable Set, Clique Covering in perfect graphs. So far, the only known polynomial time algorithms
for these problems are based on the ellipsoid method, which is ''slow'' (and numerically unstable).
-
AKS-primality test in $O((\log n)^{12})$ time.
Though many improvements (currently $O((\log n)^{7.5})$), the AKS-algorithm is still too slow in practice.
Context
StackExchange Computer Science Q#13202, answer score: 12
Revisions (0)
No revisions yet.