Hardest known natural problem in P?

Question

I wonder, what is (currently) the largest number $k$, such that a natural problem is known with the following properties:

1. An $O(n^k)$ algorithm has been already found for the problem.

2. For any fixed $\epsilon>0$ no $O(n^{k-\epsilon})$ algorithm is known for the same problem. (Note that a faster algorithm $may$ exist, just it is not known yet, so I am not looking for a proven lower bound.)

3. The problem description itself does not depend on $k$. (This condition is needed to exclude parametrized cases like "find a clique of size $k$ in an input graph, for a constant $k$.")

In a sense, such a problem might qualify as the hardest, known, natural, problem in $\bf P$ (regarding the exponent of the fastest known algorithm).

Answer 1

The AKS Primality testing algorithm may be a good candidate, where the best algorithm currently known version of the algorithm has $\tilde{O}(n^6)$ running time. See Primality testing with Gaussian periods (Lenstra and Pomerance).

Answer 2

How bout finding two disjoint shortest paths, which has a runtime of $O(|V|^8)$?

Also, $O(|V|^{12}\cdot |E|)$ algorithm is known for independent set in $P_5$-free graphs.

Answer 3

perfect graphs appear to be fundamental and therefore "natural" to complexity theory/math in many ways. the recognition algorithm runs in time $O(|V(G)|^9)$. it seems possible there are other "natural" or "fundamental" graph classes that take longer to recognize and are still in P.