So, I reached a point where I know how the next steps can be implemented, but, differently from before, the next steps on libdepixelize can have a big impact on how it will be integrated on Inkscape. I decided it would be a good thing to discuss this matter with other developers.
Currently it's possible to represent simple paths on libdepixelize (see this), but to implement the full Kopf-Lischinski algorithm, I'll need to have paths with "holes" and I'll need to use complex path representations with enough expressive power to communicate things like "point start in A, then do a Bézier to C...". I don't want to create a new interface to represent paths, because this interface already exists and it's called SVG.
Anyway, I'm sending this message now, but I'll look deeper in Inkscape code and come up with some design ideas later.