The goal of this talk is to achieve cross-fertilization between the theory and practice of algorithms for NP-hard graph problems. To fertilize practice with recent theoretical ideas, we survey recent work on the notion of H-treewidth. It is a recently introduced graph parameter that refines the classic notion of treewidth, by instantiating it with a class H of graphs that are considered easy for the target optimization problem. H-treewidth supports algorithms whose running-time guarantees are comparable to those for treewidth, while allowing for much smaller parameter values. The resulting theory has matured to the point that practical implementations can start being explored. By giving an accessible introduction into this area, the talk aims to facilitate a discussion on application areas where H-treewidth can have an impact. To fertilize theory with practical insights, the second part of the talk revisits the challenge of explaining the mysterious successes of solving real-world inputs of NP-hard graph problems. We consider several recent ways of measuring input complexity based on the shape of the landscape of feasible solutions or the complexity of certifying optimality. The intent is to spark a discussion about which aspects of real-world inputs to NP-hard graph problems can be used to theoretically explain their tractability.