=Paper=
{{Paper
|id=Vol-1662/mpr3
|storemode=property
|title=Computational complexity of guarding connected plane graphs
|pdfUrl=https://ceur-ws.org/Vol-1662/mpr3.pdf
|volume=Vol-1662
|authors=Konstantin S. Kobylkin
}}
==Computational complexity of guarding connected plane graphs==
https://ceur-ws.org/Vol-1662/mpr3.pdf
Computational complexity
of guarding connected plane graphs
Konstantin S. Kobylkin
kobylkinks@gmail.com
Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia)
Ural Federal University (Yekaterinburg, Russia)
Abstract
Computational complexity is studied for the problem of stabbing set of
straight line segments with the smallest cardinality set of disks of fixed
radii r > 0 where the set of segments forms a straight line drawing
of some connected planar graph. We claim strong NP-hardness of the
problem over the class of 4-connected (i.e. Hamiltonian) plane trian-
gulations of bounded vertex degree for small r, although the problem
is solvable in polynomial time over plane graphs for large r.
1 Introduction
Guarding the boundaries of geometric objects or complexes of plane embeddings of planar graphs is a widely
studied class of problems in computational geometry, see e.g. [6], [7] and [15]. Usually in such problems one needs
to find the smallest cardinality set C of guards (e.g. points on the plane), each of which has a bounded (in some
sense) visibility area such that each piece of the boundary or of the graph complex (e.g. edge or face) is within
the visibility area of some guard from C. Designing exact and approximate algorithms for these problems finds its
applications in security, sensor placement, lighting and robotics. In this paper the computational complexity of
the following problem (IPGD1 ) is studied: given some straight line drawing of an arbitrary simple (i.e. without
loops and parallel edges) planar graph G = (V, E) without edge crossings and a constant r > 0, find the smallest
cardinality set C ⊂ R2 of points (disk centers) such that each edge e ∈ E is within (Euclidean) distance r from
some point c = c(e) ∈ C (i.e., the disk of radius r centered at c intersects e). In the IPGD problem, each guard
has a circular visibility area that does not depend on the obstacles in contrast to the known Art Gallery problem
[15] where the coverage area of video cameras is affected by gallery walls.
There are two basic applications of studying the IPGD problem. In the first setting, given a network of physical
devices distributed around some geographical area and communicating with each other through physical links
(e.g., optical fibers), the problem is to monitor its security (e.g. connectivity) by locating the smallest number
of sensors having a circular scope area such that each network link is within the scope of some sensor. Here, the
network nodes are modelled by points on the plane while its links are given in the form of straight line segments.
The second application is again from network security [1], [2], [3]. Given a network of physical devices, one needs
to evaluate its vulnerability to simultaneous technical failures caused by natural (flood, fire, electromagnetic
pulses) or human sources. A catastrophic event (threat) is usually localized in a particular geographical area and
is modelled [2] by a disk for simplicity. It is also assumed that these disks are all of the same radius but other
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in
Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org
1 stands for Intersecting Plane Graph with Disks
200
model assumptions about threats may also be adopted [3]. A threat impacts network link when the corresponding
disk and line segment intersect. Evaluation of network vulnerability may be formulated as finding the minimum
number of threats along with their positions that cause all network links to break, and its solution reports those
parts of the network that need additional protection. Thus both aforementioned applications bring us exactly
to the IPGD problem since usually network links are geographically non-overlapping.
The computational complexity of the IPGD problem is studied over connected plane graphs. The plane
graph notion is used to denote a simple planar graph along with its straight line drawing on the plane without
edge crossings. More specifically a triple G = (V, E, F ) is called a plane graph if V ⊂ R2 , set E consists of
nondegenerate straight line segments crossing only at their endpoints, which are from V, and F denotes the set
of all open (in R2 ) regions bounded by segments from E where each f ∈ F does not intersect with any segment
from E.
IPGD is closely related to several well-known combinatorial optimization problems. Obviously, IPGD is a
special case of the geometric Hitting Set problem: given set N = {Nr (e)}e∈E of Euclidean r-neighbourhoods
of edges from E, find the smallest cardinality set C ⊂ R2 such that Nr (e) ∩ C 6= ∅ for every e ∈ E. Following
the common terminology, the set C forms a hitting set for the set of objects N . The known Vertex Cover (VC)
problem for planar graphs can be obtained from IPGD by setting r = 0 because it makes one choose disk centers
at the graph vertices. For the case of IPGD where G consists of isolated vertices (i.e., segments from E are all
of zero length), we have continuous Disk Cover problem.
Our main result is about computational complexity of the IPGD problem over highly connected plane trian-
gulations. Triangulations can denote somewhat different graph classes in the literature. In this paper it is used
in the sense that is common in the planar graph theory. A plane graph whose faces are triangles except for
possibly outer one is referred to as general plane triangulation. A general plane triangulation having triangular
outer face is called simply a plane triangulation. Consider a set S of n points on the plane. We call a plane
graph G = (V, E, F ) a Delaunay triangulation if V = S, outer face of G is defined by the boundary of conv V
and each inner face f ∈ F is a triangle that admits circumscribing disk c(f ) where the only points of S that are
contained in c(f ) are the vertices of f.
Using connections with the maximum independent set problem (MIS), the strong NP-hardness of IPGD and
VC problems (IPGD and VC become equivalent for small disk radius r) is reported over the subclass of 4-
connected (i.e., Hamiltonian) plane triangulations of bounded vertex degree. Graphs of this subclass are graphs
isomorphic to Delaunay triangulations due to [8], which supports the conjecture that both VC and IPGD are NP-
hard over 4-connected Delaunay ones. This observation motivates our complexity analysis because in applications
physical networks are often modelled by highly connected Delaunay triangulations.
In the recent relevant literature, NP-hardness of VC and MIS problems is given for classes of planar graphs
of vertex degree of at most 3, see e.g. [4]. Other works claim NP-hardness of these problems over 2-connected
3-regular planar graphs [13], over stellated 3-connected 3-regular ones [7] and over 3-regular planar Hamiltonian
graphs [9]. It contrasts with our result for highly connected plane triangulations that have the maximum number
of edges (roughly twice as much as for 3-regular graphs) within the class of plane graphs. A graph class that
contains every induced subgraph (or every subgraph, or every minor) along with every its graph is referred to as
hereditary class. It is easy to give an example demonstrating that 4-connected plane triangulations do not form
a hereditary graph class even with respect to edge contractions (without multiple edges), which prohibits direct
application of the VC complexity analysis over hereditary classes, see e.g. [4].
There is a subclass of plane triangulations for which polynomial solvability of VC is known. Consider an
arbitrary planar graph and its simple cycle. Graph edge is called a chord if it connects nonconsecutive vertices of
that cycle. The length of the longest graph cycle without chords is called its chordality. Any graph of chordality 3
is referred to as chordal graph. A chordal graph becomes a plane triangulation in the case when it is planar and 3-
connected. According to [11], VC (and, as a consequence, the IPGD problem for small r) is polynomially solvable
over chordal graphs. An explanation of this fact is given in [12], where the result on polynomial solvability of
VC is proved over classes of planar graphs of bounded chordality. Here it is demonstrated that the infinite one
does not imply NP-hardness of VC (and IPGD) over subclasses of general plane triangulations.
Our result also extends the result from [7] that claims NP-hardness of VC for graphs obtained after a finite
number of stellations of 3-connected 3-regular plane graphs where a single stellation consists in a series of ele-
mentary ones (applied for pairwise edge non-intersecting faces) which themselves amount to adding an additional
vertex inside some face of a (3-connected) plane graph along with adding the edges connecting it with the set of
vertices of that face. Such stellated graphs from [7] are not triangulations in general. Even though sequential
application of stellations finally leads to triangulation, building the reduction from an NP-complete problem
201
requires additional graph constructions.
Let R(E) be the smallest radius of the disk that intersects all segments from E. The value of R(E) can be
calculated in time O(|E|) [5]. We finish our complexity analysis of the IPGD problem with respect to r by noting
that in the case when r is at the same scale as R(E), i.e., is within some multiplicative constant 0 < θ0 < 1 from
R(E), IPGD admits polynomial (in time and space) algorithm whose complexity depends exponentially on θ0 .
This setting is closely related to the parameterized complexity one because having r scaled with respect to R(E)
implies an upper bound on the optimum of IPGD problem that depends on θ0 .
2 Our results
Computational complexity of IPGD for plane graphs is studied under additional assumptions both on radius r
r
and (geometric) plane graph size. More specifically, we have the parameter λ = λ(G) = R(E) bounded from below
while keeping another parameter µ = µ(G) = ke max k2
kemin k2 bounded from above by some polynomially computable
functions of the input length where kemax k2 and kemin k2 are euclidean lengths of the longest and shortest edges
of G respectively. It is easy to note that given some r > 0, we can scale a plane graph in such a way that makes
r extremely small or large with respect to R(E). Therefore the first parameter defines the scale of the problem
while the second serves as a measure of variance of edge lengths of the graph G. Fixing these two parameters is
natural because in practice the value of r is chosen to be adequate with respect to the network size.
IPGD problem over a connected plane graph can be transformed in polynomial time and space (in |E|) into an
equivalent one for the same graph where disk centers are chosen from some finite set Dr (G), which is referred to
as the discrete IPGD problem in the sequel. Indeed, consider an arbitrary maximum (with respect to inclusion)
subsystem (MFS) of objects (i.e., r-neighbourhoods of graph edges) from N having a nonempty intersection.
W.l.o.g., we can assume that an optimal solution to the IPGD problem consists of centers of radius r disks, each
of which lies in the intersection of some MFS. The set M of points at the intersection of an arbitrary MFS is
bounded, closed and convex. Moreover, M has a boundary (denote it by bd M ), which is composed of pieces of
boundaries of objects from N . Due to the connectedness of G, the set M is contained in the intersection of at
least two objects from N . Consider the degenerate case where two edges e1 and e2 from E are parallel and have
their r-neighbourhoods touching in such a way that touching points form a segment. In this case, obviously,
|bd Nr (e1 ) ∩ bd Nr (e2 )| = ∞. It is also possible when edges e1 and e2 intersect at their common vertex. In both
cases, bd Nr (e1 ) ∩ bd Nr (e2 ) has at most 2 extreme points of intersection. In the other (non-degenerate) ones,
|bd Nr (e1 ) ∩ bd Nr (e2 )| is obviously bounded by some absolute constant taking into account the fact that each
bd Nr (e), e ∈ E is compound of a pair of parallel straight line segments and of a pair of half-circles. Set
Dr (G) = {u ∈ R2 : u ∈ extr (bd Nr (e1 ) ∩ bd Nr (e2 )) , e1 , e2 ∈ E},
where extr N means the set of (extreme in two aforementioned degenerate cases) points of one-dimensional set N.
It is easy to note that M has at least one vertex which is just a (possibly extreme) point of bd Nr (e1 ) ∩ bd Nr (e2 )
for some distinct edges e1 , e2 ∈ E. W.l.o.g. we can restrict each point of feasible solution to the IPGD problem
to lie in the set Dr (G) of cardinality of the order O(|E|2 ), which can be found in polynomial (in |E|) time. Let
us observe that unlike the general IPGD problem each feasible solution to the discrete IPGD one has cardinality
that is bounded by O(|E|2 ).
2.1 NP-hardness of IPGD over highly connected triangulations for small r
Below the computational complexity of discrete IPGD will be studied over highly connected triangulations where
r is small with respect to R(E). In fact, both in VC (over plane graphs) and discrete IPGD problems, cardinalities
of hitting sets are minimized for finite sets of straight line segments and their r-neighbourhoods respectively. We
can prove that for small r these two problems become equivalent in the following sense, being defined on the
same plane graphs:
1. every feasible solution to VC can be converted in polynomial time and space in |E| to some feasible solution
of discrete IPGD keeping its cardinality;
2. every feasible solution to discrete IPGD can be converted in polynomial time and space to some feasible one
for VC with the same cardinality counting multiplicity.
The following lemma reduces the IPGD problem to VC for small r.
202
2
Lemma 1. Let G = (V, E, F ) be a plane graph with V ⊂ Z . The discrete IPGD problem over the graph G is
1
equivalent to VC for the same graph where r = Θ diam V and diam V is the (geometric) diameter of V.
Fary embedding [10] is a polynomial (in time and space) algorithm that gives a straight line drawing of a
simple planar graph with n vertices on the integer grid of the size 2n − 4 × n − 2. In view of Lemma 1, the IPGD
problem inherits the VC problem complexity status being considered over the respective plane graph classes
on the integer grid where r is small. In the recent complexity research for the VC problem, its computational
complexity is studied over hereditary graph classes, see e.g. [4], [12]. Example below demonstrates that 4-
connected plane triangulations constitute a hereditary class neither with respect to vertex deletions nor with
respect to edge contractions. It is assumed that the graph resulting from a single edge contraction is without
multiple edges.
Example 1. In the Fig. 1, 4-connected plane triangulation T1 is shown. Contracting the edge v3 v9 leads
to plane triangulation T2 , which contains non-facial 3-cycle v3 v5 v10 . This implies that T2 is not 4-connected.
Deleting either the vertex v8 or edge v3 v8 leads to non-triangular faces.
v1 b
v5 b v6
b b v4
v10
b
v8 b b v7
b b b
v3 v9 v2
Figure 1: Contracting the edge v3 v9 causes 4-connected plane triangulation T1 to become only 3-connected
Now comes our main result.
Theorem 1. For λ = Θ n12 and µ = O(n), discrete IPGD (and VC) is strongly NP-hard over the class of
4-connected (Hamiltonian) plane triangulations whose vertices have degree not exceeding O(log n), where n is the
number of vertices of triangulation.
In view of polynomial solvability of VC (and IPGD for small r) over classes of plane graphs of bounded
chordality [12], it is interesting whether the unbounded one could demonstrate NP-hardness of these problems
over subclasses of general plane triangulations. Below an example is given of the subclass of 3-connected general
plane triangulations of infinite chordality for which both VC and IPGD problems admit efficient polynomial-time
algorithm.
Example 2. Let p ≥ 2. Applying a sequence of elementary stellations to an axis-parallel square mesh of size
2p × 2p on the integer grid, we obtain a general triangulation and the corresponding class GT 0 of such ones over
all positive integers p. The class GT 0 has infinite chordality but the VC problem for every graph from GT 0 can
be solved in the time that is linear with respect to the number of vertices. Vertices of squares form a minimum
vertex cover of the cardinality 4p2 + 4p + 1.
Minimality follows by induction on p. For p = 2, it is proved by a tedious check. Assume that for the stellated
square mesh of size 2(p − 1) × 2(p − 1) the minimum cardinality of vertex cover is 4(p − 1)2 + 4(p − 1) + 1. The
edges of the last (2p − 1)th and 2pth stellated rows and columns require at least 8p additional vertices to be
covered, which sums up to 4p2 + 4p + 1.
Though an arbitrary 4-connected plane triangulation is isomorphic (in the usual graph sense) to some Delaunay
triangulation [8], it is still an open (possibly NP-hard) problem of getting combinatorially equivalent Delaunay
triangulation for a given 4-connected plane one (see e.g. a survey [14]). We hope it is possible to do it in
polynomial time and space, at least for certain subclasses of 4-connected plane triangulations.
Conjecture 1. VC and IPGD are NP-hard even over 4-connected Delaunay triangulations whose vertices have
degrees not exceeding O(log n), where n is the number of vertices in triangulation.
203
2.2 Polynomial solvability of IPGD over connected plane graphs for large r
The complexity analysis above boils down to the NP-hardness of IPGD over triangulations for extremely small
r. Let us finish our study with some final notes about its computational complexity for large r. First, it is
obvious that the IPGD problem is solvable over connected plane graphs for λ ≥ 1 in the time O(|E|) [5]. Let us
consider the case of IPGD over this graph class where 0 < λ < 1. In view of the fact that each disk of radius r
√ l√ m2 l √ m2
2R(E)
contains an axis-parallel rectangle whose side is r 2, roughly at most k = k(λ) = r = λ2 disks are
needed to intersect all segments from E. Therefore, the brute-force search algorithm could be applied that just
sequentially tries each subset of Dr (G) of cardinality of at most k, which amounts roughly to O k 2 |E|2k+1 time
complexity. Therefore, having λ ≥ θ0 for some absolute constant 0 < θ0 < 1, we arrive at the polynomial time
and space algorithm whose complexity depends exponentially on θ0 . The considered setting is closely related to
parameterized complexity one and it would be interesting to refine this complexity bound at least over proximity
graphs (e.g., Delaunay triangulations and other distance-based graphs).
3 Conclusion
The computational complexity of the problem of intersecting a structured set of straight line segments with
the fewest number of disks of radii r > 0 is studied, where the structural information about segments is given
in the form of an edge set of some connected plane graph. It is proved that the problem is NP-hard even for
highly connected triangulations for small r but admits a polynomial time and space solution over connected
plane graphs for the case of a large one.
Acknowledgements
Our work was supported by the Russian Science Foundation, project 14-11-00109.
References
[1] P. K. Agarwal, A. Efrat, S. K. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman. Network vulnerability
to sinlge, multiple and probabilistic physical attacks. Proceedings of Military Communication Conference,
1824–1829, 2010.
[2] P.K. Agarwal, A. Efrat, S.K. Ganjugunte, D. Hay, S. Sankararaman, G. Zussman. The resilience of WDM
networks to probabilistic geographical failures. IEEE/ACM Transactions of Network, 21:1525–1538, 2013.
[3] P. K. Agarwal, S. Har-Peled, H. Kaplan, M. Sharir. Union of random Minkowski sums and network vulner-
ability analysis. Discrete and Computational Geometry, 52(3):551–582, 2014.
[4] V. E. Alekseev, V. Lozin, D. Malyshev, M. Milanic. The maximum independent set problem in planar
graphs. Lecture Notes in Computer Science: Mathematical Foundations in Computer Science, 5162:96–107,
2008.
[5] B. K. Bhattacharya, S. Jadhav, A. Mukhopadhyay, J. M. Robert. Optimal algorithms for some intersection
radius problems. Computing, 52(3):269–279, September 1994.
[6] P. Bose, D. Kirckpatrick, Z. Li. Worst case optimal algorithms for guarding planar graphs and polyhedral
surfaces. Computational Geometry, 26:209–219, 2003.
[7] G. Das, M. T. Goodrich. On the complexity of optimization problems for 3-dimensional convex polyhedra
and decision trees. Computational Geometry, 8:123–137, 1997.
[8] M. B. Dillencourt, W. D. Smith. Graph-theoretical conditions for inscribability and Delaunay realizability.
Discrete Mathematics, 161:63–77, 1996.
[9] H. Fleischner, G. Sabidussi, V. I. Sarvanov Maximum independent sets in 3- and 4-regular Hamiltonian
graphs. Discrete Mathematics, 310(20):2742–2749, 2010.
[10] H. Fraysseix. Small sets supporting Fary embeddings of planar graphs. Proceedings of 20th annual ACM
symposium on theory of computing, 426–433, 1988.
204
[11] F. Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum
independent set of a chordal graph. SIAM Journal of Computing, 1(2):180–187, 1972.
[12] M. Kaminski, V. V. Lozin, M. Milanic Recent developments on graphs of bounded clique-width. Discrete
Applied Mathematics, 157:2747–2761, 2009.
[13] B. Mohar. Face covers and the genus problem for apex graphs. Journal of Combinatorial Theory, series B,
82(1):102–117, May 2001.
[14] J. Pach. Thirty essays on geometric graph theory. Springer, 2013.
[15] J. O’Rourke. Art gallery theorems and algorithms. Oxford University Press, 1987.
205