Hardness of minimum barrier shrinkage and minimum installation path

DOI10.1016/J.TCS.2020.06.016MaRDI QIDQ2192386zbMATH OpenOpenAlexFDO

Authors S. Cabello, Éric Colin de Verdière

Publication date 17 August 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.04228

zbMATH Keywords

NP-hardnessactivation networkbarrier probleminstallation path

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: In the Minimum Installation Path problem, we are given a graph $G$ with edge weights $w(.)$ and two vertices $s,t$ of $G$. We want to assign a non-negative power $p(v)$ to each vertex $v$ of $G$ so that the edges $uv$ such that $p(u)+p(v)$ is at least $w(uv)$ contain some $s$-$t$-path, and minimize the sum of assigned powers. In the Minimum Barrier Shrinkage problem, we are given a family of disks in the plane and two points $x$ and $y$ lying outside the disks. The task is to shrink the disks, each one possibly by a different amount, so that we can draw an $x$-$y$ curve that is disjoint from the interior of the shrunken disks, and the sum of the decreases in the radii is minimized. We show that the Minimum Installation Path and the Minimum Barrier Shrinkage problems (or, more precisely, the natural decision problems associated with them) are weakly NP-hard.

Recommendations

• Hardness of finding two edge-disjoint Min-Min paths in digraphs
• Multi-path algorithms for minimum-colour path problems with applications to approximating barrier resilience
• On finding Min-Min disjoint paths
• Computing geometric minimum-dilation graphs is NP-hard
• The minimum vulnerability problem on graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximating barrier resilience for arrangements of non-identical disk sensors
• Erratum: ``Approximating minimum-cost connectivity problems via uncrossable bifamilies
• Minimum Cell Connection in Line Segment Arrangements
• Minimum activation cost node-disjoint paths in graphs with bounded treewidth
• Minimum shared‐power edge cut
• On Minimum Power Connectivity Problems
• On the complexity of barrier resilience for fat regions and bounded ply
• Survivable network design problems in wireless networks

Cited in

(2)

• Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
• Minimum cuts in geometric intersection graphs

This page was built for publication: Hardness of minimum barrier shrinkage and minimum installation path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192386)