On the parameterized complexity of the expected coverage problem

The Maximum covering location problem (MCLP) is a well-studied problem in the field of operations research. Given a network with demands (demands can be positive or negative) on the nodes, an integer budget k, the MCLP seeks to find k potential facility centers in the network such that the neighborhood coverage is maximized. We study the variant of MCLP where edges of the network are subject to random failures due to some disruptive events. One of the popular models capturing the unreliable nature of the facility location is the linear reliable ordering (LRO) model. In this model, with every edge e of the network, we associate its survival probability (formula presented), or equivalently, its failure probability (formula presented). The failure correlation in LRO is the following: If an edge e fails then every edge (formula presented) with (formula presented) surely fails. The task is to identify the positions of k facilities that maximize the expected coverage. We refer to this problem as Expected Coverage problem. We study the Expected Coverage problem from the parameterized complexity perspective and obtain the following results. 1.For the parameter treewidth, we show that the Expected Coverage problem is W[1]-hard. We find this result a bit surprising, because the variant of the problem with non-negative demands is fixed-parameter tractable (FPT) parameterized by the treewidth of a graph.2.We complement the lower bound by the proof that Expected Coverage is FPT being parameterized by the treewidth and the maximum vertex degree. We give an algorithm that solves the problem in time (formula presented), where (formula presented) is the treewidth, (formula presented) is the maximum vertex degree, and n the number of vertices of the input graph. In particular, since (formula presented), it means the problem is solvable in time (formula presented), that is, is in XP parameterized by treewidth.