Sufficiency of the minimal proper-interval completion characterization
Sufficiency of the minimal proper-interval completion characterization
Let be an interval graph, and let be a completion of to a proper interval graph. The cited theorem gives a necessary “only if” condition for 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.