A linear time algorithm for liarʼs domination problem in proper interval graphs

•Liarʼs domination is shown as a special case of a suitable LMLM-domination in proper interval graphs.•Linear time algorithm for liarʼs domination problem in proper interval graphs.•NP-completeness of liarʼs domination decision problem for undirected path graphs.

Let G=(V,E)G=(V,E) be a graph without isolated vertices and having at least 3 vertices. A set L⊆V(G)L⊆V(G) is a liarʼs dominating set if (1) |NG[v]∩L|⩾2|NG[v]∩L|⩾2 for all v∈V(G)v∈V(G), and (2) |(NG[u]∪NG[v])∩L|⩾3|(NG[u]∪NG[v])∩L|⩾3 for every pair u,v∈V(G)u,v∈V(G) of distinct vertices in G  , where NG[x]={y∈V|xy∈E}∪{x}NG[x]={y∈V|xy∈E}∪{x} is the closed neighborhood of x in G. Given a graph G and a positive integer k, the liarʼs domination problem is to check whether G has a liarʼs dominating set of size at most k. The liarʼs domination problem is known to be NP-complete for general graphs. In this paper, we propose a linear time algorithm for computing a minimum cardinality liarʼs dominating set in a proper interval graph. We also strengthen the NP-completeness result of liarʼs domination problem for general graphs by proving that the problem remains NP-complete even for undirected path graphs which is a super class of proper interval graphs.