Efficient Minus and Signed Domination in Proper Interval Graphs with a Totally Unimodular Structure

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.