What is the famous hard problems that were shown to be in $\mathcal{P}$ after?I want to know a list of problems that are difficult to prove in the class of easy problems?Maybe like matching, linear programming. Any list or references would be appreciated.
Problems that are hard to prove in $\mathcal{P}$
reference request;big list;polynomial time
The $k$-disjoint path problem for fixed $k$. Given an undirected graph $G$ and $k$ node pairs $s_1t_1,s_2t_2,\ldots,s_kt_k$, are there node-disjoint paths in $G$ connecting the pairs? Polynomial-time algorithm follows from the work of Robertson and Seymour and relies on very non-trivial and difficult graph theoretic results. There are more general problems than this one but the disjoint paths problem is highly non-trivial even for $k=2$. For instance it is NP-Complete in directed graphs for $k=2$.