 NSFPAR ID:
 10318127
 Date Published:
 Journal Name:
 PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

The study of power domination in graphs arises from the problem of placing a minimum number of measurement devices in an electrical network while monitoring the entire network. A power dominating set of a graph is a set of vertices from which every vertex in the graph can be observed, following a set of rules for power system monitoring. In this paper, we study the problem of finding a minimum power dominating set which is connected; the cardinality of such a set is called the connected power domination number of the graph. We show that the connected power domination number of a graph is NPhard to compute in general, but can be computed in linear time in cactus graphs and block graphs. We also give various structural results about connected power domination, including a cut vertex decomposition and a characterization of the effects of various vertex and edge operations on the connected power domination number. Finally, we present novel integer programming formulations for power domination, connected power domination, and power propagation time, and give computational results.more » « less

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NPhard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhard and APXhard whenever H contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of H is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomialtime solvability results for small graphs H such as P5, P6, the claw, or the fork. We prove that for every such “possibly tractable” graph H there exists an algorithm that, given an Hfree graph G and an accuracy parameter ε > 0, finds an independent set in G of cardinality within a factor of (1 – ε) of the optimum in time exponential in a polynomial of log  V(G)  and ε−1. That is, we show that for every graph H for which Maximum Independent Set is not known to be APXhard in Hfree graphs, the problem admits a quasipolynomial time approximation scheme in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set.more » « less

Minimum flow decomposition (MFD) is the NPhard problem of finding a smallest decomposition of a network flow/circulation
X on a directed graphG into weighted sourcetosink paths whose weighted sum equalsX . We show that, for acyclic graphs, considering thewidth of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only nonnegative weights, we identify and characterise a new class ofwidthstable graphs, for which a popular heuristic is aO (logVal (X ))approximation (Val (X ) being the total flow ofX ), and strengthen its worstcase approximation ratio from to Ω (\(\Omega (\sqrt {m})\) m /logm ) for sparse graphs, wherem is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)approximation (‖X ‖ being the maximum absolute value ofX on any edge) using a poweroftwo approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X ‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (nonnegative) flow decompositions posed by Kloster et al. [2018 ], but show that its useful implication (polynomialtime assignments of weights to a given set of paths to decompose a flow) holds for the negative version. 
Given a graph, the shortestpath problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a generalization of this classical problem in which the position of each vertex in the graph is a continuous decision variable, constrained to lie in a corresponding convex set. The length of an edge is then defined as a convex function of the positions of the vertices it connects. Problems of this form arise naturally in motion planning of autonomous vehicles, robot navigation, and even optimal control of hybrid dynamical systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NPhard. Our main contribution is a strong mixedinteger convex formulation based on perspective functions. This formulation has a very tight convex relaxation and makes it possible to efficiently find globallyoptimal paths in large graphs and in highdimensional spaces.more » « less

Intersection graphs of planar geometric objects such as intervals, disks, rectangles and pseudodisks are wellstudied. Motivated by various applications, Butman et al. (ACM Trans. Algorithms, 2010) considered algorithmic questions in intersection graphs of $t$intervals. A $t$interval is a union of $t$ intervals  these graphs are also referred to as multipleinterval graphs. Subsequent work by Kammer et al.\ (APPROXRANDOM 2010) considered intersection graphs of $t$disks (union of $t$ disks), and other geometric objects. In this paper we revisit some of these algorithmic questions via more recent developments in computational geometry. For the \emph{minimumweight dominating set problem} in $t$interval graphs, we obtain a polynomialtime $O(t \log t)$approximation algorithm, improving upon the previously known polynomialtime $t^2$approximation by Butman et al. In the same class of graphs we show that it is $\NP$hard to obtain a $(t1\epsilon)$approximation for any fixed $t \ge 3$ and $\epsilon > 0$. The approximation ratio for dominating set extends to the intersection graphs of a collection of $t$pseudodisks (nicely intersecting $t$tuples of closed Jordan domains). We obtain an $\Omega(1/t)$approximation for the \emph{maximumweight independent set} in the intersection graph of $t$pseudodisks in polynomial time. Our results are obtained via simple reductions to existing algorithms by appropriately bounding the union complexity of the objects under consideration.more » « less