Sufficiency of the minimal proper-interval completion characterization

Let GG be an interval graph, and let HH be a completion of GG to a proper interval graph. The cited theorem gives a necessary “only if” condition for HH to be minimal.

Minimal proper-interval completion conjecture. The only-if condition of that theorem is also sufficient. Moreover, if this condition is sufficient, then the problem of finding a minimal completion to a proper interval graph, when the input is an interval graph, has polynomial complexity.

This conjecture concerns the characterization and complexity of minimal completions from interval graphs to proper interval graphs. The source does not provide evidence resolving it, so its status remains open.

Sources & referencesView supporting material

Primary source

Nina Pardal, “Structural characterization of some problems on circle and interval graphs”, arXiv:2006.00099 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.