Complexity and lowers bounds for Power Edge Set Problem

This article is devoted to the study of the complexity of POWER EDGE SET (PES), a problem occurring when monitoring power networks. We show that PES remains NP-hard in bipartite planar graphs with bounded degree. This result is extended to unit disk graphs and grids with maximum degree three. To the best of our knowledge, this is the most restricted class of graphs known so far on which POWER EDGE SET is NP-complete. We also show that there is no 2(o(root n)) time algorithm for POWER EDGE SET, and there is no 2(o(k))n(O(1))-time algorithm for its parameterized version, even in bipartite planar subcubic graphs and unit disk graphs, assuming ETH. Finally, we show a polynomial-time algorithm for graphs of bounded treewidth (XP wrt. treewidth), such as series-parallel graphs or outerplanar graphs. (C) 2018 Elsevier B.V. All rights reserved.