This analysis reveals polynomial solvability of domination problems in proper interval graphs, implying broader application for graph theory.
The efficient minus domination problem (EMDP) and the efficient signed domination problem (ESDP) are domination-type problems in graphs. These problems are known to be NP-complete on chordal graphs and polynomially solvable on chain interval graphs, while the complexity on proper interval graphs remained open. By exploiting the totally unimodular structure of the closed-neighborhood matrix induced by a proper interval ordering, we obtain linear programming formulations under which both the EMDP and ESDP become polynomially solvable. The same perspective naturally extends to vertex-weighted settings and to other domination variants defined by similar neighborhood constraints.
No takes yet. Share an insight, caveat, or question.
Chuan-Min Lee (2026) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: