Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond

We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do not become easy even in almost k-cycle free graphs, for any constant k ≥ 4. Triangle finding is at the base of many conditional lower bounds in P, mainly for distance computation problems, and the existence of many 4-or 5-cycles in a worst-case instance had been the obstacle towards resolving major open questions.