Algorithms Data Structures 15th PDF
Algorithms Data Structures 15th PDF
Algorithms
and Data Structures
15th International Symposium, WADS 2017
St. John's, NL, Canada, July 31 August 2, 2017
Proceedings
123
Lecture Notes in Computer Science 10389
Commenced Publication in 1973
Founding and Former Series Editors:
Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board
David Hutchison
Lancaster University, Lancaster, UK
Takeo Kanade
Carnegie Mellon University, Pittsburgh, PA, USA
Josef Kittler
University of Surrey, Guildford, UK
Jon M. Kleinberg
Cornell University, Ithaca, NY, USA
Friedemann Mattern
ETH Zrich, Zrich, Switzerland
John C. Mitchell
Stanford University, Stanford, CA, USA
Moni Naor
Weizmann Institute of Science, Rehovot, Israel
C. Pandu Rangan
Indian Institute of Technology, Madras, India
Bernhard Steffen
TU Dortmund University, Dortmund, Germany
Demetri Terzopoulos
University of California, Los Angeles, CA, USA
Doug Tygar
University of California, Berkeley, CA, USA
Gerhard Weikum
Max Planck Institute for Informatics, Saarbrcken, Germany
More information about this series at http://www.springer.com/series/7407
Faith Ellen Antonina Kolokolova
Algorithms
and Data Structures
15th International Symposium, WADS 2017
St. Johns, NL, Canada, July 31 August 2, 2017
Proceedings
123
Editors
Faith Ellen Jrg-Rdiger Sack
University of Toronto Carleton University
Toronto, ON Ottawa, ON
Canada Canada
Antonina Kolokolova
Memorial University of Newfoundland
St. Johns, NL
Canada
This volume contains the papers presented at the 15th International Algorithms and
Data Structures Symposium (WADS 2017), which was held from July 31 to August 2,
2017, in St. Johns, Newfoundland, Canada. WADS, which alternates with the Scan-
dinavian Symposium and Workshops on Algorithm Theory, SWAT, is a forum for
researchers in the area of design and analysis of algorithms and data structures.
In response to the call for papers, 109 papers were submitted. From these sub-
missions, the Program Committee selected 49 papers for presentation at WADS 2017,
using a combination of online discussion in EasyChair and a one-day video conference.
In addition, invited lectures were given by Pankaj Agarwal (Duke University), Michael
Saks (Rutgers University), and Virginia Vassilevska Williams (MIT).
Special issues of papers selected from WADS 2017 are planned for two journals,
Algorithmica and Computational Geometry: Theory and Applications.
We gratefully acknowledge the support of the WADS 2017 sponsors: Memorial
University of Newfoundland, The Fields Institute for Research in Mathematical
Sciences, Elsevier, and Springer.
Steering Committee
Frank Dehne Carleton University, Canada
Faith Ellen University of Toronto, Canada
Ian Munro University of Waterloo, Canada
Jrg-Rdiger Sack Carleton University, Canada
Roberto Tamassia Brown University, USA
Program Committee
Ittai Abraham VMware Research, Israel
Hee-Kap Ahn Pohang University of Science and Technology, Korea
Nina Amenta University of California, Davis, USA
Sayan Bhattacharya University of Warwick, UK
Therese Biedl University of Waterloo, Canada
Joan Boyar University of Southern Denmark, Denmark
Martin Dietzfelbinger Technische Universitt Ilmenau, Germany
Stephane Durocher University of Manitoba, Canada
Funda Ergun Indiana University, USA
Martn Farach-Colton Rutgers University, USA
Fedor Fomin University of Bergen, Norway
Travis Gagie Diego Portales University, Chile
Thore Husfeld IT University of Copenhagen, Denmark
and Lund University, Sweden
Michael Kerber Graz University of Technology, Austria
David Kirkpatrick University of British Columbia, Canada
Ramesh Krishnamurti Simon Fraser University, Canada
Kasper Green Larsen Aarhus University, Denmark
Vangelis Markakis Athens University of Economics and Business, Greece
Aleksandar Nikolov University of Toronto, Canada
Naomi Nishimura University of Waterloo, Canada
VIII Organization
Additional Reviewers
Pankaj K. Agarwal
This work is supported in part by NSF under grants CCF-15-13816, CCF-15-46392, and IIS-14-08846,
by ARO grant W911NF-15-1-0408, and by grant 2012/229 from the U.S.-Israel Binational Science
Foundation.
How efciently can easy dynamic programs be
approximated?
Michael Saks
whose running time is only polylogarithmic in the length of the input. For the
special case of LCS-distance between two permutations of f1; . . .; ng (Ulam
Distance), Naumovitz, Saks and Seshadhri [9] (following earlier work of
Andoni and Nguyen [5]) obtained such an additive approximation running in
~ pn.
time O
References
1. Abboud, A., Backurs, A.: Towards hardness of approximation for polynomial time prob-
lems. In: Conference on Innovations in Theoretical Computer Science (ITCS) (2017)
2. Abboud, A., Backurs, A., Williams, V.V.: Quadratic-Time Hardness of LCS and other
Sequence Similarity Measures. CoRR, abs/1501.07053 (2015)
3. Ailon, N., Chazelle, B., Comandur, S., Liu, D.: Estimating the distance to a monotone
function. Random Struct. Algorithms 31, 371383 (2017)
4. Andoni, A., Krauthgamer, R., Onak, K.: Polylogarithmic approximation for edit distance and
the asymmetric query complexity. In: IEEE Symposium on Foundations of Computer
Science (FOCS), pp. 377386 (2010)
5. Andoni, A., Nguyen, H.L.: Near-optimal sublinear time algorithms for Ulam distance. In:
Proceedings of the 21st Symposium on Discrete Algorithms (SODA), pp. 7686 (2010)
6. Backurs, A., Indyk, P.: Edit distance cannot be computed in strongly subquadratic time
(unless SETH is false). In: Proceedings of the Forty-Seventh Annual ACM on Symposium
on Theory of Computing (STOC), pp. 5158 (2015)
7. Bringmann, K.: Why walking the dog takes time: Frechet distance has no strongly sub-
quadratic algorithms unless SETH fails. CoRR, abs/1404.1448 (2014)
8. Bringmann, K., Kunnemann, M.: Quadratic conditional lower bounds for string problems
and dynamic time warping. In: Proceedings of the 56th Annual IEEE Symposium on
Foundations of Computer Science (FOCS), pp. 7997 (2015)
9. Naumovitz, T., Saks, M., Seshadhri, C.: Accurate and nearly optimal sublinear approxi-
mations to Ulam distance. In: SIAM-ACM Symposium on Discrete Algorithms, pp. 2012
2031 (2017)
10. Parnas, M., Ron, D., Rubinfeld, R.: Tolerant property testing and distance approximation.
J. Comput. Syst. Sci. 6, 10121042 (2006)
11. Saks, M., Seshadhri, C.: Estimating the longest increasing sequence in polylogarithmic time.
SIAM J. Comput. 46(2), 774823 (2017)
Fine-Grained Complexity of Problems in P
Supported by an NSF CAREER Award, NSF Grants CCF-1417238, CCF-1528078 and CCF-1514339,
and BSF Grant BSF:2012338.
Contents
d-Greedy t-spanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Gali Bar-On and Paz Carmi
The Complexity of Drawing Graphs on Few Lines and Few Planes. . . . . . . . 265
Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky,
Oleg Verbitsky, and Alexander Wolff
1 Introduction
can be modelled as line segment covering problem, where the links can be
interpreted as straight-line segments and the objects can be interpreted as unit
squares. In [9], several other applications are also stated.
We study the following variations of covering problem for line segments which
are classied depending upon their lengths and orientations.
Continuous Covering
Discrete Covering
We dene some terminologies and denitions used in this paper. We use seg-
ment to denote a line segment, and unit square to denote an axis-parallel unit
square. For a given non-vertical segment s, we dene l(s) and r(s) to be its left
and right end-points. For a vertical segment s, l(s) and r(s) are dened to be the
end-points of s with highest and lowest y-coordinates respectively. The center
of a square t is the point of intersection of its two diagonals. We use t(a, b) to
denote a square whose center is at the point a and whose side length is b.
Known results: Arkin et al. [2] studied a related problem the conict-free
covering . Given a set P of n color classes, where each color class contains exactly
two points, the goal is to nd a set of conict-free objects of minimum cardinality
which covers at least one point from each color class. An object is said to be
conict-free if it contains at most one point from each color class. Arkin et al.
[1, 2] showed that, both discrete and continuous versions of conict-free covering
problem are NP-complete where the points are on a real line and objects are
intervals of arbitrary length. These results are also valid for covering arbitrary
length segments on a line with unit intervals. They provided 2- and 4-factor
approximation algorithms for the continuous and discrete versions of conict-
free covering problem with arbitrary length intervals respectively. If the points
of the same color class are either vertically or horizontally unit separated, then
they proved that the continuous version of the conict-free covering problem with
axis-parallel unit squares is NP-complete, and proposed a factor 6 approximation
algorithm. Finally, they remarked the existence of a polynomial time dynamic
programming based algorithm for the continuous version of conict-free covering
problem with unit intervals where the points are on a real line and each pair of
Covering Segments with Unit Squares 3
same color points is unit separated. Recently, Kobylkin [9] studied the problem
of covering the edges of a given straight line embedding of a planar graph by
minimum number of unit disks, where an edge is said to be covered by a disk if
any point on that edge lies inside that disk. He proved NP-completeness results
for some special graphs. A similar study is made in [10], where a set of line
segments is given, the objective is to cover these segments with minimum number
of unit disks, where the covering of a segment by a disk is dened as in [9]. For
continuous version of the problem, they proposed a PTAS where the segments
are non-intersecting. For the discrete version, they showed that the problem is
APX-hard.
Our contributions: In Section 2, we show that the CCSUS-H1 problem is NP-
complete, and propose an O(n log n) time factor 3 approximation algorithm for
the CCSUS-HV1 problem. This improves the factor 6 approximation result of
Arkin et al. [2] while keeping the time complexity unchanged. We also provide
a PTAS for CCSUS-HV1 problem. For the CCSUS-ARB problem, we give an
O(n log n) time factor 6 approximation algorithm. In Section 3, give a polynomial
time factor 16 approximation algorithm for the DCSUS-ARB problem.
2 Continuous covering
In this version, the segments are given, and the objective is to place minimum
number of unit squares for covering at least one end-point of all the segments.
Let S be a set of n horizontal unit segments inside a unit height horizontal strip.
Start with an empty set T . Sort the segments in S from left to right with respect
to their right end-points. Repeat the following steps until all segments of S are
processed. In each step, select the left-most segment s among the uncovered
segments in S. Add a unit square t T which is inside the strip aligning its
left boundary at r(s). Mark all the segments that are covered by t as processed.
Finally, return T as the output. Thus, we have an O(n log n) time algorithm for
the CCSUS-H1-US problem.
that no two line segments corresponding to two dierent clauses intersect. The
objective is to nd a satisfying assignment of . See Figure 1(a) for an instance
of RPSAT(3) problem. Here the solid (resp. dotted) vertical segment attached to
the horizontal line of a clause represents that the corresponding variable appears
as a positive (resp. negative) literal in that clause.
(a) (b)
(c)
Fig. 1. (a) RPSAT(3) representation. (b) Connection of a cycle and a chain. (c) Cycle
gadget for a variable xi .
(a) (b)
(c) (d)
Fig. 2. Gadget for (a) type (i) chain, (b) type (ii) chain (c) type (iii) chain, and (d)
Demonstration of clause-segment s corresponding to the clause C = (xi xj xk );
shaded portions in (a), (b), (c) represent the connection of s with the variables in C .
Observation 1 Exactly half of the squares (either all empty or all shaded) can
cover all the segments in the big-cycle corresponding to the variable xi . This
solution represents the truth value (empty for true and shaded for false) of the
corresponding variable xi .
Further, for the clause C , we take a single unit horizontal segment s that
connects the chain corresponding to three variables. This is referred to as a
clause-segment. The placement of s is shown in Figure 2(d). Note that, in
order to maintain the alternating empty and shaded vertical layers in a variable
6 A. Acharyya et al.
gadget we may need to reduce the distance between two consecutive vertical
layers of squares. But, the segments are placed suciently apart so that no
unit square can cover more than two segments from a variable gadget. As the
number of segments (Q) considering all variable gadgets, is even, we need exactly
Q
2 squares to cover them. Now, if a clause C is satisable then at least one square
connected to s will be chosen, and hence s will be covered; if C is not satisable
then the square adjacent to s of each variable chain will not be chosen in the
solution, and hence we need one more square to cover s (see Figure 2(d)). Thus,
we have the following result.
ing to the gadget of variable xi . If the formula is not satisable then N > N0 ,
Clearly, (i) CCSUS-H1 problem is in NP, and (ii) number of squares and seg-
ments used in the reduction is polynomial in the the size of RPSAT(3) problem.
Here, we have both horizontal and vertical segments in S which are of unit length.
An easy way to get a factor 4 approximation algorithm for this problem is as fol-
lows. Let S = SH SV , where SH and SV are the sets of horizontal and vertical
unit segments respectively. By Theorem 2, we already have a factor 2 approxima-
tion algorithm for covering the members in SH (resp. SV ). If QH and QV be the
Covering Segments with Unit Squares 7
(a) (b)
Fig. 3. (a) Placement of unit squares for a horizontal and vertical unit segment s.
left, and then onwards each k-strip is formed with k consecutive unit vertical
strips except the last k-strip which may contain lesser than k vertical strips.
Similarly, k shifts are dened in horizontal direction. Now consider shift(i, j)
as the i-th vertical shift and j-th horizontal shift. This splits the box B into
rectangular cells of size at most k k. The following observation is important
to analyze the complexity of our algorithm.
Observation 2 There exists an optimal solution that contains squares such that
two boundaries of each square is attached to an end-point(s) of some segments.
2
Lemma 2. Finding a feasible solution for each shif t(i, j) requires O(n2k ) time.
In our algorithm, for each shif t(i, j) we calculate optimal solution in each cell
and combine them to get a feasible solution. Finally, return the minimum among
these k 2 feasible solutions.
Let OP T be an optimum set of unit squares covering S, and Q be a feasible so-
lution returned by our algorithm described above. Following the proof technique
of Lemma 2.1 of [7], we can prove the following theorem.
Theorem 4. |Q| (1 + k1 )2 |OP T | and the running time of the above algorithm
2
is O(k 2 n2k ).
Here also we start with an empty set OU T P U T and LB, and each segment in S
is attached with a ag bit. We maintain a range tree T with the end-points of the
members in S. Each time, an arbitrary segment s S with f lag(s) = 0 is chosen,
and inserted in LB. Its ag bit is set to 1. Insert four unit squares {t1 , t2 , t3 , t4 }
which fully cover the square t(l(s), 2) and four unit squares {t1 , t2 , t3 , t4 } which
fully cover the square t(r(s), 2) in OU T P U T . Remove all the segments in S that
are covered by {t1 , t2 , t3 , t4 , t1 , t2 , t3 , t4 } by performing range searching in T as
stated in Section 2.3. The end-points of the deleted segments are also deleted
from T . This process is repeated until all the members in S are agged. Finally,
return the set OU T P U T . Observation 3 suggests the following result.
Lemma 3. The above algorithm for CCSUS-ARB problem runs in O(n log n)
time, and the produced solution is factor 8 approximation of the optimal solution.
Proof. Let T1 T (resp. T2 T ) be the set of all squares which cover the left
(resp. right) end-points of the segments in S. Consider binary variable xi for
each square ti T1 , and yj for each square tj T2 . Create an ILP as follows.
Z0 : min xi + yj
i|ti T1 j|tj T2
s.t. xi + yj 1 k | sk S; xi , yj {0, 1} i | ti T1 & j | tj T2
i|l(sk )ti T1 j|r(sk )tj T2
Z1 : min xi Z2 : min yj
i|ti T1 j|tj T2
s.t. xi 1, k | sk S1 s.t. yj 1, k | sk S2
i|l(sk )ti T1 j|r(sk )tj T2
xi {0, 1} i | ti T1 yj {0, 1} j | tj T 2
1
The left end-point of a vertical segment is dened as its top end-point.
10 A. Acharyya et al.
Observe that, both the ILP s, Z1 and Z2 are the problems of covering points by
unit squares. We consider the problem Z1 , and use a multilevel LP relaxation
(see Theorem 6 stated below) to have a factor 8 approximation algorithm for the
DCPUS problem. It consists of 3 steps of LP relaxations. In each step, we use
linear programming to partition the considered points into two disjoint subsets,
and nally we reach to the Restricted-Point-Cover problem, as follows.
Restricted-Point-Cover : Given a point set P in IR2 above the x-axis and
a set R of unit width (x-span) rectangles such that bottom boundary of each
rectangle in R coincides with x-axis, nd a subset of R of minimum size to cover
all the points in P .
C OP TRP C
I F
In Section 3.2 of [3], Bansal and Pruhs showed that OP TRP
for some positive constant for a more generic version of this problem. In our
simplied case 2 for the proof of Lemma 5).
Chan et al. [5] proposed an O(1)-approximation algorithm for the DCPUS prob-
lem using quasi-uniform sampling. Thus using Lemma 4, we have an O(1) ap-
proximation for our DCSUS-ARB problem. However, the following theorem says
that one can get a factor 8 approximation algorithm for the DCPUS problem.
Theorem 6. For the standard ILP formulation of the DCPUS problem Z1 with
a set of points P1 and a set of unit squares T1 , if OP T1I and OP T1F are the op-
timum solutions of Z1 and its LP-relaxation respectively, then OP T1I 8OP T1F .
Z1 : min xi + yj
i|ti T11 j|tj T12
s.t. xi + yj 1 p P1 ; xi , yj {0, 1} i | ti T11 & j | tj T12
i|pti T11 j|ptj T12
Z11 : min xi Z12 : min yj
i|ti T11 j|tj T12
s.t. xi 1, p P11 s.t. yj 1, p P12
i|pti T11 j|ptj T12
Z11 : min xi
i|ti T11
s.t. xi 1 p P111 , and xi 1 p P112
i|pti T11 i|pti T11
xi {0, 1} i | ti T11
Again, since the sets P111 and P112 are disjoint, we may consider the following
two ILP s, Z111 and Z112 as follows.
Z111 : min xi Z112 : min xi
i|ti T11 i|ti T11
s.t. xi 1 p P111 s.t. xi 1 p P112
i|pti T11 i|pti T11
xi {0, 1} i | ti T11 xi {0, 1} i | ti T11
be an optimal fractional solution of Z11 . Clearly, x
Let x satises all the con-
F F
straints in both Z111 and Z112 . Also, it is observe that OP T111 OP T11 and
F F F F F
OP T112 OP T11 . Combining, we conclude that OP T111 +OP T112 2OP T11 .
A similar equation can be shown for Z12 as follows: OP T121
F F
+OP T122 F
2OP T12 .
Finally, we have the following four equations,
12 A. Acharyya et al.
F F F
1. OP T111 + even OP T112 2 even OP T11 2OP T11
F
,
even F F F
odd OP T122 2 odd OP T12 2OP T12 ,
F
2. odd OP T121 +
Step 3: In this step we apply Lemma 5 independently on each of Z111 , Z112 , where
is even, and Z121 , Z122 where is odd to get the following four equations.
I F I F
(i) OP T111 2OP T111 , (ii) OP T112 2OP T112 ,
I F I F
(iii) OP T121 2OP T121 , (iv) OP T122 2OP T122 .
References
1. E. M. Arkin, A. Banik, P. Carmi, G. Citovsky, M. J. Katz, J. S. B. Mitchell, and
M. Simakov. Choice is hard. In ISAAC, pages 318328, 2015.
2. E. M. Arkin, A. Banik, P. Carmi, G. Citovsky, M. J. Katz, J. S. B. Mitchell, and
M. Simakov. Conict-free covering. In CCCG, 2015.
3. N. Bansal and K. Pruhs. The geometry of scheduling. SIAM J. Comput.,
43(5):16841698, 2014.
4. A. Biniaz, P. Liu, A. Maheshwari, and M. Smid. Approximation algorithms for the
unit disk cover problem in 2D and 3D. Computational Geometry, 60:818, 2016.
5. T. M. Chan, E. Grant, J. Konemann and M. Sharpe. Weighted capacited, priority,
and geometric set cover via improved quasi-uniform sampling In SODA, Pages
15761585, 2012.
6. D. R. Gaur, T. Ibaraki, and R. Krishnamurti. Constant ratio approximation algo-
rithms for the rectangle stabbing problem and the rectilinear partitioning problem.
Journal of Algorithms, 43(1):138152, 2002.
7. D. S. Hochbaum and W. Maass. Approximation schemes for covering and packing
problems in image processing and VLSI. J. ACM, 32(1):130136, January 1985.
8. D. E. Knuth and A. Raghunathan. The problem of compatible representatives.
SIAM Journal on Discrete Mathematics, 5(3):422427, 1992.
9. K. Kobylkin. Computational complexity of guarding of proximity graphs. CoRR,
abs/1605.00313, 2016.
10. R. R. Madireddy and A. Mudgal. Stabbing line segments with disks and related
problems. In CCCG, 2016.
Replica Placement on Bounded Treewidth
Graphs
1 Introduction
We study a form of capacitated set cover problem [5] called replica placement
(RP) that nds applications in settings such as data distribution by internet
service providers (ISPs) and video on demand service delivery (e.g., [6, 8]). In
this problem, we are given a graph representing a network of servers and a set
of clients. The clients are connected to the network by attaching each client to
a specic server. The clients need access to a database. We wish to serve the
clients by placing replicas (copies) of the database on a selected set of servers
and clients. While the selected clients get served by the dedicated replicas (i.e.,
cached copies) placed on themselves, we serve the other clients by assigning
them to the replicas on the servers. The assignments must be done taking into
account Quality of Service (QoS) and capacity constraints. The QoS constraint
stipulates a maximum distance between each client and the replica serving it.
The clients may have dierent demands (the volume of database requests they
make) and the capacity constraint species the maximum demand that a replica
can handle. The objective is to minimize the number of replicas opened. The
problem can be formally dened as follows.
Problem Denition (RP): The input consists of a graph G = (V, E), a set
of clients A and a capacity W . Each client a is attached to a node u V, denoted
att(a). For each client a A, the input species a request r(a) and a distance
dmax (a). For a client a A and a node u V, let d(a, u) denote the length
of the shortest path between u and att(a), the node to which a is attached
Corresponding author
Arora et al. [1] made progress towards handling DAGs of bounded treewidth
and designed an algorithm for the case of bounded-degree, bounded-treewidth
graphs. Their algorithm achieves an approximation ratio of O( + t), where
is the maximum degree and t is the treewidth of the DAG. Their result also ex-
tends for networks comprising of bounded-degree bounded-treewidth subgraphs
connected in a tree like fashion.
Our Result and Discussion: We study the RP problem on undirected
graphs of bounded treewidth. Our main result is an O(t)-approximation algo-
rithm running in polynomial time (the polynomial is independent of t and the
approximation guarantee). In contrast to prior work, the approximation ratio
depends only on the treewidth and is independent of parameters such as the
maximum degree.
Our algorithm is based on rounding solutions to a natural LP formulation, as
in the case of prior work [2, 1]. However, the prior algorithms exploit the acyclic
nature of the graphs and the bounded degree assumption to transform a given
LP solution to a solution wherein each client is assigned to at most two replicas.
In other words, they reduce the problem to a capacitated vertex cover setting,
for which constant factor rounding algorithms are known [10].
The above reduction does not extend to the case of general bounded treewidth
graphs. Our algorithm is based on an entirely dierent approach. We introduce
the notion of clustered solutions, wherein the partially open nodes are grouped
into clusters and each client gets served only within a cluster. We show how
to transform a given LP solution to a new solution in which a partially-open
node participates in at most (t + 1) clusters. This allows us to derive an overall
approximation ratio O(t). The notion of clustered solutions may be applicable
in other capacitated set cover settings as well.
Other Related Work: The RP problem falls under the framework of the
capacitated set cover problem (CSC), which admits an O(log n)-approximation
[5]. Two versions of the CSC problem have been studied: soft capacity and hard
capacity settings. Our work falls under the more challenging hard capacity set-
ting, wherein a set can be picked at most once. The capacitated versions of the
vertex cover problem (e.g., [10]) and dominating set problem (e.g., [9]) have also
been studied. Our result applies to the capacitated dominating problem with
uniform capacities and yields O(t)-approximation.
Full Version: Due to space constraints, some of the proofs and details of
analysis could not be included in this version. A full version of the paper is
available as an Arxiv preprint (https://arxiv.org/abs/1705.00145).
(a) (b)
Fig. 1. (a) Illustration for clustered solution. Three clusters are shown C1 , C2 and C3 ,
open to an extent of 0.4, 0.4 and 0.5; the clusters are linked to the sets of fully-open
nodes {v1 , v2 , v4 }, {v1 , v2 , v3 , v4 }, and {v2 , v4 , v5 , v6 }. The solution is (0.5, 4)-clustered.
(b) Illustration for regions. The gure shows an example tree decomposition. The bags
lled solidly represent already identied boundary bags. All checkered bags belong to
the region headed by P .
3.1 De-capacitation
Consider an LP solution = x, y and let u be a partially-open or closed node.
The clients that can access u might have been assigned to other partially-open
nodes under . We call the node u de-capacitated, if even when all the above
assignments are transferred to u, the capacity at u is not exceeded; meaning,
x(a, v) < W,
au v: av vPO
Replica Placement on Bounded Treewidth Graphs 19
where PO is the set of partially-open nodes under (including u). The solution
is said to be de-capacitated, if all the partially-open and the closed nodes are
de-capacitated.
The preprocessing step transforms the input solution into a de-capacitated
solution by performing a pulling procedure on the partially-open and closed
nodes. Given a partially-open or closed node u, the procedure transfers assign-
ments from other partially-open nodes to u, as long as the capacity at u is not
violated. The procedure is shown in Figure 2, which we make use of in other
components of the algorithm as well.
Proof. We consider the partially-open and closed nodes, and process them in
an arbitrary order, as follows. Let u be a partially-open or closed node. Hy-
pothetically, consider applying the pulling procedure on u. The procedure may
terminate in one of two ways: (i) it exits mid-way because of reaching the ca-
pacity limit; (ii) the process executes in its entirety. In the former case, we fully
open u and perform the pulling procedure on u. In the latter case, the node u
is de-capacitated and so, we leave it as partially-open or closed, without per-
forming the pulling procedure. It is clear that the above method produces a
de-capacitated solution . We next analyze the cost of . Let s be the num-
ber of partially-open or closed nodes converted to be fully-open. Apart from
these conversions, the method does not alter the cost and so, cost( ) is at most
s + cost(). Let the total amount of requests be rtot = aA r(a). The extra
cost s is at most rtot /W , since any newly opened node is lled to its capacity.
Due to the capacity constraints, the input solution must also incur a cost of
at least rtot /W . It follows that cost( ) is at most 2 cost().
3.2 Clustering
them and perform the pulling procedure on these nodes. The advantage is that
the above nodes are de-capacitated and so, the pulling procedure would run to its
entirety (without having to exit mid-way because of reaching capacity limits).
As a consequence, the linkage between the nodes gets restricted, leading to a
clustered solution. Below we rst describe the transformation and then present
an analysis.
Transformation: Consider the given tree decomposition T . We select an
arbitrary bag of T and make it the root. A bag P is said to be an ancestor of a
bag Q, if P lies on the path connecting Q and the root; in this case, Q is called a
descendant of P . We consider P to be both an ancestor and descendant of itself.
A node u may occur in multiple bags; among these bags the one closest to the
root is called the anchor of u and it is denoted anchor(u). A region in T refers
to any set of contiguous bags (i.e., the set of bags induce a connected sub-tree).
In transforming into a clustered solution, we shall encounter three types
of nodes and it will be convenient to color them as red, blue and brown. To
start with, all the fully-open nodes are colored red and the remaining nodes
(partially-open nodes and closed nodes) are colored blue. The idea is to carefully
select a set of blue nodes, fully-open them and perform the pulling procedure on
these nodes; these nodes are then colored brown. Thus, while the blue nodes are
partially-open or closed, the red and the brown nodes are fully-open, with the
brown and blue nodes being de-capacitated.
The transformation identies two kinds of nodes to be colored brown: helpers
and boundary nodes. We say that a red node u V is proper, if it has at least
one neighbor v V which is a blue node. For each such proper red node u, we
arbitrarily select one such blue neighbor v V and declare it to be the helper
of u. Multiple red nodes are allowed to share the same helper. Once the helpers
have been identied, we color them all brown. The boundary brown nodes are
selected via a more involved bottom-up traversal of T that works by identifying
a set B of bags, called the boundary bags. To start with, B is initialized to be
the empty set. We arrange the bags in T in any bottom-up order (i.e., a bag
gets listed only after all its children are listed) and then iteratively process each
bag P as per the above order. Consider a bag P . We dene the region headed
by P , denoted Region(P ), to be the set of bags Q such that Q is a descendant
of P , but not the descendant of any bag already in B. See Figure 1 (b) for an
illustration. A blue node u is said to be active at P , if it occurs in some bag
included in Region(P ). Let active(P ) denote the set of blue nodes active at P .
We declare P to be a boundary bag and add it to B under three scenarios: (i) P
is the root bag. (ii) P is the anchor of some red node.(iii) the extent to which
the nodes in active(P ) are open is at least , i.e., uactive(P ) y(u) . If
P is identied as a boundary bag, then we select all the blue nodes appearing
in the bag and change their color to be brown. Once the bottom-up traversal
is completed, we have a set of brown nodes (helpers and boundary nodes). We
consider these nodes in any arbitrary order, open them fully, and perform the
pulling procedure on them. We take to be the solution obtained by the above
process. This completes the construction of . We note that a node may change
Replica Placement on Bounded Treewidth Graphs 21
its color from blue to brown in the above process, and the new color is to be
considered while determining the active sets thereafter. Notice that during the
whole process of the above transformation, the solution continues to remain
de-capacitated.
Analysis: We now show that is an (, t + 1)-clustered solution. To start
with, we have a set of red nodes that are fully-open and a set of blue nodes that
are either partially-open or closed under . The red nodes do not change color
during the transformation. On the other hand, each blue node u becomes active
at some boundary bag P . If u occurs in the bag P , it changes its color to brown,
otherwise it stays blue. Thus, the transformation partitions the set of originally
blue nodes into a set of brown nodes and a set of nodes that stay blue. In the
following discussion, we shall use the term blue to refer to the nodes that stay
blue. With respect to the solution , the red and brown nodes are fully-open,
whereas the blue nodes are partially-open or closed.
Recall that with respect to , two nodes u and v are linked, if there is a
client a assigned to both u and v. In order to prove the properties of (, t + 1)-
clustering, we need to analyze the linkage information for the blue nodes. We
rst show that the blue nodes cannot be linked to brown nodes, by proving the
following stronger observation.
Proposition 1 rules out the possibility of a blue node u being linked to any
brown node. Thus, u may be linked to a red node or another blue node. The
following lemma establishes a crucial property on the connectivity in these two
settings.
Lemma 5. (a) If two blue nodes u and v are linked under , then there must
exist a path connecting u and v consisting of only blue nodes. (b) If a blue node
u is linked to a red node v under , then there must exist a path p connecting u
and v such that barring v, the path consists of only blue nodes.
The transformation outputs a set of boundary bags B; let B denote the set
of non-boundary bags. If we treat the bags in B as cut-vertices and delete them
from T , the tree splits into a collection R of disjoint regions. Alternatively, these
regions can be identied in the following manner. For each bag P B and each
of its non-boundary child Q B, add the region headed by Q (Region(Q)) to
the collection R. Let the collection derived be R = {R1 , R2 , . . . , Rk }. It is easy
to see that R partitions B and that the regions in R are pairwise disconnected
(not connected by edges of the tree decomposition).
In order to show that is an (, t + 1)-clustered solution, let us suitably
partition the set of blue nodes into a collection of clusters C. For each region Rj ,
let Cj be the set of partially-open nodes that occur in some bag of Rj . We take
C to be the collection {C1 , C2 , . . . , Ck }. It can be veried that the collection C
is a partitioning of the set of partially-open nodes. Based on Lemma 5 we can
establish the following result.
22 A. Aggarwal et al.
The above proposition is proved via a cycle cancellation procedure that trans-
fers assignments amongst the nodes in F . The procedure can ensure that, except
for at most |F | clients, every other client a A is assigned to at most one node
from F . We open dedicated replicas at the exceptional clients and this results in
an cost increase of at most |F |.
The proposition does not alter the other assignments and so, its output solu-
tion is also (1/4, t + 1)-clustered. Given the proposition and the pre-processing,
we can assume that = x, y is (1/4, t+1)-clustered wherein each client a A is
assigned to at most one node from F and that y(a) 1/2. For each node ui F ,
let Ai A denote the set of clients assigned to the node ui . The proposition
guarantees that these sets are disjoint.
For a node v and a client a, let load(a, v) denote the amount of load imposed
by a on v towards the capacity: load(a, v) = x(a, v)r(a). It will be convenient
to dene the notion over sets of clients and nodes. For a set of clients B and
a set of nodes U , let load(B, U ) denote the load imposed by the clients in
B on the nodes U : load(B, U ) = aB,vU :av x(a, v)r(a); when the sets are
singletons, we
shall omit the curly braces. Similarly, for a subset C C, let
load(C ) = vC load(v).
The intuition behind the remaining transformation is as follows. We shall
identify a suitable set of nodes L = {v1 , v2 , . . . , vt+1 } from C, with vi being called
the consort of ui in C, and fully open all these nodes. Then, we consider the non-
consort nodes C = C L and for each i t+1, we transfer the load load(Ai , C )
to the node ui . As a result, no clients are assigned to the non-consort nodes any
more and so, they can be fully closed. In order to execute the transfer, for each
i t+1, we create space in ui by pushing a load equivalent to load(Ai , C ) from
ui to its (fully-opened) consort vi . The amount of load load(Ai , C ) involved in
the transfer is very small: the bounded opening property ensures that y(C) <
1/4 and thus, load(Ai , C ) < W/4. The fully-opened consort vi has enough
additional space to receive the load: y(vi ) 1/4 and so, load(A, vi ) W/4,
which means that if we fully open the consort, we get an additional space of
(3/4)W . However, an important issue is that a consort vi may not be accessible to
all the clients in Ai . Therefore, we need to carefully choose the consorts in such a
manner that each fully open node ui has enough load accessible to the consort vi
that can be pushed to vi . Towards this purpose, we dene the notion of pushable
load. For a node ui F and a node v C, let pushable(ui , v) denote the amount
24 A. Aggarwal et al.
of load on ui that is accessible to v: pushable(ui , v) = aAi :av x(a, ui )r(a).
We next show how to identify a suitable set of consorts such that the pushable
load is more than the load that we wish to transfer.
Lemma 7. We can nd a set of nodes L = {v1 , v2 , . . . , vt+1 } such that for all
i t + 1, pushable(ui , v) load(Ai , C ).
We have shown that each node ui has a load of at least load(Ai , C ) which
can be pushed to its consort vi . As observed earlier load(Ai , C ) < W/4 and
load(Ai , vi ) W/4. Hence, when we fully open the consort, we get an additional
space of (3/4)W , which is sucient to receive the load from ui .
Given the above discussion, we iteratively consider each cluster Cj C and
perform the above transformation. This results in (t + 1) consorts from Cj being
fully-opened and all the other nodes in Cj being fully closed. At the end of
processing all the clusters, we get a solution in which each node either fully open
or fully close. For each cluster Cj , we incur an extra cost of at most (t + 1)
while applying Proposition 2, and an additional cost of (t + 1) for opening the
consorts. Thus, the cost increases by at most 2(t + 1)|C|.
References
1. S. Arora, V. Chakaravarthy, K. Gupta, N. Gupta, and Y. Sabharwal. Replica place-
ment on directed acyclic graphs. In V. Raman and S. Suresh, editors, Proceedings
of the 34th International Conference on Foundation of Software Technology and
Theoretical Computer Science (FSTTCS), pages 213225, 2014.
2. S. Arora, V. Chakaravarthy, N. Gupta, K. Mukherjee, and Y. Sabharwal. Replica
placement via capacitated vertex cover. In A. Seth and N. Vishnoi, editors, Proceed-
ings of the 33rd International Conference on Foundations of Software Technology
and Theoretical Computer Science (FSTTCS), pages 263274, 2013.
3. A. Benoit, H. Larcheveque, and P. Renaud-Goud. Optimal algorithms and approxi-
mation algorithms for replica placement with distance constraints in tree networks.
In Proceedings of the 26th IEEE International Parallel and Distributed Processing
Symposium (IPDPS), pages 10221033, 2012.
4. H. Bodlaender and A. Koster. Combinatorial optimization on graphs of bounded
treewidth. Computer Journal, 51(3):255269, 2008.
5. J. Chuzhoy and J. Naor. Covering problems with hard capacities. SIAM Journal
of Computing, 36(2):498515, 2006.
6. I. Cidon, S. Kutten, and R. Soer. Optimal allocation of electronic content. Com-
puter Networks, 40:205218, 2002.
7. U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM,
45(4):634652, 1998.
8. K. Kalpakis, K. Dasgupta, and O. Wolfson. Optimal placement of replicas in trees
with read, write, and storage costs. IEEE Transactions on Parallel and Distributed
Systems, 12:628637, 2001.
9. M. Kao, H. Chen, and D. Lee. Capacitated domination: Problem complexity and
approximation algorithms. Algorithmica, 72(1):143, 2015.
10. B. Saha and S. Khuller. Set cover revisited: Hypergraph cover with hard capacities.
In A. Czumaj, K. Mehlhorn, A. Pitts, and R. Wattenhofer, editors, Proceedings
of the 39th International Colloquium on Automata, Languages, and Programming
(ICALP), volume 7391 of LNCS, pages 762773. Springer, 2012.
Fast Exact Algorithms for Survivable Network
Design with Uniform Requirements
1 Introduction
The survivable network design problem involves designing a cost eective com-
munication network that can survive equipment failures. The failure may be
caused by any number of things such as a hardware or software breakage, human
error or a broken link between two network components. Designing a network
which satises certain connectivity constraints, or augmenting a given network
to a certain connectivity are important and well studied problems in network
design. In terms of graph theory these problems correspond to nding a spanning
subgraph of a graph which satises given connectivity constraints and, augment-
ing the given graph with additional edges so that it satises the given constraints,
respectively. Designing a minimum cost network which connects all the nodes,
is the well-known Minimum Spanning Tree(MST) problem. However such a
Supported by Parameterized Approximation ERC Starting Grant 306992 and
Rigorous Theory of Preprocessing ERC Advanced Investigator Grant 267959.
network fails on the failure of a single link. This leads to the question of design-
ing a minimum cost network which can survive one or more link failures. Such a
network must be -connected, in order to survive 1 link failures (we use the
term -connected to represent -edge connected). This problem is NP-hard (for
2), and a 2-approximation algorithm is known [19]. In the special case when
the weights are 1 or , i.e. we wish to nd a minimum spanning -connected
2
subgraph, a 1 + +1 approximation may be obtained in polynomial time [6]. The
above results also hold in the case of directed graphs. The case of = 1 for
digraphs, known as Minimum Strong Spanning Subgraph(MSSS), is NP-
hard as it is a generalization of the Hamiltonian Cycle. Further, the Minimum
Equivalent Graph(MEG) problem reduces to it in polynomial time.
Adding a minimum number of edges to make the graph satisfy certain con-
nectivity constrains is known as minimum augmentation problem. Minimum
augmentation nd application in designing survivable networks [12, 16] and in
data security [14, 17]. Watanabe and Nakamura [25] gave a polynomial time algo-
rithm for solving the -edge connectivity augmentation in an undirected graph,
where we want to add minimum number of edges to the graph to make it -edge
connected. Frank gave a polynomial time algorithm for the same problem in
directed graphs [11]. However in the weighted case, or when the augmenting set
must be a subset of a given set of links, the problem becomes NP-Hard problem.
Even the restricted case of augmenting the edge connectivity of a graph from
1 to remains NP-hard [1]. A 2-approximation may be obtained for these
problems, by choosing a suitable weight function and applying the algorithm of
[19]. We refer to [1, 4, 18, 20] for more details, other related problems and further
applications. A few results are also known in the frameworks of parameterized
complexity and exact exponential time algorithms. Marx and Vegh gave an FPT
algorithm for computing a minimum cost set of at most k links, which augments
the connectivity of an undirected graph from 1 to [22]. Basavaraju et al.
[2] improved the running time of this algorithm and, also gave an algorithm for
another variant of this problem. Bang-Jensen and Gutin [1, Chapter 12] obtain
an FPT algorithm for a variant of MSSS in unweighted graphs. The rst exact
algorithms for MEG and MSSS, running in time O(2O(m) nO(1) ), where m is
the number of edges in the graph, were given in by Moyles and Thompson [23] in
1969. Only recently, Fomin et al. [10] gave the rst single-exponential algorithm
for MEG and MSSS, i.e. with a running time of 2O(n) . For the special case of
Hamiltonian Cycle, a O(2n ) time algorithm is known [15, 3] for digraphs from
1960s. It was recently improved to O(1.657n ) for undirected graphs [5], and to
O(1.888n ) for bipartite digraphs [9] (but these are randomized algorithms). For
other results and more details we refer to Chapter 12 of [1].
In this paper we consider the problem of designing an exact algorithm for
nding a minimum weight spanning subgraph of a given -connected (di)graph.
Minimum Weight -connected Spanning Subgraph
Input: A graph G (or digraph D), and a weight function w on the edges(or
the arcs).
Output: A minimum weight spanning -connected subgraph.
Fast Exact Algorithms for Survivable Network Design with Uniform Requirements 27
One can observe that such a subgraph contains at most (n1) edges (2(n1)
arcs for digraphs). Hence a solution can be obtained by enumerating all possible
subgraphs with at most these many edges and testing if it is -connected. How-
ever such an algorithm will take 2O(n(log n+log )) time. One may try a more
clever approach, by using the observation that we can enumerate all possible
minimal -connected graphs in 2O(n) time. Then we test if any of these graph
is isomorphic to a subgraph of the input graph. However, subgraph isomorphism
requires 2n(log n+log ) unless the Exponential Time Hypothesis fails [7]. In this
paper, we give the rst single exponential algorithm for this problem that runs
in time 2O(n) . As a corollary, we also obtain single exponential time algorithm
for the minimum weight connectivity augmentation problem.
Minimum Weight -connectivity Augmentation
Input: A graph G (or a digraph D), a set of links L V V (ordered pairs
in case of digraphs), and a weight function w : L N.
Output: A minimum weight subset L of L such that G L (or D L) is
-connected
Our Methods and Results. We extend the algorithm of Fomin et al. for nding a
Minimum equivalent Graph [10], to solve Minimum weight - Connected
sub-digraph, exploiting the structural properties of -connected (di)graphs. A
digraph D is -connected if and only if for some r V (D), there is a collection
I of arc disjoint in-branchings rooted at r and a collection O of arc disjoint
out-branchings rooted at r. Then computing a I and a O with the largest pos-
sible intersection yields a minimum weight -connected spanning sub-digraph.
We show that the solution can be embedded in a linear matroid of rank O(n),
and then compute the solution by a dynamic programming algorithm with rep-
resentative sets over this matroid.
Theorem 1. Let D be a -edge connected digraph on n vertices and w : A(D)
N. Then we can nd a min-weight -edge connected subgraph of D in 2O(n) time.
For the case of undirected graphs, no equivalent characterization is known. How-
ever, we obtain a characterization by converting the graph to a digraph with
labels on the arcs, corresponding to the undirected edges. Then computing a
solution that minimizes the number of labels used, gives the following theorem.
Theorem 2. Let G be a -edge connected graph on n vertices and w : E(G)
N. Then we can nd a min-weight -edge connected subgraph of G in 2O(n)
time.
For the problem of augmenting a network to a given connectivity requirement,
at a minimum cost, we obtain the following results by applying the previous
theorems with suitably chosen weight functions.
Theorem 3. Let D be a digraph (or a graph) on n vertices, L V (D) V (D)
be a collection of links with weight function w : L N. For any integer , we can
nd a min-weight L L such that D = (V (D), A(D) L ) is -edge connected,
in time 2O(n) .
28 A. Agrawal et al.
2 Directed Graphs
In this section, we give a single exponential exact algorithm, that is of running
time 2O(n) , for computing a minimum weight spanning -connected subgraph of
a connected n-vertex digraph. We rst consider the unweighted version of the
problem and it will be clear that the same algorithm works for weighted version
as well. In a digraph D, we dene OutD (v) = {(v, w) A(D)} and InD (v) =
{(u, v) A(D)} to be the set of out-edges and in-edges of v, respectively. We
begin with the following characterization of -connectivity in digraphs.
A(I) denotes the set of arcs which are present in some I I and A(O) denotes
the set of arcs which are present in some O O.
V (Dr )} 4 . Since OutDr (r) = and |V (Dr )| = n, we have that the rank of
4
We slightly abuse notation for the sake of clarity, as strictly speaking X and
OutDG
r (v) are disjoint, since they are subsets of two dierent copies of the arc set.
30 A. Agrawal et al.
Since InDr+ (r) = and V (Dr+ ) = n, we have that the rank of these partition
matroids, MiO,2 , i [], is n 1. We dene two uniform matroids MI and
MO of rank (n 1), corresponding to I and O, on the ground sets EI and
EO , respectively, where Ei and EO are copies of the arc set of D. We dene
matroid M = (E, I) as the direct sum of MI , MO , MiI,j , MiO,j , for i [] and
j {1, 2}. That is, M = i[],j{1,2} (M i
I,j M i
O,j ) MI MO Since the
rank of MiI,j , MiO,j where i [] and j {1, 2}, are n 1 each, and rank of MI
and MO is (n 1), we have that the rank of M is 6(n 1). We briey discuss
the representation of these matroids. The matroids MiI,1 , MiO,1 for i [] are
graphic matroids, which are representable over any eld of size at least 2. The
matroids MiI,2 , MiO,1 are partition matroids with partition size 1, and therefore
they are representable over any eld of at least 2 as well. Finally, the two uniform
matroids, MI and MO , are representable over any eld with at least |A(D)| + 1
elements. Hence, at the start of our algorithm, we choose a representation of all
these matroids over a eld F of size at least |A(D)| + 1. So M is representable
over any eld of size at least |A(D)| + 1 (see [8, 10]).
For an arc e A(D) not incident to r there are 4 + 2 copies of it in M.
Let eiJ,j denotes its copy in EJ,j i
, where i [], j {1, 2} and J {I, O}.
An arc incident to r has only 3 + 2 copies in M. For an arc e InD (r) we
i i i
will denote its copies in EI,1 , EO,1 , EI,2 by eiI,1 , eiO,1 , eiI,2 , and similarly for an
arc e OutD (r) we will denote its copies in EI,1 i i
, EO,1 i
, EO,2 by eiI,1 , eiO,1 , eiO,2 .
And nally, for any arc e A(D), let eI and eO denote its copies in EI and
EO , respectively. For e A(D) \ OutD (r) and i [], let SI,e i
= {eiI,1 , eiI,2 }.
Similarly for e A(D) \ InD (r), i [], let SO,e = {eO,1 , eO,2 }. Let Se =
i i i
j
(i=1 SI,e
i
) (j=1 SO,e ) {eI , eO }. For X I, let AX denote the set of arcs
e A(D) such that Se X = .
Observe that any arc e A(D) can belong to at most one in-branching in I
and at most one out-branching in O, because both I and O are collection of arc
disjoint subgraphs of D. Because of Observation 1, if we consider that each Ii I
is embedded into MiI,1 and MiI,2 and each Oi O is embedded into MiO,1 and
MiO,2 , then we obtain an independent set Z of rank 4(n 1) corresponding
Fast Exact Algorithms for Survivable Network Design with Uniform Requirements 31
n = 6(n 1), such that D has arc disjoint in-branchings containing AT and
arc disjoint out-branchings containing AT , which are all rooted at r.
Since Z is a basis in M, for any i [], j {1, 2} and k {I, O}, we have
that Z Ek,j
i i = Z E i
is a basis in Mik,j (see [8, 10]). For each i [], let X 1 I,1
and X i = Z E i . By Claim 1, A i = A i and hence, by Observation 1,
2 I,2 X1 X2
I i = A i forms an in-branching rooted at r. Because of Claim 1, {I i | i } are
X1
pairwise arc disjoint as I i I j = for every i = j []. Further AT is covered
in arc disjoint in-branchings {AIi,1 | i }, as T EI,j
i
X i for j {1, 2}. By
j
similar arguments we can show that there exist a collection {O i | i []} of
out-branchings rooted at r containing AT . The reverse direction of the lemma
follows from Lemma 2.
Lemma 4. Let D be a connected digraph on n vertices and [(n 2)].
In time 2O(n) we can compute B 6 nrep6 B 6 such that |B 6 | n6 . Here
n = 6(n 1).
Proof. We give an algorithm via dynamic programming. Let D be an array of size
+ 1. For i {0, 1, . . . , } the entry D[i] will store the family B 6i nrep6i B 6i . We
will ll the entries in array D according to the increasing order of index i, i.e. from
0, 1, . . . , . For i = 0, we have B 0 = {}. Let W = {{eI , eO , eiI,1 , eiI,2 , ejO,1 , ejO,2 } |
i, j [], e A(D)} and note that |W| = 2 m, where m = |A(D)|. Given that
we have lled all the entries D[i ], where i < i + 1, we ll the entry D[i + 1] at
step i + 1 as follows. Let F 6(i+1) = (B 6i W) I.
n 6(i+1)
Claim. 2 () F 6(i+1) rep B 6(i+1) , for all i {0, 1, . . . 1}
Now the entry for D[i+1] is F 6(i+1) which is n 6(i+1) representative family
for F 6(i+1) , and it is computed as follows. By Theorem 4 we have that |B 6i |
n 6(i+1)
6i , Hence it follows that |F | 2 m n6i and moreover, we can compute
n 6(i+1)
F 6(i+1) in time O(2 mn n6i ). We use Theorem 4 to compute F 6(i+1) rep
n
n
F 6(i+1) of size at most 6(i+1) . This step can be done in time O( 6(i+1) tp +
n 1
t 6(i+1) ), where t = |F 6(i+1) | = 2 m 6i . We know from Claim 2 that
n
n 6(i+1)
F 6(i+1) rep B 6(i+1) . Therefore by the transitive property of representative
n 6(i+1) 6(i+1)
sets [8, 10], we have B 6(i+1) = F 6(i+1) rep B . Finally, we assign the
family B 6(i+1)
to D[i + 1]. This completes the description of the algorithm and
Fast Exact Algorithms for Survivable Network Design with Uniform Requirements 33
its correctness. Now, since n /6, we can bound the total running time of this
n
n 1 2
n
algorithm as O i=1 i 6(i+1) + 6(i+1) m 6i 2O(n) .
We have the following algorithm for computing I and O given A(I) A(O).
This algorithm extends a given set of arcs to an minimum weight collection of
arc disjoint out-branchings. This is a simple corollary of [24, Theorem 53.10]
and it also follows from the results of Gabow [13].
Proof. Let n = 6(n 1). We x an arbitrary r V (D) and for each choice
of , the cardinality of |A(I) A(O)|, we attempt to construct a solution. By
Lemma 3 we know that there exists a -connected spanning subdigraph D of
D with at most 2(n 1) arcs if and only if there exists T B 6 nrep6 B 6 ,
where n = 6(n 1), such that D has a collection I = {I1 , I2 , . . . , I } of arc
disjoint in-branchings rooted at r and a collection O = {O1 , O2 , . . . , O } of arc
disjoint out-branchings rooted at r such that AT A(I) A(O). Using Lemma 4
we compute B 6l nrep6 B 6 in time 2O(n) , and for every F B 6 we check if
An similar algorithm can be obtained for the weighted version of the problem
using the notion of weighted representative sets, thus proving Theorem 1.
3 Undirected Graphs
which is a partition matroid on the ground set Ai2 , which is a copy of the arc
set A(DG r
), such that the following holds. I2i = {I | I Ai2 , |I InDG r (v)|
if and only if exactly one of the following holds. Either W Se = ; or, there exists
t, t [], t = t , such that, (i) (ae )O , (ae )O W , (ii) Set W = {(ae )t1 , (ae )t2 },
(iii) Set W = {(ae )t1 , (ae )t2 }, and (iv) i [] \ {t, t }, Sei W = . Now
for each [(n 2)/2], we dene the following set. B 6 = {W | W
I, |W | = 6 and e E(G), (W, e) = 1} Observe that for every W B 6 ,
|Typ(AW )| = and, ae AW if and only if ae AW . Therefore, any set in
this collection corresponds to a potential candidate for the subset of arcs which
appear in exactly two out-branchings in O. The following lemma, relates the
computation of out-branchings minimizing types and representative sets.
out-branchings rooted at r, AT A(O) and |Typ(O)| (n 1) . Further,
we can compute B 6 n 6 B 6 such that |B 6 | n in time 2O(n) .
rep 6
4 Augmentation Problems
The algorithms for Minimum Weight -connected Spanning Subgraph
may be used to solve instances of Minimum Weight -connectivity Aug-
mentation as well. Given an instance (D, L, w, ) of the augmentation problem,
we construct an instance (D , w , ) of Minimum Weight -connected Span-
ning Subgraph, where D = D L and w is a weight function that gives a
weight 0 to arcs in A(D) and it is w for the arcs from L. It is easy to see that
the solution returned by our algorithm contains a minimum weight augmenting
set. A similar approach works for undirected graphs as well, proving Theorem 3.
References
1. Bang-Jensen, J., Gutin, G.Z.: Digraphs: theory, algorithms and applications.
Springer Science & Business Media (2008)
2. Basavaraju, M., Fomin, F.V., Golovach, P., Misra, P., Ramanujan, M., Saurabh,
S.: Parameterized algorithms to preserve connectivity. In: Automata, Languages,
and Programming, pp. 800811. Springer (2014)
3. Bellman, R.: Dynamic programming treatment of the travelling salesman problem.
Journal of the ACM (JACM) 9(1), 6163 (1962)
4. Berman, P., Dasgupta, B., Karpinski, M.: Approximating transitive reductions
for directed networks. In: Proceedings of the 11th International Symposium on
Algorithms and Data Structures. pp. 7485. Springer-Verlag (2009)
36 A. Agrawal et al.
1 Introduction
Problem Denition and Motivation. We consider the Tree Partition-
ing problem dened as follows:
Tree Partitioning
Given: A tree T ; k, b, s1 , . . . , sb N
Parameter: k
Question: Does there exist a subset E E(T ) of at most k edges such that
the components of T E can be grouped into b groups, where group i contains
si vertices, for i = 1, . . . , b?
The special case of the problem when s1 = = sb = |V (T )|/b is referred to
as Balanced Tree Partitioning.
The two problems are special cases of the Balanced Graph Partitioning
problem, which has applications in the areas of parallel computing [3], computer
vision [3], VLSI circuit design [4], route planning [8], and image processing [22].
The special case of Balanced Graph Partitioning, corresponding to b =
2, is the well-known N P-complete problem Bisection [16]. The Balanced
Graph Partitioning problem has received a lot of attention from the area of
approximation theory (for instance, see [2, 12, 21]). Moreover, the complexity
and the approximability of the problem restricted to special graph classes, such
as grids, trees, and bounded degree trees [1214, 20], have been studied.
(A) We prove that Balanced Tree Partitioning, and hence Tree Parti-
tioning, is N P-complete for trees with maximum degree at most 3. This
answers an open question in [13] about the complexity of Balanced Tree
Partitioning for trees of maximum degree 4 and 3, after they had shown
the N P-completeness of the problem for trees of maximum degree at most
5. This also closes the door on the complexity of these problems on trees, as
the simple case when the tree is a path is in P.
(B) We prove that both Tree Partitioning and Balanced Tree Parti-
tioning are W [1]-hard. This answers an open question in [23]. We also prove
the membership of the problems in the class W [1], using the characterization
of W [1] given by Chen et al. [7].
(C) We present an exact subexponential-time algorithm for Tree Partition-
ing, and hence for Balanced Tree Partitioning, that runs in time
2O( n) , where n is the number of vertices in the tree.
For the lack of space, many details and proofs in this paper have been omitted,
and can found in [1].
Related Work and Our Contributions. Feldmann and Foschini [13] stud-
ied Balanced Tree Partitioning. They showed that the problem is N P-
complete for trees of maximum degree at most 5, and left the question about
the complexity of the problem for maximum degree 4 and 3 open. Whereas the
reduction used in the current paper to prove the N P-hardness of Balanced
Tree Partitioning on trees of maximum degree at most 3 starts from the
same problem (3-Partition) as in [13], and is inspired by their construction,
the reduction in this paper is much more involved in terms of the gadgets em-
ployed and the correctness proofs.
Bevern et al. [23] showed that the parameterized complexity of Balanced
Graph Partitioning is W [1]-hard when parameterized by the combined pa-
rameters (k, ), where k is (an upper bound on) the cut size, and is (an upper
bound on) the number of resulting components after the cut. It was observed
in [23], however, that the employed FPT -reduction yields graphs of unbounded
The Complexity of Tree Partitioning 39
treewidth, which motivated the authors to ask about the parameterized com-
plexity of the problem for graphs of bounded treewidth, and in particular for
trees. We answer their question by showing that the problem is W [1]-complete.
Bevern et al. [23] also showed that Balanced Graph Partitioning is
W [1]-hard on forests by a reduction from the Unary Bin Packing problem,
which was shown to be W [1]-hard in [18]. We note that the disconnectedness of
the forest is crucial to their reduction, as they represent each number x in an
instance of Bin Packing as a separate path of x vertices. For Balanced Tree
Partitioning, in contrast to Unary Bin Packing (and hence, to Balanced
Graph Partitioning on forests), the diculty is not in grouping the compo-
nents into groups (bins) because enumerating all possible distributions of k + 1
components (resulting from cutting k edges) into b k + 1 groups can be done
in FPT -time; the diculty, however, stems from not knowing which tree edges
to cut. The FPT -reduction we use to show the W [1]-hardness is substantially
dierent from both of those in [18, 23], even though we use the idea of non-
averaging sets in our constructiona well-studied notion in the literature (e.g.,
see [5]), which was used for the W [1]-hardness result of Unary Bin Packing
in [18].
Many results in the literature have shown that certain N P-hard graph prob-
lems are solvable in subexponential time. Some of these rely on topological
properties of the underlying graph that guarantee the existence of a balanced
graph-separator of sub-linear size, which can then be exploited in a divide-and-
conquer approach (e.g., see [6, 9]). There are certain problems on restricted
graph classes that resist such approaches due to the the problem specications;
designing subexponential-time algorithms for such problems usually requires ex-
ploiting certain properties of the solution itself, in addition to properties of the
graph class (see [15, 19] for such recent results). In the case of Tree Parti-
tioning and Balanced Tree Partitioning, since every tree has a balanced
separator consisting of a single vertex, yet the two problems remain N P-hard
on trees, clearly a divide-and-conquer approach based solely on balanced sep-
arators does not yield subexponential-time algorithms for these problems. To
design subexponential-time algorithms for them, we rely on the observation that
the number of possible partitions of an integer n N is subexponential in n; this
allows for
a compact representation of all solutions using a solution space of
size 2O( n) , enabling a dynamic programming approach that solves the problems
within the same time upper bound.
Terminologies. We refer the reader to [10, 11] for more information about
graph theory and parameterized complexity.
Let T be a rooted tree. For an edge e = uv in T such that u is the parent of
v, by the subtree of T below e we mean the subtree Tv of T rooted at v. For two
edges e, e in T , e is said to be below e if e in an edge of the subtree of T below
e . A nice binary tree T is dened recursively as follows. If |V (T )| 1 then T
is a nice binary tree. If V (T ) > 1, then T is nice if (1) each of the left-subtree
and right-subtree of T is nice and (2) the sizes of the left-subtree and the right-
subtree dier by at most 1. For any n N, there is a nice binary tree of order
40 Z. An et al.
2 N P-completeness
and whose right subtree Ri is a nice binary tree of size s 2. We denote by Ril
and Rir the left and right subtrees of Ri , respectively. Let H = (p1 , . . . , p3k ) be a
path on 3k vertices. The tree T is constructed by adding an edge between each
pi in H and the root of Ti , for i [3k]. See Figure 1 for illustration. It is clear
from the construction that T is a degree-3 tree of 4k s vertices, since each Ti has
size ai + s 1 and P has 3k vertices. We will show that (S, s) is a yes-instance of
3-Partition if and only if the instance I = (T, 6k 1, b = 4k) is a yes-instance
of Balanced Degree-3 Tree Partitioning.
3k
p1 H pi p3k
Li Ri
a1 ai Ril Rir a3k
s s s s
2
-1 2
-2 s s 2
-1 2
-2
2
-1 2
-2
T1 Ti T3k
Fig. 1. Illustration of the construction of the tree T .
Note that the size of T is 4k s, and hence, if the vertices in T can be grouped
into 4k groups of equal size, then each group must contain s vertices. From the
aforementioned statement, it follows that at least one cut is required in each tree
Ti because the size of each Ti is ai + s 1 > s.
Suppose that the instance I has a solution P that cuts 6k 1 edges in T .
Proof. Since |Ti | > s, any Ti must contain at least one P -component. Since
CP has 6k P -components, at least one of the 3k Ti s contains at most one P -
component, because otherwise the P -components containing vertices in H are
not accounted for. Therefore, at least one Ti contains exactly one P -component
C, which must be a lowest P -component in Ti . By Lemma 1, C = Ri and
|C| s/4, and hence C cannot be any proper subtree of Li , Ril , or Ril . This
leaves Li , Ril , and Ril as the only possible choices for C.
Suppose that C = Ril . After removing C, the partial-Ti , denoted Ti , has
size s 1 + ai (s/2 1) = s/2 + ai , and contains no P -components. Let D
be the set of vertices that are not in Ti , and are in the same group as Ti .
Observe that for any j = i, j [3k], if a vertex in Lj is in D then all vertices
42 Z. An et al.
3 W [1]-completeness
To show that Tree Partitioning is W [1]-hard (membership in W [1] is shown
using a characterization of W [1] given in [7]), we give a xed-parameter tractable
reduction (FPT -reduction) from the k-Multi-Colored Clique problem (k-
MCC), which is W [1]-complete ([11]), and is dened as follows: Given a graph
M = (V (M ), E(M )) and a proper k-coloring of the vertices f : V (M ) C,
where C = {1, 2, ..., k} and each color class has the same cardinality, decide
whether there exists a clique Q V (M ) of size k such that, u, v Q, f (u) =
f (v). For i [k], we dene Ci = {v M | f (v) = i} to be the color class
consisting of all vertices whose color is i. Let n = |Ci |, i [k], and let N = k n.
We label the vertices in Ci arbitrarily as v1i , . . . , vni . We rst introduce some
terminologies.
For a nite set X N and Z+ , we say that X is -non-averaging if for
any numbers x1 , . . . , x X, and for any number x X, the following holds:
if x1 + + x = x then x1 = = x = x.
Let X = {x1 , . . . , xn } be a (k 1)-non-averaging set. It is known that we can
construct such a set X such that each element xi X, i [n], is polynomial in n
(for instance, see [5]). Jensen et al. [18] showed that a (k1)-non-averaging set of
cardinality n, in which each number is at most k 2 n2 n4 , can be constructed in
polynomial time in n; we will assume that X is such a set. Let k = k + k2 , and
let z = k 2 n5 . Choose 2k numbers b1 , . . . , bk , c1 , . . . , ck N such that bj = k 2j z
for j [k], and cj = k 2(k+j) z for j [k]. Observe that each number in the
The Complexity of Tree Partitioning 43
for illustration. For each edge e in M between two vertices vij and vpq , i, p
[n], j, q [k], j < q, we create two stars Sv j and Sv pq , with bj +xi 1 and bq +xp 1
i
leaves, respectively, and of roots rv j and rv pq , respectively. We introduce a star Se
i
with root re and cqj 1 leaves, and connect re to rv j and rv pq to form a tree Te with
i
root re that we call an edge-gadget (for edge e). We connect re to r. See Figure 3
for illustration. Note that the number of vertices in Te that are not in Sv j Sv pq is
i
exactly cqj . Finally, we create k +1 copies of a star Sf ix consisting of ckk1 +k +1
many vertices, and connect the root r of T to the root of each of these copies.
This completes the construction of T . Let t = |T |. We dene the reduction from
k-Multi-Colored Clique to Tree Partitioning to be the map that takes
an instance I = (M, f) of k-Multi-Colored Clique and produces the instance
I = (T, k , b = k + k2 , c1 , . . . , ck , c21 , . . . , ck1 , c32 , . . . , ck2 . . . , ckk1 , t ), where k =
k
k + 3 k2 and t = t j=1 cj j,q[k],j<q cqj . Clearly, this reduction is an
FPT -reduction. Next, we describe the intuition behind this reduction.
r
Se
re
Svj
i
Sv j
i
Sv q
p
rv j rv q
i p cqj 1
cj (k 1)bj (k 1)xi 1 bj + xi 1 bq + xp 1
Each number cj , j [k], chosen above, will serve as a signature for class
Cj , in the sense that it will ensure that in any solution to the instance, a vertex-
gadget corresponding to a vertex in class Cj is cut and placed in the group
of size cj . Each number cjj , j, j [k], j < j , will serve as a signature for
the class-pair (Cj , Cj ), in the sense it will ensure that in a solution exactly one
edge-gadget corresponding to an edge e between classes Cj and Cj is cut and
the star Se is placed in the group whose size is cjj . Each number bj , j [k], will
serve as a signature for any edge such that one of its endpoints is in Cj (i.e.,
a signature for an arbitrary vertex in Cj ), ensuring that in a solution, k 1 of
these edges are cut. Finally, the choice of the xi s, for i [n], to be elements of
a (k 1)-non-averaging set, will ensure that all the edges cut that are incident
to vertices in the same class Cj , j [k], are incident to the same vertex in Cj .
Next, we prove the correctness of the reduction. One direction is easy:
Lemma 3. If (M, f ) is a yes-instance of k-Multi-Colored Clique then I
is a yes-instance of Tree Partitioning.
To prove the converse,
let P = (EP , P ) be a solution to the instance
I = (T, k , b = k + k2 , c1 , . . . , ck , c21 , . . . , ck1 , c32 , . . . , ck2 . . . , ckk1 , t ) of Tree Par-
titioning. Let Gj , j [k], denote the group of size cj , Gqj , j, q [k], j < q,
denote the group of size cqj , and Grest denote the group of size t . We have:
Lemma 4. There is a solution P that cuts exactly k = k + 3 k2 edges from T
as follows. For each j [k], P cuts exactly one edge between the root r of T and
the root of a vertex-gadget corresponding to a vertex in color class Cj ; moreover,
P assigns the resulting vertex-gadget to group Gj . For each j, q [k], j < q, P
cuts exactly 3 edges from one edge-gadget Te , corresponding to an edge e between
a vertex vij , i [n], in color classes Cj , and a vertex vpq , p [n], in color class
Cq ; those 3 edges are the edges rre , re rv j , and re rv pq , where re is the root of star
i
Se in Te , and rv j , rv pq are the roots of stars Sv j , Sv pq in Te , respectively; moreover,
i i
P assigns Se to group Gqj .
Lemma 5. If I is a yes-instance of Tree Partitioning then (M, f ) is a yes-
instance of k-MCC.
kBy Lemma 4, we can assume that I has a solution P = (EP , P ) that cuts
Proof.
k+3 2 edges, and that satises the properties in the lemma. Let rrvi1 , . . . , rrvik ,
1 k
i1 , . . . , ik [n], be the edges between the root r of T and the roots of the
vertex-gadgets Svi1 , . . . , Svik that P cuts. We claim that the set of vertices Q =
1 1
{vi11 , . . . , vikk } induce a multi-colored clique in M . To show that, it suces to show
that each of the k2 edges rre cut by P , between r and the root of an edge-gadget
Te , where e = vij vpq , i, p [n], p, q [k], p < q, satises that vij , vpq Q.
Consider an arbitrary group Gj , j [k]. The size of Gj is cj , and by Lemma 4,
P assigns the star Svj of size cj (k 1)bj (k 1)xij to Gj . Each star Se is
ij
assigned to some group Gqp whose size is exactly |Se |. Therefore, each group Gj
The Complexity of Tree Partitioning 45
correspond to the same vertex vijj . Observe that this will prove that Q is a clique,
since it will imply that each vertex in Q is incident to exactly k 1 of the k2
many edges between the color classes.
Let Sv j , . . . , Sv j be the k 1 stars placed in Gj . The sizes of these stars
i i
1 k1
are bj + xi1 , . . . , bj + xik1 , respectively. The size cj of Gj is equal to the sum of
the sizes of these k 1 stars, plus that of Svj . Therefore: cj = cj (k 1)b
ij
4 Subexponential-time Algorithms
+
n Z . A partition of n is a collection X of positive integers such that
Let
xX x = n. Let p(n) denote the total number of (distinct) partitions of n.
It is well known that p(n) = 2O( n) [17]. It follows that the total number
of
partitions of all integers n , where 0 < n n, is 0<n n p(n ) = 2O( n) .
Let L be a list of numbers in N that are not necessarily distinct. We denote
by L(i) the ith number in L, and by Li the sublist of L consisting of the rst i
numbers. The length of L, denoted |L|, is the number of elements in L.
Let (T, k, b, s1 , . . . , sb ) be an instance of Tree Partitioning. Let n = |T |.
Consider a partial assignment of n n vertices of T to the b groups, with the
possibility of some groups being empty. Since the groups are indistinguishable,
such an assignment corresponds to a partition of the n vertices into at most b
46 Z. An et al.
Bibliography
[1] Z. An, Q. Feng, I. Kanj, and G. Xia. The Complexity of Tree Partitioning.
Available at http://arxiv.org/abs/1704.05896.
[2] K. Andreev and H. Rcke. Balanced graph partitioning. Theory of Com-
puting Systems, 39(6):929939, 2006.
48 Z. An et al.
1 Introduction
Local search is a popular technique for designing time and cost ecient approx-
imation algorithms. It has a long history in combinatorial optimization and has
proved to be very eective for achieving near-optimum solutions. The use of this
technique in geometric approximation is relatively new, but has resulted in im-
proved approximation for metric and geometric versions of many combinatorial
problems. In fact, this technique has been used in this domain to achieve several
breakthrough results.
In this article, we restrict ourselves to the works based on local search in
geometric approximation. One of the rst results of local search for the problems
in metric space is a 3+
approximation algorithm for k-median due to Arya et al.
[1]. An arguably simplied analysis was later given by Gupta and Tangwongsan
[15]. Building on the work of Arya et al., Kanungo et al. [16] have designed a
9 +
approximation algorithm for k-means. In a celebrated work Mustafa and
The author has been supported by NSF under Grant CCF-1615845.
Ray [20] designed the rst PTASes for the Hitting Set problem for a wide class
of geometric range spaces. Around the same time Chan and Har-Peled [7] gave
PTASes for Maximum Independent Set problem of geometric objects including
fat objects and pseudodisks in the plane. Cohen-Addad and Mathieu [8] have
shown the eectiveness of local search for achieving PTASes for facility location
type problems. In a recent breakthrough, Cohen-Addad et al. [9] and Friggstad et
al. [13] have independently designed the rst PTAS for k-means which was a long
standing open problem. Very recently, Govindarajan et al. [14] have obtained the
rst PTASes for the Set Cover and Dominating Set problems for non-piercing
regions. See also [2, 3, 4, 5] for related work on local search.
In this paper, we consider art gallery problems and design PTASes using local
search proving the eectiveness of this technique for a new family of problems.
2 Preliminaries
Consider the orthogonal polygon P in the MSC or MHSC problem. An orthog-
onal segment s P is called canonical if (i) s is an extension of a side of P ,
52 S. Bandyapadhyay and A. Basu Roy
and (ii) s is maximal in terms of length, i.e., there is no other segment in P that
strictly contains it. We note that the endpoints of a canonical segment lie on the
boundary of P . Also the number of canonical segments is at most the number
of sides of P . It is not hard to see that there exists a canonical segment s for
any segment s P , such that s can guard all the points in P guarded by s.
Henceforth, for any solution S of MHSC or MSC, without loss of generality we
assume that S consists of only canonical segments. Obviously, for MHSC, any
solution consists of only horizontal canonical segments.
Now we describe a local search framework similar to the ones in [7, 20] for
designing and analyzing local search algorithms. In the following sections we will
apply this framework to get near optimum approximations for MHSC and MSC.
We note that this framework is applicable for discrete optimization problems,
where given a set S, the goal is to nd an optimum subset S S that is feasible.
Notably, not every subset S S is a feasible solution. Moreover, there is an
initial feasible solution that can be found in polynomial time, and given any
S S, one can decide the feasibility of S in polynomial time. We note that
for MHSC (resp. MSC), S is the nite set of all horizontal (resp. horizontal and
vertical) canonical segments, which is a feasible solution. Let n = |S|. Fix
> 0.
As we deal with only minimization problems in this article, the local search
algorithm we consider is the following.
Theorem 4. There exists a local search PTAS for the MHSC problem, where
the input polygon may or may not contain holes.
We use the local search framework to get a PTAS for MSC problem assuming P
does not contain any holes. In fact, one can construct a family of polygons with
holes for which our local search scheme performs very poorly (see full paper).
We start the local search algorithm with the set of canonical segments. Now
consider the local search solution L and an optimum solution R. Then we have
the following lemma which will be useful later.
(a) (b)
Y
(c) (d)
Fig. 1: (a) A connected component of the arrangement. (b) The boundary of the
closure of the component. (c) A horizontal segment X and a vertical segment
Y (bolded). The two slabs generated by taking the Minkowski sum of the two
segments with S , a square of side length . (d) The fattened boundary of the
closure.
First, we x some notations. For every X X , denote its left (resp. right)
endpoint by (X) (resp. r(X)), and the set of vertical segments in Y intersecting
it by vert(X). Also, denote any non-empty intersection point X Y by p(X, Y ),
where X X and Y Y.
One can visualize H as a self-intersecting curve. For simplicity we will dis-
entangle it to get a simple closed curve. To this end, we consider the object
H = H S , which is the Minkowski-sum of H and a square S with side length
, where is an arbitrarily small positive quantity (see Figure 1c and 1d). This is
basically fattening the boundary H such that the boundary of H is a simple
closed curve. Also note that it fattens only towards the positive horizontal and
vertical axes. Let H be the boundary of H . Now for every p(X, Y ) H,
there exists at least one point on H among the following points p(X, Y ),
p(X, Y ) + (0, ), p(X, Y ) + (, 0), and p(X, Y ) + (, ). Refer to that point as
p (X, Y ). If multiple of these points exist on H , then choose one arbitrarily.
For convenience we use p (X, Y ) as a proxy for p(X, Y ) while adding edges
to H whose one endpoint is p(X, Y ). At the end we will use the original points
p(X, Y ). As the two points are arbitrarily close the latter conversion does not af-
fect the planarity. Hereafter, for any reference to a point p (X, Y ), we will assume
that p(X, Y ) H. Now note that the only edges that are needed to be drawn
are the edges in EX and EX ,Y . The endpoints of the edges in EX will be the left
endpoints of the segments in X . Also the endpoints of the edges in EX ,Y will be
the left endpoints of the segments in X and the intersection
points
p(X, Y ) for
X X and Y Y such that p(X, Y ) H. Let Q = X (X) X,Y p (X, Y ),
the set of endpoints of the edges we will draw. Note that all the points of Q are
on H .
We consider GX as a tree rooted at some segment Xr X . Later we will
use this tree structure to add edges to H in an inductive manner. We denote
the parent of a segment Xi with respect to GX by parent(Xi ). Let r(Xr ) =
(x , y ). We cut open the closed curve H at (x , y + ) such that the open
curve is homeomorphic to an interval M , where r(Xr ) gets mapped before (Xr ).
For simplicity, we denote the mapped points by their original notations. Thus
r(Xr ) < (Xr ) in M . Note that one can consider another homeomorphism to an
interval (the reection of M with respect to its middle point) so that (Xr ) <
r(Xr ). One can visualize M in a way such that H is disconnected at the point
(x , y + ) and straightened out to get M . The way we have dened M it has the
following property: for any child Xi of Xr , if Xi lies above Xr , r(Xr ) < (Xr ) <
(Xi ) < r(Xi ) and if Xi lies below Xr , r(Xr ) < r(Xi ) < (Xi ) < (Xr ). Observe,
that the endpoints of M are not in Q and we already have an embedding of the
points of Q on the interval M . We use this embedding of the points to draw the
edges between them so that the edges do not cross each other.
For any edge (a, b) EX EX ,Y , (a, b) is called an edge corresponding to a
segment X of GX if either a or b is X, and the other endpoint is not parent(X).
For any subtree, we call all the edges corresponding to its nodes as its corre-
sponding edges. Now we proceed towards the inductive process of addition of
edges. For that we need to dene a concept called zone for every segment Xi of
58 S. Bandyapadhyay and A. Basu Roy
4
s4 t4
6
1
2 t2 s2
3 t3 s3
Fig. 2: The bolded curves corresponding to the children (2, 3, 4) of 1 are mapped to
the corresponding zones in M . si and ti are the respective left and right endpoint
of the zone of i for i = 2, 3, 4.
Lemma 9. Given the plane graph H as dened before, the edges of EX and
EX ,Y can be drawn in a non-crossing manner.
Proof. We note that the edges of EX EX ,Y are drawn outside of the closed
curve H . Thus they do not cross the edges of H as the latter edges lie inside
H . Consider the set Q of the endpoints of the edges to be drawn. We use the
Effectiveness of Local Search for Art Gallery Problems 59
Theorem 10. There exists a local search PTAS for the MSC problem, where
the input polygon does not contain holes.
Acknowledgments
We would like to thank the anonymous referees, Abhiruk Lahiri, and Kasturi
Varadarajan for their valuable comments, which have helped us improve the
presentation of the paper.
References
[1] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit.
Local search heuristics for k-median and facility location problems. SIAM
J. Comput., 33(3):544562, 2004.
60 S. Bandyapadhyay and A. Basu Roy
Aritra Banik1 , Fahad Panolan2 , Venkatesh Raman3 , Vibha Sahlot1 , and Saket
Saurabh3
1
Indian Institute of Technology, Jodhpur, India.
{aritrabanik|sahlotvibha}@gmail.com
2
Department of Informatics, University of Bergen, Norway.
[email protected]
3
The Institute of Mathematical Sciences, HBNI, Chennai, India.
{vraman|saket}@imsc.res.in
is for all the families of conict graphs for which the Independent Set
problem is W[1]-hard.
was studied in [1] and shown to be NP-complete. In fact, even if we do not care
about the size of the conict free set cover we seek, just the decision version of a
conict free set cover set is the same as Rainbow Covering, which is known to
be NP-complete. Thus, seeking a conict free set cover can transform a problem
from being tractable to intractable.
In order to restrict the family of graphs to which a conict graph belongs, we
need to dene the notion of arboricity. The arboricity of an undirected graph is the
minimum number of forests into which its edges can be partitioned. A graph G is
said to have arboricity d if the edges of G can be partitioned into at most d forests.
Let Gd denote the family of graphs of arboricity d. This family includes the family
of intersection graphs of low density objects in low dimensional Euclidean space
as explained in [8,9]. Specically, this includes planar graphs, graphs excluding a
xed graph as a minor, graphs of bounded expansion, and graphs of bounded
degeneracy. Har-Peled and Quanrud [8,9] showed that low-density geometric
objects form a subclass of the class of graphs that have polynomial expansion,
which in turn, is contained in the class of graphs of bounded arboricity. Thus,
our restriction of the family of conict graphs to a family of graphs of bounded
arboricity covers a large class of low-density geometric objects.
Theorem 1. Let (A, B)-Set Cover be tractable and let Gd be the family of
graphs of arboricity d. Then, the corresponding (A, B)-Graphical CF-SC is
also tractable if CGF belongs to Gd . In particular we obtain following results
when CGF belongs to Gd :
If (A, B)-Set Cover admits an FPT algorithm with running time (k)nO(1) ,
then (A, B)-Graphical CF-SC admits an FPT algorithm with running time
2O(dk) (k) nO(1) .
If (A, B)-Set Cover admits a factor -approximation running in time
nO(1) then (A, B)-Graphical CF-SC admits a factor -FPT-approximation
algorithm running in time 2O(dk) nO(1) .
all the points in P . The Matroidal Conflict Free Set Cover problem
(Matroidal CF-SC, in short) is dened similarly to Graphical CF-SC. In
particular, the input consists of a linear matroid M = (F, J ) over the ground
set F such that the set cover F J .
Theorem 3. (P, I )-Matroidal CF-SC is FPT for all representable matroids
M = (I, J ) dened over I. In fact, given a linear representation, the algorithm
runs in time 2k (n + m)O(1) . Here, is the exponent in the running time of
matrix multiplication.
A graph is called a cluster graph, if all its connected components are cliques.
Since cluster graphs can be captured by partition matroids, Theorem 3 implies
that (P, I )-Matroidal CF-SC is FPT if CGF is a cluster graph.
Notations. For t N, we use [t] as a shorthand for {1, 2, . . . , t}. A family of sets
A is called a p-family, if the cardinality of all the sets in A is p. Given two families
of sets A and B, we dene A B = {X Y | X A and Y B and X Y = }.
Given a graph G, V (G) and E(G) denote its vertex-set and edge-set, respectively.
We borrow notations from the book of Diestel [5] for graph-related notations.
2 FPT Algorithms
In this section we prove Theorems 1 and Theorem 3. The Proof of Theorem 1 is
based on a randomization scheme while the proof of Theorem 3 uses the idea of
ecient computation of representative families [6].
denote the family of subsets of intervals of size at most k that covers rst i points
and are independent in the matroid M = (I, J ). Furthermore, for every j [k],
by P ij , we denote the subset of P i containing sets of size exactly j. Thus,
70 A. Banik et al.
k
Pi = P ij .
j=1
In this subsection whenever we talk about independent sets, these are independent
sets of the matroid M = (I, J ). Furthermore, we assume that we are given, AM ,
the linear representation of M . Without loss of generality we can assume that
AM is a n |I| matrix, where n |I|.
Observe that (P, I, k, M = (I, J )) is a Yes instance of (P, I )-Matroidal
CF-SC if and only if P n is non-empty. This implies that P n is non-empty if and
only if P n 0 P n is non-empty. We capture this into the following lemma.
rep
For an ease of presentation by P 0 , we denote the set {}. The next lemma
provides an ecient computation of the family P i 1k P i . In particular, for
rep
every 1 i n, we compute
k
i =
P ij kj P ij .
P rep
j=1
Notice that in the Equation 1, the union is taken over I Zi+1 . Since for any
I Zi+1 , I covers pi+1 , the value I 1 is strictly less than i + 1 and hence
Equation 1 is well dened. Let N (i+1)j denote the subset of N i+1 containing
subsets of size exactly j.
Claim. N i+1 1k
rep P
i+1
.
Parameterized Complexity of Geometric Covering Problems Having Conflicts 71
k O(1)
(n + |I|) number of operation over the eld in which AM is given and
j
k
|N (i+1)j
| |I| k . Hence the total running time to compute D[i + 1] for any
j
i + 1 [n] is
k
k
(n + |I|)O(1) ) = 2k (n + |I|)O(1) .
j=1
j
k
k
(i+1)j | k
|D[i + 1]| = |N |I| k = 2k |I| k.
j=1 j=1
j
References
1. Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B.,
Simakov, M.: Choice is hard. In: ISAAC. pp. 318328 (2015)
2. Arkin, E.M., Banik, A., Carmi, P., Citovsky, G., Katz, M.J., Mitchell, J.S.B.,
Simakov, M.: Conict-free covering. In: CCCG (2015)
3. Banik, A., Panolan, F., Raman, V., Sahlot, V.: Frechet distance between a line and
avatar point set. FSTTCS pp. 32:132:14 (2016)
4. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M.,
Pilipczuk, M., Saurabh, S.: Parameterized algorithms. Springer (2015)
5. Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173.
Springer (2012)
6. Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Ecient computation of
representative families with applications in parameterized and exact algorithms. J.
ACM 63(4), 29 (2016)
7. Gabow, H.N., Westermann, H.H.: Forests, frames, and games: Algorithms for
matroid sums and applications. Algorithmica 7(5&6), 465497 (1992)
8. Har-Peled, S., Quanrud, K.: Approximation algorithms for low-density graphs.
CoRR abs/1501.00721 (2015)
9. Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion
and low-density graphs. In: ESA. vol. 9294, pp. 717728. Springer (2015)
10. Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J.,
Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for
geometric graphs. J. Algorithms 26(2), 238274 (1998)
11. Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a
symposium on the Complexity of Computer Computations. pp. 85103 (1972)
12. Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of
linear matroids. In: ICALP, Proceedings, Part I. vol. 9134, pp. 922934. Springer
(2015)
13. Lokshtanov, D., Panolan, F., Saurabh, S., Sharma, R., Zehavi, M.: Covering small
independent sets and separators with applications to parameterized algorithms.
ArXiv e-prints (May 2017)
14. Marx, D.: Parameterized complexity of independence and domination on geometric
graphs. In: IPEC, pp. 154165. Springer (2006)
15. Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput.
Sci. 410(44), 44714479 (2009)
16. Naor, M., Schulman, J.L., Srinivasan, A.: Splitters and near-optimal derandomiza-
tion. In: FOCS. pp. 182191 (1995)
Obedient Plane Drawings for Disk Intersection Graphs
1 Introduction
Disk intersection graphs have been long studied in mathematics and computer science
due to their wide range of applications in a variety of domains. They can be used
to model molecular bonds as well as the structure of the cosmic web, interference in
communication networks and social interactions in crowds. Finding planar realizations of
supported by DFG project MU/3501-2
supported by the Netherlands Organisation for Scientic Research (NWO) under project no.
639.021.123 and 614.001.504
supported by the ERC grant PARAMTIGHT: Parameterized complexity and the search for
tight complexity results, no. 280152
D G
(a)
Fig. 1: A set D of disks, the induced graph G, and an obedient plane straight-line drawing of G.
approach. On the positive side, we show that the problem can be solved efciently if the
degree of vertices belonging to ply-3 triangles (that is, the three corresponding disks have
a common intersection) is bounded by three (Section 3). In this result no assumption
concerning the uniformity of the disks radii is needed. Due to space restrictions, some
of the proofs are sketched or omitted in this short paper.
Notation. Throughout this paper disks are closed disks in the plane. Let D be a
set of disks, let G = (V, E) be the intersection graph of D and let be a straight-line
drawing of G. We use capital letters to denote disks and non-capital letters to denote
the corresponding vertices, e.g., the vertex corresponding to disk D D is d V .
We use the shorthand uv to denote the edge {u, v} E. Further, uvw refers to the
triangle composed of the edges uv, vw and wu. We identify vertices and edges with their
geometric representations, e.g., uv also refers to the line segment between the points
representing u and v in . We use int(D) to refer to the interior of a disk D D. The
ply of a point p R2 with respect to D is the cardinality |{D D | p D}|. The ply
of D is the maximum ply of any point p R2 with respect to D.
Planar Montone 3-Satisability. Let = (U , C) be a 3-S ATISFIABILITY (3SAT)
formula where U denotes the set of variables and C denotes the set of clauses. We call
the formula monotone if each clause c C is either positive or negative, that is, all
literals of c are positive or all literals of c are negative. Note that this is not the standard
notion of monotone Boolean formulas. Formula = (U , C) is planar if its variable
clause graph G = (U C, E) is planar. The graph G is bipartite and every edge in E
is incident to both a clause vertex from C and a variable vertex from U . The edge {c, u}
is contained in E if and only if a literal of variable u U occurs in c C. In the decision
problem P LANAR M ONOTONE 3-S ATISFIABILITY we are given a planar and monotone
3SAT formula together with a monotone rectilinear representation R of the variable
clause graph of and we need to decide whether is satisable. The representation R
is a contact representation on an integer grid, see Figure 2a. In R the variables are
represented by horizontal line segments arranged on a line . The clauses are represented
by E-shapes. All positive clauses are placed above and all negative clauses are placed
below . P LANAR M ONOTONE 3-S ATISFIABILITY is N P-complete [4].
Evans et al. [8] showed that P LANAR D ISK O BEDIENCE R ECOGNITION is N P-hard.
Further, they provide a polynomial time algorithm to recognize disk-obedience graphs
for the case that the respective disk intersection graph is thin and unit. A disk intersection
graph G is thin if (i) the graph distance between any two triangles of G is larger than 48
and (ii) removal of all disks within graph distance 8 of a triangle decomposes the graph
into isolated paths. A path is isolated if for any pair of adjacent disks A and B of the
path, the convex hull of A B is intersected only by disks adjacent to A or B.
In this section we strengthen the N P-hardness result by Evans et al. by showing that
P LANAR D ISK O BEDIENCE R ECOGNITION is N P-hard even for unit disks. Further,
we show that the path-isolation property of thin disk intersection graphs is essential to
make the problem tractable. This is implied by the fact that our result holds even for
disk intersection graphs that are thinnish, that is, removing all disks that belong to a
76 B. Banyassady et al.
c c
c c
1 1
s s
u1 u2 u5
v v v v v v v v v v
u3 u4 u5 s s
1 1
u1 u2 u3 u4 u5 s s s s s s
1 1 1 1 1 1
u3 u 4 u 5 c c
u2 u3 u5 c c
u1 u2 u5 c c
(a) (b) (c)
Fig. 2: (a) A monotone rectilinear representation. For the purposes of illustration, the line segments
representing variables and clauses are thickened and labeled. (b) Gadget layout mimicking the
monotone rectilinear representation from (a) in the proof of Theorem 1. The v-nodes are variable
gadgets, the c-nodes are clause gadgets, the s-nodes are splitter gadgets and the (1)-nodes are
inverter gadgets. The input of the splitter gadgets are marked with an arrow. The black polygonal
paths represent wires. (c) Gadget layout for the proof of Theorem 3
triangle decomposes the graph into disjoint paths (which are not necessarily isolated).
Being thinnish does not impose any distance or other geometric constraint on the set of
disks and its intersection graph. Nevertheless, our reduction also works if the distance
between any two triangles is lower bounded by some value. In particular, this implies
that spacial separation of triangles is not sufcient for tractability.
(a) (b)
Fig. 3: The variable gadget has two possible states: narrow and wide. It can also be used as an
inverter as either the wire to the left or to the right has to be in narrow position.
upper path of disks and vice versa. We say these paths are in a narrow position. On
the other hand, the paths on the right side are in a wide position: the upper path in the
obedient plane straight-line drawing of the disk intersection graph belongs to the upper
path of disks. By ipping the combinatorial embedding of the subgraph induced by the
edges incident to the triangle vertices of the gadget, we can allow the left paths to be
in wide position and the right path to be in narrow position; see Figure 3b. However,
observe that (i) without ipping the embedding it is not possible to switch between
the narrow and the wide positions and (ii) exactly one side has to be in narrow and the
other in wide position in order to avoid edge-crossings. We shall use these two states of
the variable gadget to encode the truth state of the corresponding variable. The parallel
paths of disks to either side of the triangle act as wires that propagate the state of the
variable gadget. Figure 4a illustrates the information propagation and shows that it is not
necessary that the disk centers of the two parallel paths are collinear. Thus, wires are
very exible structures that allow us to transmit the truth states of the variable gadgets to
other gadgets in our construction. Observe that our variable gadget can also be used as
an inverter. If the narrow state is propagated to the triangle from one side, the other side
is forced to propagate the wide state and vice versa.
Clauses. For each clause vertex we create a clause gadget as depicted in Figure 4b.
Each of the three sets of disks {R1 , R2 , ...}, {G1 , G2 , ...} and {B1 , B2 , ...} belong to
one wire. Note that if a wire is in narrow position, the position of the vertices of the
wire is essentially unique up to an arbitrarily small wiggle room. The clause gadget is
designed such that if all three of its wires are in narrow position the disk intersection
graph can not be drawn obediently. The reason for this is that the unique positions of
the vertices of the triangle r1 g1 b1 in the middle of the gadget enforce a crossing, see
Figure 4b. However, if at least one of the incident wires is in wide position and, thus,
at least one of u, v or w can be placed freely in its disk, then the gadget can be drawn
obediently.
Splitters. The nal gadget in our construction is the splitter gadget, see Figure 5a.
It works as follows. The three sets of disks {R1 , R2 , ...}, {G1 , G2 , ...} and {B1 , B2 , ...}
belong to three wires r, g, b respectively. We also created a disk O which almost com-
pletely overlaps with G2 . Without the disk O the gadget would contain a vertex of
degree 3 that is not part of a triangle. The disk O articially creates a triangle so that the
resulting disk intersection graph is thinnish. We refer to the wire b as the input of the
gadget and to the wires r and g as the outputs. If the input is narrow then both outputs
have to be wide due to the unique positions of the vertices in the narrow wires. However,
78 B. Banyassady et al.
b4
B3 B4
b3 B2
G2 R2
b2
B1
G4 R4
g2 g1 r1
b1 r2
g3 r3 r4
g4
g5 G1 R1 r5
G3 R3
(a) (b)
Fig. 4: (a) A curved wire that propagates the narrow position between the two disks with dashed
boundary. (b) The clause gadget.
if the input is wide, then any of the outputs can have any combination of states. For
instance, both can be narrow. For our reduction we shall always connect the two outputs
to inverters so that if the input of the splitter is narrow, then the inverted outputs are also
narrow.
Layout. Figure 2b illustrates how we layout and combine our gadgets. We mimic
the monotone rectilinear representation R for . We place the variable gadgets and
clause gadgets according to R. Consider a variable u U . From the variable gadget of u
one wire wt leads to the top; another wire wb leads to the bottom. If u occurs as a literal
only once in a positive clause, the top wire wt leads directly to the corresponding clause
gadget. Otherwise, it leads to the input of a splitter. As stated earlier, we connect the
outputs of the splitter to inverters. We split the resulting wires recursively until we have
created as many wires as there are literals of u in positive clauses. We call the created
wires the children of wt and wt is their origin. Similarly, the wire wb that leads from the
variable gadget of u to the bottom is connected to the negative clauses in which u occurs
and the resulting wires are the children of wb and wb is their origin. Further, we refer
to u as the variable of wt and wb . Note that while in some of our gadgets we require
very precise coordinates, the required precision does not depend on the input size. Thus,
the construction can be carried out in polynomial time.
Correctness. It remains to argue that our reduction is correct. Recall that if the input
of a splitter is narrow then the outputs are wide. Since we place inverters at the outputs of
each splitter it follows that all children of a narrow wire w are also narrow. Conversely,
if a wire connected to a clause gadget is wide then it is a child of a wide wire.
Assume there exists an obedient plane straight-line drawing of the disk intersection
graph of the set of disks we created. We create a satisfying truth assignment for . In
an obedient plane straight-line drawing, for each clause gadget c there is at least one
wire w connected to c that is wide; otherwise there is a crossing in the subdrawing of the
clause gadget. Consequently, the origin of w is wide as well. If c is positive, we set the
variable of w to true and if c is negative we set the variable of w to false. Thus, we have
created a truth assignment in which for each clause, there is at least one satised literal.
Note that it is not possible that we set a variable to both true and false since a wire can
Obedient Plane Drawings for Disk Intersection Graphs 79
B3
G1 B2
G3
b3 r1
b2
B1 b1
o g1
g3 g2 r1
g4
R2
b1
R1
r2
O R4
G2 r3
G4
g1
r4
g2 o R3
r5
(a)
only be the origin of either positive of negative clauses due to the fact that in a monotone
rectilinear representation all negative clauses are below and all positive clauses are above
the variable line.
Finally, assume that is satisable. For each variable u we orient its variable gadget
such that the wire that leads to the positive clauses is wide if and only if u is true. We
draw the splitter gadgets such that all children of wide wires are wide. Since every clause
has a satised literal, the corresponding clause gadget is connected to a wide wire and,
thus, can be drawn without introducing crossing.
Spacial Separation. Note that the splitter, variable, clause and inverter gadgets each
contain one triangle and recall that all gadgets are connected by wires, which do not
contain triangles. Thus, it is straightforward to ensure a minimum distance between any
two triangles by simply increasing the length of our wires accordingly.
H C
c
h r R A pac pbc
x q p
l p a pab b
t
T B
L
(a) (b)
Fig. 6: (a) Every crossing between centered edges implies the existence of an arrow. (b) In a
centered drawing, every point in a ply-3 triangle abc belongs to one of the three disks.
embeddings for the triangle-induced subgraphs is bounded. This motivates the following
denition. Let D be a set of disks and G = (V, E) be the intersection graph of D. A
triangle abc of G is called light if deg(a), deg(b), deg(c) 3 or if A B C = . We
say that D is light if every triangle of G is light. In this section we show that for any
light set D of disks there always exists an obedient plane straight-line drawing of the
intersection graph of D. Note that we do not require the disks in D to have unit radius.
We begin by introducing some notations and by stating some helpful observations. A
set of disks is connected if the union of all disks is connected. A set D of disks is said
to be in general position if for any connected subset D D, |D | = 3 the disk centers
of D are non-collinear. Let G = (V, E) be the intersection graph of a set of disks D
and be a straight-line drawing of G. A vertex v V that is placed at its respective
disks center in is called centered. An edge e E between two centered vertices in
is called centered. The drawing is called centered if all vertices in V are centered. An
arrow (h, t, l, r) in a straight-line drawing of a graph G = (V, E) is a sequence of
vertices h, t, l, r V such that ht, hl, hr, lr E and such that ht and lr cross in , see
Figure 6a. We refer to h, t, l, r as the arrows head, tail, left and right vertex respectively.
Evans et al. [8] show that any set of disks with ply 2 in general position admits an
obedient plane straight-line drawing. We observe that with some minor adaptations, their
observation furthermore yields an explicit statement regarding the graph structure in
non-plane centered drawings. We restate their proof together with our modications
to show that every crossing between centered edges implies the existence of an arrow.
Furthermore, we strengthen this statement by showing that if the intersection point x of
the two edges is contained in the interior of one of the corresponding disks, then there
always is an arrow whose heads disk contains x in its interior.
Lemma 1. Let G = (V, E) be the disk intersection graph of a set of disks D in general
position. Let be a straight-line drawing of G. For any crossing in between centered
edges ab and cd there exists an arrow (h, t, l, r) where H L R lr = and either
(i) ht = ab and lr = cd, or (ii) ht = cd and lr = ab. Furthermore, if x = ab cd is
contained in the interior of at least one of A, B, C, D, then x int(H).
Obedient Plane Drawings for Disk Intersection Graphs 81
Our nal auxiliary result states that under certain conditions, the number of crossings
along one edge in a centered drawing is at most one.
Lemma 2. Let D be a light set of disks in general position and let G = (V, E) be the
intersection graph of D. Let be a straight-line drawing of G. Let (a, b, c, d) be an
arrow in where a, b, c, d are centered and A C D cd = . Then there exists no
centered edge other than ab that crosses cd in .
Proof Sketch. According to the denition of an arrow, we know that ab, cd, ac, ad E,
see Figure 7c (left). Assume that some centered edge f g = ab crosses cd. According
to Lemma 1, the intersection of f g and cd implies existence of an arrow A consisting
of c, d and two other vertices f and g, at least one of which has to be different from a
and b. Since acd is a light triangle in G and since A C D = , the degree of a, c, d
is bounded by 3. Due to deg(a) 3 the vertex a can not be connected to any vertex
other than b, c, d, which means that a cannot be an endpoint of the edge f g. Note that b
could be equal to f or g. We perform a case distinction regarding the containment of the
edges bc and bd in E.
First, assume that bc E and bd E, see Figure 7a (left). Because of the degree
restrictions for c and d, neither of them can be adjacent to a vertex different from a, b, c, d.
Thus, cd can not be the head-tail edge of A since the head of A is connected to f and
g. If cd is the left-right edge of A, then the head of A has to be b and without loss of
generality f is equal to b. Due to Lemma 1 we know that B C D = and, thus,
since bcd is light the degree of b is bounded by 3. However, this is a contradiction to the
fact that b is connected to g.
Now, assume that bc E and bd / E, see Figure 7b. Similar to the last case, the
degree restriction for c implies that c can not be adjacent to any vertex other than a, b, d.
This implies that c can not be the head of A and it can be the right or the left vertex
of A only if b is the head of A. In this case cd is the left-right edge of A and d has to
be connected to the head b of A, which contradicts bd / E. Thus, c can only be the tail
of A, and so d is the head. The head d is connected to f and g both of which have to
be different from a and b due to deg(a) 3 and due to bd / E respectively. This is a
contradiction to deg(d) 3.
We sketch the nal case. Assume bc / E and bd / E, see Figure 7c (left). Due to
degree restrictions we see that cd is the left-right edge of A and w.l.o.g. g = b is the
head. Head g can not be located inside triangle acd since this would imply an additional
crossing with ab, which contradicts degree restrictions. If g is exterior to acd and f is
interior, Observation 1 implies a contradiction to the degree bounds of a, c, d. If g and
f are exterior to acd, f g has to cross ad or ac, which implies the existence of another
arrow, again contradicting degree restrictions.
82 B. Banyassady et al.
a d d a d
a
c b c b c b
(a) (b)
a d d d e d e
a b
a
a b
c b c b c f c f
(c) (d)
Theorem 2. Let D be a light set of disks in general position whose intersection graph
is G. Then G has a plane straight-line drawing obedient to D.
Proof. We describe an iterative approach that transforms a centered drawing of G into a
crossing-free drawing obedient to D. In each step we change the position of precisely
one, two or three vertices to remove one or two crossings. During the entire procedure,
each vertex is moved at most once. We maintain the following invariant: After and before
each step, all crossing edges are centered. We proceed by describing our algorithm. After
that we show that the invariant is maintained and, thus, that the algorithm is correct.
Algorithm. Let ab and cd be two centered edges that cross in a point x. By Lemma 1
there exists an arrow consisting of a, b, c, d, w.l.o.g. (a, b, c, d), where AC Dcd = ,
see Figure 7c (left). Note that this implies that the degree of a, c, d is bounded by 3
since D is light and since A C D = . In order to remove the crossing we move
some of a, b, c, d and we use a , b , c , d to denote the new postions of these vertices.
We distinguish two cases. First assume that x A B C D and x / int(A)
int(B) int(C) int(D), i.e. x is on the boundary of all four disks. In this case we
set a = x and we move vertices c, d by a distance R+ in the direction given by
the vector ba, see Figure 7a. Value should be chosen small enough such that c C,
d D and c d does not cross an edge ef , unless cd already crosses ef .
vertices is incident to an edge that has a crossing. In our algorithm we considered two
main cases. In the rst case we moved vertices a, c and d, which formed a complete
graph with vertex b. Note that all these vertices have exactly degree three due to the
degree restrictions. Therefore none of them can be adjacent to a vertex different from
a, b, c, d. In the second case we moved vertex a, which is adjacent to exactly b, c and d
due the degree restriction on a. Therefore, in both cases the moved vertices can only be
incident to edges with crossing if there exists some edge ef = ab, cd that has a crossing
with ab or cd. According to Lemma 2 there is no edge that crosses cd except for ab.
Due to Lemma 1, if ef crosses ab, there exists an arrow A composed of the edge ef
and ab. According to Lemma 2, ab can not be the left-right edge of A. The degree of a
is bounded by 3 and, thus, a has to be the tail, b has to be the head and e, f have to be
the left and right vertex of A.
We perform a case distinction regarding the equivalence of e, f and c, d. First,
asumme that {e, f } = {c, d} and without loss of generality e = d and f = c. Then A
consists of a, b, c, d. Next, assume that exactly one of e, f is equal to one of c, d and
without loss of generality e = d and f = a, b, c, d. Then d is adjacent to a, c, b, f ,
which contradicts the degree bound for d. Finally assume that both e, f are distinct
from a, b, c, d. By Lemma 2, neither cd nor ef can have a crossing with any edge other
than ab. Hence, the situation looks like the one illustrated in Figure 7d. In this case, in
addition to moving a to x, we move b to y = ab ef as described above. Now, a b
does not have any crossing and, thus, a is not incident to an edge with a crossing. For
symmetric reasons, neither is b .
the interesting question whether a more general statement can be made that captures all
these hardness results at once.
NP-Membership. For many combinatorial problems, showing N P-membership is
an easy exercise. For disk-obedience the question turns out to be much more intricate.
A naive idea to show NP-membership would be to guess the coordinates of all vertices.
However, it is not obvious that there always exists a rational representation of bounded
precision. Indeed, there are several geometric problems where this approach is known to
fail. In some cases an explicit rational representation may require an exponential number
of bits, in others optimal solutions may require irrational coordinates, see [1,3,14]. Many
problems initially not known to lie in N P turned out to be R-complete. The complexity
class R captures all computational problems that are equivalent under polynomial time
reductions to the satisability of arbitrary polynomial equations and inequalities over
the reals, see [6, 14]. We leave it as an open problem to determine the relation of disk
obedient plane straight-line drawings with respect to N P and R.
Acknowledgments. This work was initiated during the Fixed-Parameter Computa-
tional Geometry Workshop at Lorentz Center, April 48, 2016. We thank the organizers
and all participants for the productive and positive atmosphere.
References
1. Abrahamsen, M., Adamaszek, A., Miltzow, T.: Irrational guards are sometimes needed. arXiv
preprint arXiv:1701.05475 (2017)
2. Angelini, P., Lozzo, G.D., Bartolomeo, M.D., Battista, G.D., Hong, S., Patrignani, M., Roselli,
V.: Anchored drawings of planar graphs. In: Graph Drawing. Lecture Notes in Computer
Science, vol. 8871, pp. 404415. Springer (2014)
3. Bajaj, C.: The algebraic degree of geometric optimization problems. Discrete & Computational
Geometry 3(2), 177191 (1988)
4. de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J.
Comput. Geometry Appl. 22(3), 187206 (2012)
5. Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc
wireless networks. Wireless networks 7(6), 609616 (2001)
6. Cardinal, J.: Computational geometry column 62. SIGACT News 46(4), 6978 (2015)
7. Evans, W., Kirkpatrick, D., Lofer, M., Staals, F.: Minimizing co-location potential of moving
entities. SIAM J. Comput. 45(5), 18701893 (2016)
8. Evans, W.S., van Garderen, M., Lofer, M., Polishchuk, V.: Recognizing a DOG is hard, but
not when it is thin and unit. In: FUN 2016. pp. 16:116:12 (2016)
9. Keszegh, B., Pach, J., Palvolgyi, D.: Drawing planar graphs of bounded degree with few
slopes. SIAM Journal on Discrete Mathematics 27(2), 11711183 (2013)
10. Kroller, A., Fekete, S.P., Psterer, D., Fischer, S.: Deterministic boundary recognition and
topology extraction for large sensor networks. In: SoDA 2006. pp. 10001009 (2006)
11. Kuhn, F., Moscibroda, T., Wattenhofer, R.: Unit disk graph approximation. In: Proceedings of
the 2004 joint workshop on Foundations of mobile computing. pp. 1723. ACM (2004)
12. Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: of theory and
practice. In: PoDC. pp. 6372 (2003)
13. Lofer, M.: Data Imprecision in Computational Geometry. Ph.D. thesis, Utrecht University
(2009)
14. Matousek, J.: Intersection graphs of segments and R. arXiv preprint arXiv:1406.2636 (2014)
15. Wang, Y., Gao, J., Mitchell, J.S.B.: Boundary recognition in sensor networks by topological
methods. In: MobiCom 2006. pp. 122133 (2006)
-Greedy t-spanner
1 Introduction
q to the set E if the length of the shortest path between p and q in G is more
than t|pq|, see Algorithm 1 for more details. It has been shown in [9, 8, 12, 11,
17, 21] that for every set of points, the Path-Greedy spanner has O(n) edges, a
bounded degree and total weight O(wt(M ST (P ))), where wt(M ST (P )) is the
weight of a minimum spanning tree of P . The main weakness of the Path-Greedy
algorithm is its time complexity the naive implementation
of the Path-Greedy
algorithm runs in near-cubic time. By performing n2 shortest path queries,
where each query uses Dijkstras shortest path algorithm, the time complexity
of the entire algorithm reaches O(n3 log n), where n is the number of points in
P . Therefore, researchers in this eld have been trying to improve the Path-
Greedy algorithm time complexity. For example, the Approximate-Greedy algo-
rithm generates a graph with the same theoretical properties as the Path-Greedy
spanner in O(n log n) time [13, 19]. However, in practice there is no correlation
between the expected and the unsatisfactory resulting spanner as shown in [15,
16]. Moreover, the algorithm is complicated and dicult to implement.
Another attempt to build a t-spanner more eciently is introduced in [14,
15]. This algorithm uses a matrix to store the length of the shortest path between
every two points. For each pair of points, it rst checks the matrix to see if there
is a t-spanning path between these points. In case the entry in the matrix for this
pair indicates that there is no t-spanning path, it performs a shortest path query
and updates the matrix. The authors in [15] have conjectured that the number
of performed shortest path queries is linear. This has been shown to be wrong
in [5], as the number of shortest path queries may be quadratic. In addition, Bose
et al. [5] have shown how to compute the Path-Greedy spanner in O(n2 log n)
time. The main idea of their algorithm is to compute a partial shortest path
and then extend it when needed. However, the drawback of this algorithm is
that it is complex and dicult to implement. In [1], Alewijnse et al. compute
the Path-Greedy spanner using linear space in O(n2 log2 n) time by utilizing the
Path-Greedy properties with respect to the Well Separated Pair Decomposition
(WSPD). In [2], Alewijnse et al. compute a t-spanner in O(n log2 n log2 log n)
expected time by using bucketing for short edges and by using WSPD for long
edges. Their algorithm is based on the assumption that the Path-Greedy spanner
consists of mostly short edges.
Additional eort has been put in developing algorithms for computing t-
spanner graphs, such as -Graph algorithm [10, 18], Sink spanner, Skip-List
spanner [3], and WSPD-based spanners [6, 7]. However, none of these algorithms
produces a t-spanner as good as the Path-Greedy spanner in all aspects: size,
weight and maximum degree, see [15, 16].
Therefore, our goal is to develop a simple and ecient algorithm that achieves
both the theoretical and practical properties of the Path-Greedy spanner. In this
paper we introduce the -Greedy algorithm that constructs such a spanner for
a set of n points in the plane in O(n2 log n) time. Moreover, we show that for
a set of n points placed independently at random in a unit square the expected
running time of the -Greedy algorithm is O(n log n).
-Greedy t-spanner 87
Algorithm 1 Path-Greedy(P, t)
Input: A set P of points in the plane and a constant t > 1
Output: A
t-spanner
G(V, E) for P
1: sort the n2 pairs of distinct points in non-decreasing order of their distances
and store them in list L
2: E
3: for (p, q) L consider pairs in increasing order do
4: length of the shortest path in G between p and q
5: if > t|pq| then
6: E := E |pq|
7: return G = (P, E)
2 -Greedy
In this section we describe the -Greedy algorithm (Section 2.1) for a given set
P of points in the plane, and two real numbers t and , such that 1 < t.
Then, in Section 2.2 we prove that the resulting graph is indeed a t-spanner with
bounded degree. Throughout this section we assume that < t (for example,
4
= t 5 or = 1+4t
5 ), except in Lemma 4, where we consider the case that = t.
that |pv| < |pu| < |pw|. Point v lies in Cp representing the rst case, where the
algorithm does not change the spanner and proceeds to the next pair without
performing a shortest path query. The algorithm runs a shortest path query be-
tween p and u, since u / Cp (for the purpose of illustration assume p / Cu ).
Figure 1(b) describes the second case of the algorithm, where the length of the
shortest path between p and u is at most |pu|. In this case the algorithm adds
a cone to Cp without updating the spanner. Figure 1(c) describes the third case
of the algorithm, where the length of the shortest path between p and w is more
than |pw|. In this case the algorithm adds a cone to Cp and the edge (p, w) to
the spanner.
Algorithm 2 -Greedy
Input: A set P of points in the plane and two real numbers t and s.t. 1 < t
Output: A
t-spanner
for P
1: sort the n2 pairs of distinct points in non-decreasing order of their distances
(breaking ties arbitrarily) and store them in list L
2: E /* E is the edge set */
3: Cp p P /* Cp is set of cones with apex at p */
4: G (P, E) /* G is the resulting t-spanner */
5: for (p, q) L consider pairs in increasing order do
6: if (p / Cq ) and (q / Cp ) then
7: d length of the shortest path in G between p and q divided |pq|
8: if d > then
9: E E {(p, q)}
10: d 1
1
11: 4 arcsin( d2t ) /* cos sin t
= d */
12: cp (2, q) cone of angle 2 with apex at p and bisector pq
13: cq (2, p) cone of angle 2 with apex at q and bisector qp
14: Cp Cp cp (2, q)
15: Cq Cq cq (2, p)
16: return G = (P, E)
u u u
v v v
w w w
p p p
Proof. Let r be the orthogonal projection of r onto segment pq. Then, |rr | =
|pr| sin , |pr | = |pr| cos , and |r q| = |pq| |pr |. Thus, |r q| = |pq| |pr| cos .
By the triangle inequality
Proof. Clearly, the number of shortest path queries performed for each point is
at most n 1. Thus, we may assume that t/ > 1 + 1/n. Consider a point p P
and let (p, q) and (p, r) be two pairs of points that -Greedy algorithm has run
shortest path queries for. Assume w.l.o.g. that the pair (p, r) has been considered
before the pair (p, q), i.e., |rp| |pq|. Let d be the length of the path computed
by the shortest path query for (p, r) divide by |pr|. If d , then the cone added
to the collection Cp has an angle of at least 4 arcsin( 2t ). Otherwise, the
algorithm adds the edge (p, r) to G and a new cone to the collection of cones Cp ,
where the angle of this cone is 4 arcsin( 12t ). Thus, after the shortest path
query performed for the pair (p, r), the collection Cp contains a cone cp (, r),
where is at least 2 2 arcsin( 2t ). The -Greedy algorithm performs a shortest
path query for (p, q) only if p / Cq and q / Cp . Thus, the angle rpq is at least
t t
0, 1 + , and 1.
2 1
Thus, we have k = O( t/1 ).
1
t
x1
Observation 1 For = t x , where x > 1 is a xed integer, the number of
x
shortest path queries performed by -Greedy algorithm for each point is O( t1 ).
t1
t (1 + )x , t 1 + x , and .
x
2x
Thus, we have k t1
x
= O( t1 ).
2
n log n
Observation 2 The running time of -Greedy algorithm is O( (t/1) 2 ).
Proof. The algorithm sorts the n2 pairs of distinct points in non-decreasing
order of their distances, this takes O(n2 log n) time. A shortest path query is
n
done by Dijkstras shortest path algorithm on a graph with O( t/1 ) edges and
n 1
takes O( t/1 +n log n) time. By Lemma 2 each point performs O( t/1 ) shortest
path queries. Therefore, we have that the running time of -Greedy algorithm is
n
O(( t/1 )2 log n).
Observation 3 The number of cones that each point has in its collection along
1
the algorithm is constant depending on t and (O( t/1 )).
Proof. As shown in Lemma 2, the number of shortest path queries for each point
1
is O( t/1 ). The subsequent step of a shortest path query is the addition of two
cones, meaning that for each point p the number of cones in the collection of
1
cones Cp is O( t/1 ).
Corollary 1. The additional space for each point p for the collection Cp is con-
stant.
Proof. Let G = (P, E) be the output graph of the -Greedy algorithm. To prove
that G is a t-spanner for P we show that for every pair (p, q) P , there exists a
t-spanning path between them in G. We prove the above statement by induction
-Greedy t-spanner 91
on the rank of the distance |pq|, i.e., the place of (p, q) in a non-decreasing
distances order of all pairs of points in P .
Base case: Let (p, q) be the rst pair in the ordered list (i.e., the closest pair).
The edge (p, q) is added to E during the rst iteration of the loop in step 9 of
Algorithm 2, and thus there is a t-spanning path between p and q in G.
Induction hypothesis: For every pair (r, s) that appears before the pair (p, q)
in the ordered list, there is a t-spanning path between r and s in G.
The inductive step: Consider the pair (p, q). We prove that there is a t-
spanning path between p and q in G. If p / Cq and q / Cp , we check whether
there is a -spanning path in G between p and q. If there is a path which length
is at most |pq|, then |pq| t|pq|, meaning there is a t-spanning path between
p and q in G. If there is no path of length of at most |pq|, we add the edge (p, q)
to G, which forms a t-spanning path.
Consider that p Cq or q Cp , and assume w.l.o.g. that q Cp . Let (p, r)
be the edge handled in Step 5 in Algorithm 2 when the cone containing q has
been added to Cp (Step 12 in Algorithm 2). Notice that |pr| |pq|. Step 7 of
Algorithm 2 has computed the value d for the pair (p, r). In the algorithm there
are two scenarios depending on the value of d.
The rst scenario is when d > , then the algorithm has added the edge (p, r)
to G and a cone cp (, r) to Cp , where = 2( 4 arcsin( 12t )). Thus, the angle
between (p, q) and (p, r) is less than /2. Hence, |rq| < |pq| and by the induction
hypothesis there is a t-spanning path between r and q. Consider the shortest
path between p and q that goes through the edge (p, r). The length of this path
is at most |pr| + t|rq|. By Lemma 1, we have |pr| + t|rq| |pr| + t|rq| t|pq|
for = 1. Therefore, we have a t-spanning path between p and q.
The second scenario is when d , then the algorithm has added a cone
cp (, r) to Cp , where = 2( 4 arcsin( d2t )). Thus, the angle between (p, q)
and (p, r) is less than /2. Hence, |rq| < |pq| and by the induction hypothesis
there is a t-spanning path between r and q. Consider the shortest path between
p and q that goes through r. The length of this path is at most d|pr| + t|rq|. By
Lemma 1, we have d|pr| + t|rq| t|pq|. Therefore, we have a t-spanning path
between p and q.
Theorem 4. The -Greedy algorithm computes a t-spanner for a set of points
P with the same properties as the Path-Greedy t-spanner, such as degree and
n
weight, in O(( t/1 )2 log n) time.
Proof. Clearly, the degree of the -Greedy is at most the degree of the Path-
Greedy -spanner. The edges of the -Greedy spanner satisfy the -leap frog
property, thus, the weight of the -Greedy is as Path-Greedy t-spanner. Hence,
we can pick close to t, such that we will have the required bounds.
Lemma 4. If t = , the result of the -Greedy algorithm is identical to the result
of the Path-Greedy algorithm.
Proof. Assume towards contradiction that for t = the resulting graph of the
-Greedy algorithm, denoted as G = (P, E), diers from the result of the Path-
Greedy algorithm, denoted as G = (P, E ). Assuming the same order of the
92 G. Bar-On and P. Carmi
sorted edges, let (p, q) be the rst edge that is dierent in G and G . Notice
that -Greedy algorithm decides to add the edge (p, q) to G when there is no
t-spanning path between p and q in G. Since until handling the edge (p, q) the
graphs G and G are identical, the Path-Greedy algorithm also decides to add
the edge (p, q) to G . Therefore, the only case we need to consider is (p, q) E
and (p, q) / E. The -Greedy algorithm does not add an edge (p, q) to G in
two scenarios: (i) there is a t-spanning path between p and q in the current
graph G which contradicts that the Path-Greedy algorithm adds the edge
(p, q) to G ; (ii) p Cq or q Cp the -Greedy algorithm does not perform
a shortest path query between p and q. Assume w.l.o.g., q Cp , and let (p, r)
be the edge considered in Step 5 in Algorithm 2 when the cone containing q
has been added to Cp . The angle of the added cone is = 2 2 arcsin( d2t ),
where d is the length of the shortest path between p and r divided |pr|. Thus,
1
we have |pr| |pq| and cos sin d , where is the angle rpq. Then, by
t
Lemma 1, |pr| + t|rq| t|pq|, and since there is a path from p to r of length
at most |pr|, we have that there is t-spanning path between p and q in the
current graph. This is in contradiction to the assumption that the Path-Greedy
algorithm adds the edge (p, q) to E .
each point runs a constant number of shortest path queries follows from
Lemma 2;
the expected number of points visited in each query is constant The fact
that the points are randomly chosen uniformly in the unit square implies
that the expected number of points at distance of at most r from point p
is (r2 n). A shortest path query from a point p to a point q terminates
as soon as the minimum key in the priority queue exceeds |pq|, thus, it is
expected to visit O(n (|pq|)2 ) points.
By Lemma 2 the number of shortest path queries performed by the algorithm
1
for a point p is O( t/1 ). Each such query denes a cone with apex at p of
angle (t/ 1), such that no other shortest path query from p will be
1
performed to a point in this cone. By picking k = t/1 and r = kn , we
have that the expected number of points around each point in a distance of
1
r is (k 2 ) = ( (t/1) 2 ).
-Greedy t-spanner 93
Assume we partition the plane into k equal angle cones with apex at point p.
The probability that there exists a cone that does not contain a point from
2
the set of points of distance kn is at most k (1 k1 )k . Let Q be the set
of points that p computed a shortest path query to, and let q Q be the
farthest point in Q from p. Then, the expected Euclidean distance between
p and q is less than kn . Thus, the expected number of points visited by the
2 2 2
k
entire set of shortest path queries from a point is O( t/1 ) = O( (t) 3 );
Since both t and t/ are constants bigger than one, the expected running time
of the -Greedy algorithm is O(n log n).
A very nice outcome of -Greedy algorithm and its analysis can be seen
when is equal to t. Assume that -Greedy algorithm (for = t) has computed
a shortest path query for two points p and q and the length of the received path
is d|pq|. If the probability that t/d > 1 + is low (e.g, less than 1/2), for some
constant > 0, then -Greedy algorithm computes the Path-Greedy spanner
with linear number of shortest path queries. Thus -Greedy algorithm computes
the Path-Greedy spanner for a point set uniformly distributed in a square in
expected O(n log n) time.
Not surprisingly our experiments have shown that this probability is indeed
low (less than 1/100), since most of the shortest path queries are performed on
94 G. Bar-On and P. Carmi
pairs of points placed close to each other (with respect to Euclidean distance),
and thus with a high probability their shortest path contains a constant number
of points. Moreover, it seems that for a real-life input this probably is low.
Thus, there is a very simple algorithm to compute the Path-Greedy spanner in
expected O(n2 log n) time for real-life inputs, based on the -Greedy algorithm
For real-life input we mean that our analysis suggests that in the current
computers precision (Memory) one cannot create an instance of points set with
more than 1000 points, where the Path-Greedy spanner based on the -Greedy
algorithm has more than O(n2 log n) constructing time.
4 Experimental Results
In this section we discuss the experimental results by considering the properties
of the graphs generated by dierent algorithms and the number of shortest path
queries performed during these algorithms. We have implemented the Path-
Greedy, -Greedy, Gap-Greedy, -Graph, Path-Greedy on -Graph algorithms.
The Path-Greedy on -graph t-spanner, rst computes a -graph t -spanner,
where t < t, and then runs the Path-Greedy t/t -spanner on this t -spanner. The
shortest path queries criteria is used for an absolute running time comparison
that is independent of the actual implementation. The known theoretical bounds
for the algorithms can be found in Table 1.
The experiments were performed on a set of 8000 points, with dierent values
of the parameter (between 1 and t). We have chosen to present the parameter
for the values t, t0.9 and t. This values do not have special properties, they
where chosen arbitrary to present the behavior of the spanner.
To avoid the eect of specic instances, we have run the algorithms several
times and taken the average of the results. However, in all the cases the dierence
between the values is negligible. Table 24 show the results of our experiments
for dierent values of t and . The columns of the weight (divided by wt(M ST ))
and the degree are rounded to integers, and the columns of the edges are rounded
to one digit after the decimal point (in k).
The implementation details and the results analysis appear in [4].
Weight
Algorithm Edges wt(M ST ) Degree Time
1
n
Path-Greedy O( t1 ) O(1) O( t1 ) O(n3 log n)
n
Gap-Greedy O( t1 ) O(log n) 1
O( t1 ) O(n log2 n)
n
-Graph O( ) O(n) O(n) O( n log n)
1 1
-Greedy n
O( t/1 ) O(1) O( t/1 ) O( t/1 n2 log n)
References
1. S. P. A. Alewijnse, Q. W. Bouts, A. P. ten Brink, and K. Buchin. Computing the
greedy spanner in linear space. Algorithmica, 73(3):589606, 2015.
2. S. P. A. Alewijnse, Q. W. Bouts, A. P. ten Brink, and K. Buchin. Distribution-
sensitive construction of the greedy spanner. Algorithmica, pages 123, 2016.
3. S. Arya, D. M. Mount, and M. H. M. Smid. Randomized and deterministic algo-
rithms for geometric spanners of small diameter. In FOCS, pages 703712, 1994.
4. G. Bar-On and P. Carmi. -greedy t-spanner. CoRR, abs/1702.05900, 2017.
5. P. Bose, P. Carmi, M. Farshi, A. Maheshwari, and M. H. M. Smid. Computing the
greedy spanner in near-quadratic time. In SWAT, pages 390401, 2008.
6. P. B. Callahan. Optimal parallel all-nearest-neighbors using the well-separated
pair decomposition. In FOCS, pages 332340, 1993.
7. P. B. Callahan and S. R. Kosaraju. A decomposition of multi-dimensional point-
sets with applications to k-nearest-neighbors and n-body potential elds. In STOC,
pages 546556, 1992.
8. B. Chandra. Constructing sparse spanners for most graphs in higher dimensions.
Inf. Process. Lett., 51(6):289294, 1994.
9. B. Chandra, G. Das, G. Narasimhan, and J. Soares. New sparseness results on
graph spanners. Int. J. Comp. Geom. and Applic., 5:125144, 1995.
10. K. L. Clarkson. Approximation algorithms for shortest path motion planning. In
STOC, pages 5665, 1987.
11. G. Das, P. J. Heernan, and G. Narasimhan. Optimally sparse spanners in 3-
dimensional Euclidean space. In SoCG, pages 5362, 1993.
12. G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean
spanners. Int. J. Comp. Geom. and Applic., 7(4):297315, 1997.
13. G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean
spanners. Int. J. Comp. Geom. and Applic., 7(4):297315, 1997.
14. M. Farshi and J. Gudmundsson. Experimental study of geometric t-spanners. In
ESA, pages 556567, 2005.
15. M. Farshi and J. Gudmundsson. Experimental study of geometric t-spanners: A
running time comparison. In WEA, pages 270284, 2007.
16. M. Farshi and J. Gudmundsson. Experimental study of geometric t-spanners. ACM
Journal of Experimental Algorithmics, 14, 2009.
17. J. Gudmundsson, C. Levcopoulos, and G. Narasimhan. Fast greedy algorithms for
constructing sparse geometric spanners. SIAM J. Comput., 31(5):14791500, 2002.
18. J. M. Keil. Approximating the complete Euclidean graph. In SWAT, pages 208
213, 1988.
19. C. Levcopoulos, G. Narasimhan, and M. H. M. Smid. Improved algorithms for
constructing fault-tolerant spanners. Algorithmica, 32(1):144156, 2002.
20. G. Narasimhan and M. Smid. Geometric Spanner Networks. Cambridge University
Press, New York, NY, USA, 2007.
21. J. Soares. Approximating Euclidean distances by small degree graphs. Discrete &
Computational Geometry, 11(2):213233, 1994.
Dynamic Graph Coloring
1 Introduction
is clearly not optimal. A dynamic graph algorithm seeks to maintain some clever
data structure for the underlying problem such that the time taken to update
the solution is much smaller than that of the best static algorithm.
In this paper, we study the problem of maintaining a coloring in a dynamic
graph undergoing insertions and deletions of both vertices and edges. At rst sight,
this may seem to be a hopeless task, since there exist near-linear lower bounds
on the competitive factor of online graph coloring algorithms [9], a restricted
case of the dynamic setting. In order to break through this barrier, we allow a
fair number of vertex recolorings per update. We focus on the combinatorial
aspect of the problem the trade-o between the number of colors used versus
the number of recolorings per update. We present a strong general lower bound
and two simple algorithms that provide complementary trade-os.
Denitions and Results. Let C be a positive integer. A C-coloring of a graph
G is a function that assigns a color in {1, . . . , C} to each vertex of G. A C-coloring
is proper if no two adjacent vertices are assigned the same color. We say that G
is C-colorable if it admits a proper C-coloring, and we call the smallest such C
the chromatic number of G.
A recoloring algorithm is an algorithm that maintains a proper coloring of a
simple graph while that graph undergoes a sequence of updates. Each update
adds or removes either an edge or a vertex with a set of incident edges. We say
that a recoloring algorithm is c-competitive if it uses at most c Cmax colors,
where Cmax is the maximum chromatic number of the graph during the updates.
For example, an algorithm that computes the optimal coloring after every
update is 1-competitive, but may recolor every vertex for every update. At the
other extreme, we can give each vertex a unique color, resulting in a linear
competitive factor for an algorithm that recolors at most 1 vertex per update. In
this paper, we investigate intermediate solutions that use more than C colors but
recolor a sublinear number of vertices per update. Note that we do not assume
that the value C is known in advance, or at any point during the algorithm.
In Section 2, we present two complementary recoloring algorithms: an O(dN 1/d )-
competitive algorithm with an amortized O(d) recolorings per update, and an
O(d)-competitive algorithm with an amortized O(dN 1/d ) recolorings per update,
where d is a positive integer parameter and N is the maximum number of vertices
in the graph during a sequence of updates. Interestingly, for d = (log N ), both
are O(log N )-competitive with an amortized O(log N ) vertex recolorings per
update. Using standard techniques, the algorithms can be made sensitive to the
current (instead of the maximum) number of vertices in the graph.
We provide lower bounds in Section 3. In particular, we show that for any
recoloring algorithm A using c colors, there exists a specic 2-colorable graph on N
vertices and a sequence of m edge insertions and deletions that forces A to perform
2
at least (m N c(c1) ) vertex recolorings. Thus, any x-competitive recoloring
1
algorithm performs in average at least (N x(2x1) ) recolorings per update.
To allow us to focus on the combinatorial aspects, we assume that we have
access to an algorithm that, at any time, can color the current graph (or an
induced subgraph) using few colors. Of course, nding an optimal coloring of an
Dynamic Graph Coloring 99
For the description of our algorithms we consider only inserting a vertex with its
incident edges. Deletions cannot invalidate the coloring and edge insertions can
be done by removing and adding one of the vertices with the appropriate edges.
Our algorithms partition the vertices into a set of buckets, each of which has
its own distinct set of colors. All our algorithms guarantee that the subgraph
induced by the vertices inside each bucket is properly colored and this implies
that the entire graph is properly colored at all times.
The algorithms dier in the number of buckets they use and the size (maximum
number of vertices) of each bucket. Typically, there is a sequence of buckets of
increasing size, and one reset bucket that can contain arbitrarily many vertices
and that holds vertices whose color has not changed for a while. Initially, the size
of each bucket depends on the number of vertices in the input graph. As vertices
are inserted and deleted, the current number of vertices changes. When certain
100 L. Barba et al.
si si si si
1 1 1 1
s s 1
Fig. 1: The small-buckets algorithm uses d levels, each with s buckets of capacity si ,
1/d
where i is the level, s = NR , and NR is the number of vertices during the last reset.
buckets are full, we reset everything, to ensure that we can accommodate the
new number of vertices. This involves emptying all buckets into the reset bucket,
computing a proper coloring of the entire graph, and recomputing the sizes of
the buckets in terms of the current number of vertices.
We refer to the number of vertices during the most recent reset as NR , and
1/d
we express the size of the buckets in s = NR , where d > 0 is an integer
parameter that allows us to achieve dierent trade-os between the number
of colors and number of recolorings used. Since s = O(N 1/d ), where N is the
maximum number of vertices thus far, we state our bounds in terms of N . Note
that it is also possible to keep NR within a constant factor of the current number
of vertices by triggering a reset whenever the current number of vertices becomes
too small or too large. We omit these details for the sake of simplicity.
Our rst algorithm, called the small-buckets algorithm, uses a lot of colors, but
needs very few recolorings. In addition to the reset bucket, the algorithm uses
ds buckets, grouped into d levels of s buckets each. All buckets on level i, for
0 i < d, have capacity si (see Fig. 1). Initially, the reset bucket contains
all vertices, and all other buckets are empty. Throughout the execution of the
algorithm, we ensure that every level always has at least one empty bucket. We
call this the space invariant.
When a new vertex is inserted, we place it in any empty bucket on level 0.
The space invariant guarantees the existence of this bucket. Since this bucket
has a unique set of colors, assigning one of them to the new vertex establishes a
proper coloring. Of course, if this was the last empty bucket on level 0, lling it
violates the space invariant. In that case, we gather up all s vertices on this level,
place them in the rst empty bucket on level 1 (which has capacity s and must
exist by the space invariant), and compute a new coloring of their induced graph
using the set of colors of the new bucket. If this was the last free bucket on level
1, we move all its vertices to the next level and repeat this procedure. In general,
if we lled the last free bucket on level i, we gather up all at most s si = si+1
vertices on this level, place them in an empty bucket on level i + 1 (which exists
by the space invariant), and recolor their induced graph with the new colors. If
we ll up the last level (d 1), we reset the structure, emptying each bucket into
Dynamic Graph Coloring 101
n1/3 1-trees
...
... ...
... ... ... ... ... ...
1/3
Fig. 3: (left) A 1-conguration is any forest that has many 1-trees as induced subgraphs.
(right) A 2-tree is constructed by connecting the roots of many 1-trees.
3 Lower bound
In this section we prove a lower bound on the amortized number of recolorings for
any algorithm that maintains a c-coloring of a 2-colorable graph, for any constant
c 2. We say that a vertex is c-colored if it has a color in [c] = {1, . . . , c}. For
simplicity of description, we assume that a recoloring algorithm only recolors
vertices when an edge is inserted and not when an edge is deleted, as edge deletions
do not invalidate the coloring. This assumption causes no loss of generality, as
we can delay the recolorings an algorithm would perform in response to an edge
deletion until the next edge insertion.
The proof for the lower bound consists of several parts. We begin with a specic
initial conguration and present a strategy for an adversary that constructs a
large conguration with a specic colouring and then repeatedly performs costly
operations in this conguration. In light of this strategy, a recoloring algorithm
has a few choices: it can allow the conguration to be built and perform the
recolorings required, it can destroy the conguration by recoloring parts of it
instead of performing the operations, or it can prevent the conguration from
being built in the rst place by recoloring parts of the building blocks. We show
that all these options require a large number of amortized recolorings.
n2/3 1 leaf nodes attached to it. Initially, our forest consists of n1/3 pairwise
disjoint 1-trees, which account for all n vertices in our forest. The sequence of
updates we construct never performs a cut operation among the edges of a 1-tree.
Thus, the forest remains a 1-conguration: a forest of rooted trees with the n1/3
independent 1-trees as induced subgraphs; see Fig. 3 (left). We require that the
induced subtrees are not upside down, that is, the root of the 1-tree should be
closer to the root of the full tree than its children. Intuitively, a 1-conguration
is simply a collection of our initial 1-trees linked together into larger trees.
Let F be a 1-conguration. We assume that A has already chosen an initial
3-coloring of F . We assign a color to each 1-tree as follows. Since each 1-tree is
properly 3-colored, the leaves cannot have the same color as the root. Thus, a
2/3
1-tree T always has at least n 2 1 leaves of some color C, and C is dierent
from the color of the root. We assign the color C to T . In this way, each 1-tree
is assigned one of the three colors. We say that a 1-tree with assigned color C
becomes invalid if it has no children of color C left. Notice that to invalidate
2/3
a 1-tree, algorithm A needs to recolor at least n 2 1 of its leaves. Since the
1/3
coloring uses only three colors, there are at least n 3 1-trees with the same
assigned color, say X. In the remainder, we focus solely on these 1-trees.
1/3
A 2-tree is a tree obtained by merging n 9 1-trees with assigned color X, as
follows. First, we cut the edge connecting the root of each 1-tree to its parent, if
it has one. Next, we pick a distinguished 1-tree with root r, and connect the root
1/3
of each of the other n 9 1 1-trees to r. In this way, we obtain a 2-tree whose
1/3
root r has n2/3 1 leaf children from the 1-tree of r, and n 9 1 new children
that are the roots of other 1-trees; see Fig. 3 (right) for an illustration. This
1/3 1/3
construction requires n 9 1 edge insertions and at most n 9 edge deletions (if
every 1-tree root had another parent in the 1-conguration).
1/3 1/3
We build 3 such 2-trees in total. This requires at most 6( n 9 ) = 2n3 updates.
If none of our 1-trees became invalid, then since our construction involves only
1-trees with the same assigned color X, no 2-tree can have a root with color X.
Further, since the algorithm maintains a 3-coloring, there must be at least two
2-trees whose roots have the same color. We can now perform a matching link,
by connecting the roots of these two trees by an edge (in general, we may need
to perform a cut rst). To maintain a 3-coloring after a matching link, A must
recolor the root of one of the 2-trees and either recolor all its non-leaf children
or invalidate a 1-tree. If no 1-tree has become invalidated, this requires at least
n1/3
9 recolorings, and we again have two 2-trees whose roots have the same color.
Thus, we can perform another matching link between them. We keep doing this
1/3
until we either performed n 6 matching links, or a 1-tree is invalidated.
1/3
Therefore, after at most n1/3 updates ( 2n3 for the construction of the 2-trees,
n1/3
and 3 for the matching links), we either have an invalid 1-tree, in which case
n2/3 1 n1/3
A recolored at least 2 nodes, or we performed 6 matching links, which
1/3 1/3 2/3
forced at least n 6 n 9 = n54 recolorings. In either case, we forced A to
2/3
perform at least (n ) vertex recolorings, using at most n1/3 updates.
104 L. Barba et al.
Since no edge of a 1-tree was cut, we still have a valid 1-conguration, where
the process can be restarted. Consequently, for any m 2n1/3 , there exists a
sequence of m updates that starts with a 1-conguration and forces A to perform
2/3
1/3 (n
nm ) = (m n1/3 ) vertex recolorings.
3.2 On k-trees
We are now ready to
{
describe a general lower n2/c
{
{
{
2(c2) 2(ck+1) 2(ck)
bound for any number 0-trees n c(c1)
n c(c1) n c(c1)
of colors c. The general
1-trees (k 2)-trees (k 1)-trees
approach is the same as
when using 3 colors: We Fig. 4: A k-tree is constructed by connecting the roots of
construct trees of height a large number of (k 1)-trees.
up to c + 1, each exclud-
ing a dierent color for the root of the merged trees. By now connecting two such
trees, we force the algorithm A to recolor the desired number of vertices.
A 0-tree is a single node, and for each 1 k c, a k-tree is a tree obtained
2(ck)
recursively by merging 2 n c(c1) (k 1)-trees as follows: Pick a (k 1)-tree and
2(ck)
let r be its root. Then, for each of the 2 n c(c1) 1 remaining (k 1)-trees,
connect their root to r with an edge; see Fig. 4 for an illustration.
As a result, for each 0 j k 1, a k-tree T consists of a root r with
2(cj1)
2 n c(c1) 1 j-trees, called the j-subtrees of T , whose root hangs from r. The
root of a j-subtree of T is called a j-child of T . By construction, r is also the
root of a j-tree which we call the core j-tree of T .
Whenever a k-tree is constructed, it is assigned a color that is present among
a large fraction of its (k 1)-children. Indeed, whenever
a k-tree is assigned a
2(ck)
color ck , we guarantee that it has at least 2c n c(c1) (k 1)-children of color ck .
We describe later how to choose the color that is assigned to a k-tree.
We say that a k-tree that was assigned color ck has a color violation if its
root no longer has a (k 1)-child with color ck . We say that a k-tree T becomes
invalid if either (1) it has a color violation or (2) if a core j-tree of T has a color
violation for some 1 j < k; otherwise we say that T is valid.
Observation 1 To obtain a color violation
in a k-tree constructed by the above
2(ck)
2
procedure, A needs to recolor at least c n c(c1) vertices.
Notice that a valid c-colored k-tree of color ck cannot have a root with color ck .
Formally, color ck is blocked for the root of a k-tree if this root has a child with
color ck . In particular, the color assigned to a k-tree and the colors assigned to
its core j-trees for 1 j k 1 are blocked as long as the tree is valid.
3.3 On k-congurations
A 0-conguration is a set F0 of c-colored nodes, where |F0 | = T0 = n, for
some suciently large constant which will be specied later. For 1 k < c, a
Dynamic Graph Coloring 105
Note that the trees of a k-conguration may be part of m-trees for m > k. If at
least T2k k-trees in a k-conguration are valid, then the conguration is valid.
For our construction, we let the initial conguration F0 be an arbitrary
c-colored 0-conguration in which each vertex is c-colored. To construct a k-
conguration Fk from a valid (k 1)-conguration Fk1 , consider the at least
Tk1
2 valid (k 1)-trees from Fk1 . Recall that the trees of Fk1 may be part
of larger trees, but since we consider edge deletions as free operations we can
separate the trees. Since each of these trees has a color assigned, among them at
least Tk1
2c have the same color assigned to them. Let ck1 denote this color.
2(ck)
Because each k-tree consists of 2 n c(c1) (k 1)-trees, to obtain Fk we merge
Tk1
2c (k 1)-trees of color ck1 into Tk k-trees, where
Tk1 1 k 2(ci)
Tk = 2(ck)
= k
n1 i=1 c(c1) .
2c 2 n c(c1) (4c)
(k 1)-tree used is valid, then each of the Tk k-trees of Fk is also valid. Thus,
Fk is a valid conguration. Moreover, for Fk to become invalid, A would need
to invalidate at least T2k of its k-trees. Since we use (k 1)-trees with the same
assigned color to construct k-trees, we can conclude the following about the use
of colors in any k-tree.
Lemma 3.2. Let Fk be a valid k-conguration. For each 1 j < k, each core
j-tree of a valid k-tree of Fk has color cj assigned to it. Moreover, ci = cj for
each 1 i < j < k.
(1) the tree has a color violation, but all its j 1-subtrees are valid and no
core i-tree for 1 i j 1 has a color violation; or
(2) A core i-tree has a color violation for 1 i j 1, or the tree has a
color violation and at least one of its (j 1)-subtrees is invalid.
In case (1) the algorithm A has to perform fewer recolorings, but the tree can be
made valid again with a color reassignment, whereas in case (2) the j-tree has to
be rebuild.
Let Y0 , Y1 and Y2 respectively be the set of j-trees of Fj that are either valid,
T
or are invalid by case (1) or (2) respectively. Because at least 2j j-trees were
T
invalidated, we know that |Y1 | + |Y2 | > 2j . Moreover, for each tree in Y1 , A
2(cj)
recolored at least 2c n c(c1) 1 vertices to create the color violation on this
j-tree by Observation 1. For each tree in Y2 however, A created a color violation
in some i-tree for i < j. Therefore, for each tree in Y2 , by Observation 1, the
2(ci) 2(cj+1)
number of vertices that A recolored is at least 2c n c(c1) 1 > 2c n c(c1) 1.
Case 1: |Y1 | > |Y2 |. Recall that each j-tree in Y1 has only valid (j1)-subtrees
by the denition of Y1 . Therefore, each j-tree in Y1 can be made valid again by
performing a color assignment on it while performing no update. In this way,
T
we obtain |Y0 | + |Y1 | > 2j valid j-trees, i.e., Fj becomes a valid j-conguration
contained in Fk . Notice that when a color assignment is performed on a j-tree,
vertex recolorings previously performed on its (j 1)-children cannot be counted
again towards invalidating this tree.
Since we have a valid j-conguration instead of a valid k-conguration, we
wasted some edge insertions. We say that the insertion of each edge in Fk that is
not an edge of Fj is a wasted edge insertion. By Lemma 3.3, to construct Fk from
Fj we used (Tj ) edge insertions. That is, (Tj ) edge insertions became wasted.
However, while we wasted (Tj ) edge insertions, we also forced A to perform
2(cj) 2(cj)
(|Y1 | n c(c1) ) = (Tj n c(c1) ) vertex recolorings. Since 1 j < k c 1, we
2(cj) 2 2
know that n c(c1) n c(c1) . Therefore, we can charge A with (n c(c1) ) vertex
recolorings per wasted edge insertion. Finally, we remove each edge corresponding
to a wasted edge insertion, i.e., we remove all the edges used to construct Fk
Dynamic Graph Coloring 107
per wasted edge insertion. Finally, we remove each edge corresponding to a wasted
edge insertion, i.e., we go back to the valid (j 1)-conguration Fj1 as before.
Lemma 3.4. After a reset phase in which h edge insertions become wasted, we
2
can charge A with (h n c(c1) ) vertex recolorings. Moreover, A will be charged
at most O(1) times for each recoloring.
Theorem 3.5. Let c be a constant. For any suciently large integers n and
depending only on c, and any m = (n) suciently large, there exists a forest
F with n vertices, such that for any recoloring algorithm A, there exists a
2
sequence of m updates that forces A to perform (m n c(c1) ) vertex recolorings
to maintain a c-coloring of F .
108 L. Barba et al.
References
1. S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in O(log n)
update time. SIAM J. on Comp., 44(1):88113, 2015.
2. S. Baswana, S. Khurana, and S. Sarkar. Fully dynamic randomized algorithms for
graph spanners. ACM Trans. on Alg., 8(4):35, 2012.
3. P. Borowiecki and E. Sidorowicz. Dynamic coloring of graphs. Fundamenta
Informaticae, 114(2):105128, 2012.
4. O. Coudert. Exact coloring of real-life graphs is easy. In Proc. 34th Design Autom.
Conf., pages 121126. ACM, 1997.
5. C. Demetrescu, D. Eppstein, Z. Galil, and G. F. Italiano. Dynamic graph algorithms.
In M. J. Atallah and M. Blanton, editors, Algorithms and Theory of Computation
Handbook. Chapman & Hall/CRC, 2010.
6. C. Demetrescu, I. Finocchi, and P. Italiano. Dynamic graphs. In D. Mehta and
S. Sahni, editors, Handbook on Data Structures and Applications, Computer and
Information Science. CRC Press, 2005.
7. A. Dutot, F. Guinand, D. Olivier, and Y. Pigne. On the decentralized dynamic
graph-coloring problem. In Proc. Worksh. Compl. Sys. and Self-Org. Mod., 2007.
8. M. M. Halldorsson. Parallel and on-line graph coloring. J. Alg., 23(2):265280,
1997.
9. M. M. Halldrsson and M. Szegedy. Lower bounds for on-line graph coloring. Theo.
Comp. Sci., 130(1):163 174, 1994.
10. M. Henzinger, S. Krinninger, and D. Nanongkai. A subquadratic-time algorithm
for decremental single-source shortest paths. In Proc. 25th ACM-SIAM Symp. on
Discr. Alg., pages 10531072, 2014.
11. J. Holm, K. De Lichtenberg, and M. Thorup. Poly-logarithmic deterministic
fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and
biconnectivity. J. ACM, 48(4):723760, 2001.
12. B. M. Kapron, V. King, and B. Mountjoy. Dynamic graph connectivity in polylog-
arithmic worst case time. In Proc. 24th ACM-SIAM Symp. on Discr. Alg., pages
11311142, 2013.
13. R. M. Karp. Reducibility among combinatorial problems. In Complexity of computer
computations, pages 85103. Plenum, New York, 1972.
14. L. Lovasz, M. E. Saks, and W. T. Trotter. An on-line graph coloring algorithm
with sublinear performance ratio. Discr. Math., 75(1-3):319325, 1989.
15. M. V. Marathe, H. Breu, H. B. Hunt, III, S. S. Ravi, and D. J. Rosenkrantz. Simple
heuristics for unit disk graphs. Networks, 25(2):5968, 1995.
16. L. Ouerfelli and H. Bouziri. Greedy algorithms for dynamic graph coloring. In
Proc. Int. Conf. on Comm., Comp. and Control App., pages 15, 2011.
17. D. Preuveneers and Y. Berbers. ACODYGRA: an agent algorithm for coloring
dynamic graphs. In Symb. Num. Alg. Sci. Comp., pages 381390, 2004.
18. L. Roditty and U. Zwick. Improved dynamic reachability algorithms for directed
graphs. In Proc. 43rd IEEE Sym. Found. Comp. Sci., pages 679688, 2002.
19. L. Roditty and U. Zwick. Dynamic approximate all-pairs shortest paths in undi-
rected graphs. In Proc. 45th IEEE Sym. Found. Comp. Sci., pages 499508, 2004.
20. M. Thorup. Fully-dynamic min-cut. Combinatorica, 27(1):91127, 2007.
21. S. Vishwanathan. Randomized online graph coloring. J. Alg., 13(4):657669, 1992.
22. D. Zuckerman. Linear degree extractors and the inapproximability of max clique
and chromatic number. Theory Comp., 3:103128, 2007.
Universal Hinge Patterns for Folding Strips
Eciently into Any Grid Polyhedron
1 Introduction
In computational origami design, the goal is generally to develop an algorithm
that, given a desired shape or property, produces a crease pattern that folds into
an origami with that shape or property. Examples include folding any shape
[9], folding approximately any shape while being watertight [10], and optimally
folding a shape whose projection is a desired metric tree [14,15]. In all of these
results, every dierent shape or tree results in a completely dierent crease pat-
tern; two shapes rarely share many (or even any) creases.
The idea of a universal hinge pattern [6] is that a nite set of hinges (possible
creases) suce to make exponentially many dierent shapes. The main result
along these lines is that an N N box-pleat grid suces to make any polycube
Work performed while at MIT.
made of O(N ) cubes [6]. The box-pleat grid is a square grid plus alternating
diagonals in the squares, also known as the tetrakis tiling. For each target
polycube, a subset of the hinges in the grid serve as the crease pattern for that
shape. Polycubes form a universal set of shapes in that they can arbitrarily
closely approximate (in the Hausdor sense) any desired volume.
The motivation for universal hinge patterns is the implementation of pro-
grammable matter material whose shape can be externally programmed. One
approach to programmable matter, developed by an MITHarvard collabora-
tion, is a self-folding sheeta sheet of material that can fold itself into several
dierent origami designs, without manipulation by a human origamist [12,1].
For practicality, the sheet must consist of a xed pattern of hinges, each with
an embedded actuator that can be programmed to fold or not. Thus for the
programmable matter to be able to form a universal set of shapes, we need a
universal hinge pattern.
The box-pleated polycube result [6], however, has some practical limitations
that prevent direct application to programmable matter. Specically, using a
sheet of area (N 2 ) to fold N cubes means that all but a (1/N ) fraction of the
surface area is wasted. Unfortunately, this reduction in surface area is necessary
for a roughly square sheet, as folding a 11N tube requires a sheet of diameter
(N ). Furthermore, a polycube made from N cubes can have surface area as
low as (N 2/3 ), resulting in further wastage of surface area in the worst case.
Given the factor-(N ) reduction in surface area, an average of (N ) layers of
material come together on the polycube surface. Indeed, the current approach
can have up to (N 2 ) layers coming together at a single point [6]. Real-world
robotic materials have signicant thickness, given the embedded actuation and
electronics, meaning that only a few overlapping layers are really practical [12].
Our results: strip folding. In this paper, we in-
troduce two new universal hinge patterns that avoid
these ineciencies, by using sheets of material that
(a)
are long only in one dimension (strips). Specically,
Fig. 1 shows the two hinge patterns: the canonical
strip is a 1 N strip with hinges at integer grid lines
and same-oriented diagonals, while the zig-zag strip
is an N -square zig-zag with hinges at just integer grid
lines. We show in Section 2 that any grid surface
any connected surface made up of unit squares on the
3D cube gridcan be folded from either strip. The (b)
strip length only needs to be a constant factor larger
than the surface area, and the number of layers is Fig. 1. Two universal
at most a constant throughout the folding. Most of hinge patterns in strips.
our analysis concerns (genus-0) grid polyhedra, that (a) A canonical strip of
is, when the surface is topologically equivalent to a length 5. (b) A zig-zag
sphere (a manifold without boundary, so that every strip of length 6. The
edge is incident to exactly two grid squares, and with- dashed lines are hinges.
out handles, unlike a torus). We show in Section 4 that a grid polyhedron of
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron 111
surface area N can be folded from a canonical strip of length 2N with at most
two layers everywhere, or from a zig-zag strip of length 4N with at most four
layers everywhere.
The improved surface eciency and reduced layering of these strip results
seem more practical for programmable matter. In addition, the panels of either
strip (the facets delineated by hinges) are connected acyclically into a path,
making them potentially easier to control. One potential drawback is that the
reduced connectivity makes for a imsier device; this issue can be mitigated by
adding tabs to the edges of the strips to make full two-dimensional contacts
across seams and thereby increase strength.
We also show in Section 5 an important practical result for our strip foldings:
under a small assumption about feature size, we give an algorithm for actually
folding the strip into the desired shape, while keeping the panels rigid (at) and
avoiding self-intersection throughout the motion. Such a rigid folding process
is important given current fabrication materials, which put exibility only in
the creases between panels [12]. An important limitation, however, is that we
assume zero thickness of the material, which would need to be avoided before
this method becomes practical.
Our approach is also related to the 1D chain robots of [7], but based on thin
material instead of thick solid chains. Most notably, working with thin material
enables us to use a few overlapping layers to make any desired surface without
scaling, and still with high eciency. Essentially, folding long thin strips of sheet
material is like a fusion between 1D chains of [7] and the square sheet folding of
[6,12,1].
Milling tours. At the core of our ecient strip foldings are ecient approxi-
mation algorithms for milling a grid polyhedron. Motivated by rapid-fabrication
CNC milling/cutting tools, milling problems are typically stated in terms of a
2D region called a pocket and a cutting tool called a cutter, with the goal
being to nd a path or tour for the cutter that covers the entire pocket. In our
situation, the pocket is the surface of the grid polyhedron, and the cutter
is a unit square constrained to move from one grid square of the surface to an
(intrinsically) adjacent grid square.
The typical goals in milling problems are to minimize the length of the tour
[3] or to minimize the number of turns in the tour [2]. Both versions are known
to be strongly NP-hard, even when the pocket is an integral orthogonal polygon
and the cutter is a unit square. We conjecture that the problem remains strongly
NP-hard when the pocket is a grid polyhedron, but this is not obvious.
In our situation, both length and number of turns are important, as both
inuence the required length of a strip to cover the surface. Thus we develop
one algorithm that simultaneously approximates both measures. Such results
have also been achieved for 2D pockets [2]; our results are the rst we know for
surfaces in 3D. Specically, we develop in Section 3 an approximation algorithm
for computing a milling tour of a given grid polyhedron, achieving both a 2-
approximation in length and an 8/3-approximation in number of turns.
112 N.M. Benbernou et al.
Fig. 2. Strip folding of individual letters typeface, AZ and 09: unfolded font (top)
and folded font (bottom), where the face incident to the bottom edge remains face-up.
2 Universality
In this section, we prove that both the canonical strip and zig-zag strip of Fig. 1,
of sucient length, can fold into any grid surface. We begin with milling tours
4
http://erikdemaine.org/fonts/strip/
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron 113
(a) (b)
Fig. 3. (a) Left and (b) right turn with a canonical strip.
which provide an abstract plan for routing the strip, and then turn to the details
of how to manipulate each type of strip.
Dual graph. Recall that a grid surface consists of one or more grid squares
that is, squares of the 3D cube gridglued edge-to-edge to form a connected
surface (ignoring vertex connections). Dene the dual graph to have a dual vertex
for each such grid square, and any two grid squares sharing an edge dene a dual
edge between the two corresponding dual vertices. Our assumption of the grid
surface being connected is equivalent to the dual graph being connected.
Milling tours. A milling tour is a (not necessarily simple) spanning cycle
in the dual graph, that is, a cycle that visits every dual vertex at least once (but
possibly more than once). Equivalently, we can think of a milling tour as the
path traced by the center of a moving square that must cover the entire surface
while remaining on the surface, and return to its starting point. Milling tours
always exist: for example, we can double a spanning tree of the dual graph to
obtain a milling tour of length less than double the given surface area.
At each grid square, we can characterize a milling tour as going straight,
turning, or U-turningintrinsically on the surfaceaccording to which two sides
of the grid square the tour enters and exits. If the sides are opposite, the tour is
straight; if the sides are incident, the tour turns; and if the sides are the same, the
tour U-turns. Intuitively, we can imagine unfolding the surface and developing
the tour into the plane, and measuring the resulting planar turn angle at the
center of the grid square.
Strip folding. To prove universality, it suces to show that a canonical strip
or zig-zag strip can follow any milling tour and thus make any grid polyhedron. In
particular, it suces to show how the strip can go straight, turn left, turn right,
and U-turn. Then, in 3D, the strip would be further folded at each traversed
edge of the grid surface, to stay on the surface. Indeed, U-turns can be viewed
as folding onto the opposite side of the same surface, and thus are intrinsically
equivalent to going straight; hence we can focus on going straight and making
left/right turns.
Canonical strip. Fig. 3 shows how a canonical strip can turn left or right;
it goes straight without any folding. Each turn adds 1 to the length of the strip,
and adds 2 layers to part of the grid square where the turn is made. Therefore
a milling tour of length L with t turns of a grid surface can be followed by a
canonical strip of length L + t. Furthermore, if the milling tour visits each grid
square at most c times, then the strip folding has at most 3c layers covering any
point of the surface.
114 N.M. Benbernou et al.
Fig. 4. Going straight with a zig-zag strip requires at most two unit squares per grid
square. Left and right crease patterns show two dierent parities along the strip.
(a) (b)
Fig. 5. Turning with a zig-zag strip has two cases because of parity. (a) Turning left
at an odd position requires three grid squares, whereas turning right requires one grid
square. (b) Turning left at an even position requires one grid square, whereas turning
right requires three grid squares.
Zig-zag strip. Fig. 4 shows how to fold a zig-zag strip in order to go straight.
In this straight portion, each square of the surface is covered by two squares of
the strip. Fig. 5 shows left and right turns. Observe that turns require either one
or three squares of the strip. Therefore a milling tour of length L with t turns
can be followed by a zig-zag strip of length at most 2L + t. Furthermore, if the
milling tour visits each grid square at most c times, then the strip folding has
at most 3c layers covering any point of the surface.
The goal in the rest of this paper is to achieve better bounds for grid poly-
hedra, using more carefully chosen milling tours.
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron 115
3.1 Bands
The basis for our approximation algorithms is the notion of bands for a grid
polyhedron P . Let xmin and xmax respectively be the minimum and maximum
x coordinates of P ; dene ymin , ymax , zmin , zmax analogously. These minima and
maxima have integer values because the vertices of P lie on the integer grid.
Dene the ith x-slab Sx (i) to be the slab bounded by parallel planes x = xmin +i
and x = xmin + i + 1, for each i {0, 1, . . . , xmax xmin 1}. The intersection of
P with the ith x-slab Sx (i) (assuming i is in the specied range) is either a single
band (i.e., a simple cycle of grid squares in that slab), or a collection of such
bands, which we refer to as x-bands. Dene y-bands and z-bands analogously.
Two bands overlap if there is a grid square contained in both bands. Each grid
square of P is contained in precisely two bands (e.g., if a grid squares outward
normal were in the +z-direction, then it would be contained in one x-band and
one y-band). Two bands B1 and B2 are adjacent if they do not overlap, and a
grid square of B1 shares an edge with a grid square of B2 . A band cover for P is
a collection of x-, y-, and z-bands that collectively cover the entire surface of P .
The size of a band cover is the number of its bands.
Proposition 2. [2, Lemma 4.9] The size of a minimum band cover of a grid
polyhedron P is a lower bound on the number of turns in any milling tour of P .
116 N.M. Benbernou et al.
Proposition 3. A vertex cover for GP induces a band cover of the same size
and vice versa.
Because the bands fall into three classes (x-, y-, and z-), with no over-
lapping bands within a single class, GP is tripartite. Hence we can use an
-approximation algorithm for vertex cover in tripartite graphs to nd an -
approximate vertex cover in GP and thus an -approximate band cover of P .
Our next goal will be to eciently tour the bands in the cover. Given a band
cover S for a grid polyhedron P , dene the band graph GS to be the subgraph
of GP induced by the subset of vertices corresponding to S. We will construct
a tour of the bands S based on a spanning tree of GS . Our rst step is thus to
show that GS is connected (Lemma 5 below). We do so by showing that adjacent
bands (as dened in Section 3.1) are in the same connected component of GS ,
using the following lemma of Genc [11]:
Lemma 4. [11]5 For any band B in a grid polyhedron P , let Nb be the bands of
P overlapping B. (Equivalently, Nb is the set of neighbors of B in GP ). Then
the subgraph of GP induced by NB is connected.
Now we can present our algorithm for transforming a band cover into an ecient
milling tour.
We now state some additional properties of any milling tour produced by the
approximation algorithm of Theorem 6, which will be useful for later applications
to strip folding in Section 4.
5
Genc [11] uses somewhat dierent terminology to state this lemma: straight cycles
in the dual graph are our bands, and crossing is our overlapping. The induced
subgraph is also dened directly, instead of as an induced subgraph of GP .
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron 117
The algorithm described above is polynomial in the surface area N of the grid
polyhedron, or equivalently, polynomial in the number of unit cubes making
up the polyomino solid. For our application to strip folding, this is polynomial
in the length of the strip, and thus sucient for most purposes. On the other
hand, polyhedra are often encoded as a collection of n vertices and faces, with
faces possibly much larger than a unit square. In this case, the algorithm runs
in pseudopolynomial time.
Although we do not detail the approach here, our algorithm can be modied
to run in polynomial time. To achieve this result, we can no longer aord to deal
with unit bands directly, because their number is polynomially related to the
number N of grid squares, not the number n of vertices. To achieve polynomial
time in n, we concisely encode the output milling tour using fat bands rather
than unit bands, which can then be easily decoded into a tour of unit bands. By
making each band as wide as possible, their number is polynomially related to
n instead of N . Details of an O(n3 log n)-time milling approximation algorithm
(with the same approximation bounds as above) can be found in [4].
In this section, we show how we can use the milling tours from Section 3 to fold a
canonical strip or zig-zag strip eciently into a given (genus-0) grid polyhedron.
For both strip types, dene the length of a strip to be the number of grid squares
it contains; refer to Fig. 1. For a strip folding of a polyhedron P , dene the
number of layers covering a point q on P to be the number of interior points of
the strip that map to q in the folding, excluding crease points, that is, points lying
on a hinge that gets folded by a nonzero angle. (This denition may undercount
the number of layers along one-dimensional creases, but counts correctly at the
remaining two-dimensional subset of P .) We will give bounds on the length of
the strip and also on the maximum number of layers of the strip covering any
point of the polyhedron.
118 N.M. Benbernou et al.
For zig-zag strips, we instead use Properties (1) and (2) of Proposition 7:
Theorem 9. Let P be a grid polyhedron, and let N be the number of grid squares
of P . Then P can be covered by a folding of a zig-zag strip of length 4N , and
with at most four layers covering any point of P .
By coloring the two sides of the zig-zag strip dierently, we can also bicolor
the surface of P in any pattern we wish, as long as each grid square is assigned
a uniform color. We do not prove this result formally here, but mention that
the bounds in length would become somewhat worse, and the rigid motions
presented in Section 5 do not work in this setting.
So far we have focused on just specifying a nal folded state for the strip, and
ignored the issue of how to continuously move the strip into that folded state.
In this section, we show how to achieve this using a rigid folding motion, that is,
a continuous motion that keeps all polygonal faces between hinges rigid/planar,
bending only at the hinges, and avoids collisions throughout the motion. Rigid
folding motions are important for applications to real-world programmable mat-
ter made out of sti material except at the hinges. Our approach may still suer
from practical issues, as it requires a large (temporary) accumulation of many
layers in an accordion form.
We prove that, if the grid polyhedron P has fea-
ture size at least 2, then we can construct a rigid mo-
tion of the strip folding without collision. (By feature (a) (b)
size at least 2, we mean that every exterior voxel of P Fig. 7. Accordion for (a)
is contained in some empty 2 2 2 box.) If the grid canonical strip and (b)
polyhedron we wish to fold has feature size 1, then zig-zag strip, with hinges
one solution is to scale the polyhedron by a factor drawn thick for increased
of 2, and then the results here apply. visibility.
Our approach is to keep the yet-unused portion of the strip folded up into an
accordion and then to unfold only what is needed for the current move: straight,
left, or right. Fig. 7 shows the accordion state for the canonical strip and for
the zig-zag strip. We will perform the strip folding in such a way that the strip
never penetrates the interior of the polyhedron P , and it never weaves under
Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron 119
(a)
(b)
Fig. 8. Canonical strip, face-up cases. (a) Straight. (b) Turn where e23 is at.
previous portions of the strip. Thus, we could wrap the strip around P s surface
even if P s interior were already a lled solid. This restriction helps us think
about folding the strip locally, because some of P s surface may have already
been folded (and it thus should not be penetrated) by earlier parts of the strip.
It suces to show, regardless of the local geometry of the polyhedron at the
grid square where the milling tour either goes straight or turns, and regardless of
whether the accordion faces up or down relative to the grid square it is covering,
that we can maneuver the accordion in a way that allows us to unroll as many
squares as necessary to perform the milling-tour move. Fig. 8 shows two key
cases for unrolling part of the accordion of a canonical strip. See [5] for details.
Acknowledgments. We thank ByoungKwon An and Daniela Rus for several
helpful discussions about programmable matter that motivated this work.
References
Fig. 9. An example of joining together a few letters from our typeface in Fig. 2. Un-
folding (bottom) not to scale with folding (top).
An optimal XP algorithm for Hamiltonian Cycle
on graphs of bounded clique-width
1
Universite Clermont Auvergne, LIMOS, CNRS, Aubiere, France
2
Logic and Semantics, TU Berlin, Berlin, Germany
[email protected], [email protected], [email protected]
1 Introduction
Tree-width is one of the graph width parameters that plays an important role
in graph algorithms. Various problems which are NP-hard on general graphs,
have been shown to be solvable in polynomial time on graphs of bounded tree-
width [1,2]. A celebrated algorithmic meta-theorem by Courcelle [3] states that
every graph property expressible in monadic second-order logic which allows
B. Bergougnoux and M.M. Kante are supported by French Agency for Research
under the GraphEN project (ANR-15-CE-0009). O. Kwon is supported by the Eu-
ropean Research Council (ERC) under the European Unions Horizon 2020 research
and innovation programme (ERC consolidator grant DISTRUCT, agreement No.
648527).
quantications over edge and vertex sets (MSO2 ) can be decided in linear time
on graphs of bounded tree-width. Minimum Dominating Set, q-Coloring,
and Hamiltonian Cycle problems are such graph problems.
Courcelle and Olariu [5] dened the notion of clique-width of graphs, whose
modeling power is strictly stronger than tree-width. The motivation of clique-
width came from the observation that many algorithmic problems are tractable
on classes of graphs that can be recursively decomposed along vertex partitions
(A, B) where the number of neighbourhood types between A and B is small. We
formally dene clique-width in Section 2. Courcelle, Makowsky, and Rotics [4]
extended the meta-theorem on graphs of bounded tree-width [3] to graphs of
bounded clique-width, at a cost of a smaller set of problems, namely, the class of
problems expressible in MSO1 , which allows quantications on vertex sets only.
Some of the known examples of graph problems that are MSO2 -denable, but not
MSO1 -denable are Max-Cut, Edge Dominating Set, and Hamiltonian
Cycle problems.
A natural question is whether such problems allow an algorithm with running
time f (k) nO(1) for some function f , when a clique-width k-expression of an
n-vertex input graph is given. This question has been carefully answered by
Fomin et al. [8,9]. In particular, they showed that for Max-Cut and Edge
Dominating Set, there is no f (k) no(k) -time algorithm unless the Exponential
Time Hypothesis (ETH) fails, and proposed for both problems algorithms with
running time nO(k) . They proved that Hamiltonian Cycle also cannot be
solved in time f (k) no(k) , unless ETH fails, but left open the question of nding
an algorithm running in time nO(k) . Until now, the best algorithm is the one by
2
Espelage, Gurski, and Wanke [7] which runs in time nO(k ) .
Our Contribution and Approach. In this paper, we prove that Hamiltonian
Cycle can be solved in time nO(k) , thereby resolving the open problem in [9].
A Hamiltonian cycle in a graph is a cycle containing all vertices of the graph.
The Hamiltonian Cycle problem asks whether given a graph G, G contains
a Hamiltonian cycle or not.
part only depends on the labels, it is sucient to store for each pair of labels
(i, j), the number of paths whose end vertices are labeled by i and j. As the
2
number of paths of a path-partition is bounded by n, there are at most nO(k )
possibilities. This is the basic idea of the XP algorithm developed by Espelage,
Gurski, and Wanke [7].
The essential idea of our algorithm is to introduce an equivalence relation
between two path-partitions. Given a path-partition P that is arestriction of
a Hamiltonian cycle C, we consider the maximal paths in C P P E(P ) as
another path-partition Q. As depicted in Figure 1, we can construct a multigraph
associated with P and Q on the vertex set {v1 , . . . , vk }, by adding a red edge
vi vj (an undashed edge) if there is a path in P with end vertices labeled by i and
j, and by adding a blue edge vi vj (a dashed edge) if there is a path in Q with end
vertices labeled by i and j. A crucial observation is that this multigraph admits
an Eulerian trail where red edges and blue edges are alternatively used. This is
indeed a characterisation of the fact that two such path-partitions can be joined
into a Hamiltonian cycle. To determine the existence of such an Eulerian trail,
it is sucient to know the degree of each vertex and the connected components
of the corresponding multigraphs of the two path-partitions. This motivates
an equivalence relation between path-partitions. As a byproduct, we can keep
in each equivalence class a representative and since the number of equivalence
classes is bounded by 2k log2 k nk , we can turn the naive algorithm into an nO(k) -
time algorithm (there are at most 2k log2 k partitions of k-elements set). A more
detailed explanation of our algorithm is provided in Section 3.
1
v1
2
v2
3
v3
4
v4
2 Preliminaries
The size of a set V is denoted by |V |, and we write [V ]2 to denote the set of
all subsets of V of size 2. We denote by N the set of non-negative integers. We
essentially follow [6] for our graph terminology, but we deal only with nite
graphs. The vertex set of a graph G is denoted by V (G) and its edge set by
E(G) [V (G)]2 . We write xy to denote an edge {x, y}. Let G be a graph.
For X V (G), we denote by G[X] the subgraph of G induced by X, and for
F E(G), we write G F for the subgraph (V (G), E(G) \ F ). The degree of a
vertex x, denoted by degG (x), is the number of edges incident with x. A cut-edge
in a connected graph is an edge e such that G {e} is disconnected. For two
sets A, B V (G), A is complete to B if for every v A and w B, vw E(G).
A graph is non-trivial if it contains an edge, otherwise it is said trivial. A
walk of a graph is an alternating sequence of vertices and edges, starting and
ending at some vertices, where for every consecutive pair of a vertex x and an
edge e, x is incident with e. A trail of a graph is a walk where each edge is used
at most once. A trail is closed if its rst and last vertices are the same.
A multigraph is essentially a graph, but we allow two edges to be incident
with the same set of vertices. Formally, a multigraph G is a pair (V (G), E(G))
of disjoint sets, also called sets of vertices and edges, respectively, together with
a map multG : E(G) V (G) [V (G)]2 , which maps every edge to one or two
vertices, still called its end vertices. Note that we admit loops in multigraphs,
while we do not in our denition of graphs. If there is e E(G) such that
multG (e) = {x, y} (or multG (e) = {x}), we use the term multiedge to refer to
{x, y} (or {x}). The degree of a vertex x in a multigraph G, is dened analo-
gously as in graphs, except that each loop is counted twice, and similarly for
other notions. If there are exactly k edges e such that multG (e) = {x, y} (or
multG (e) = {x}), then we denote these distinct edges by {x, y}1 , . . . , {x, y}k (or
{x}1 , . . . , {x}k ); if k = 1, then for the sake of clarity, we write {x, y} (or {x})
instead of {x, y}1 (or {x}1 ).
An Eulerian trail in a multigraph is a closed trail containing all edges.
Clique-width. A graph is k-labeled if there is a labeling function f : V (G)
{1, . . . , k}, and we call f (v) the label of v. For a k-labeled graph G, we simply
call the set of all vertices with label i as the label class i of G.
The clique-width of a graph G is the minimum number of labels needed to
construct G using the following four operations:
1. Creation of a new vertex v with label i (denoted by i(v)).
2. Disjoint union of two labeled graphs G and H (denoted by G H).
3. Joining by an edge each vertex with label i to each vertex with label j (i = j,
denoted by i,j ).
4. Renaming label i to j (denoted by ij ).
Such an expression is called a clique-width k-expression or simply a k-expression
if it uses at most k distinct labels. We can naturally represent this expression
as a tree-structure. Such trees are known as syntactic trees associated with k-
expressions.
An optimal XP algorithm for Hamiltonian Cycle on graphs of bounded clique-width 125
Suppose there are two such path-partitions P1 and P2 where there is a cycle
C1 satisfying the conditions of Proposition 1. Let Q be the subpaths of C1 con-
necting two consecutive paths in P1 . See Figure 1 for an illustration. Note that
if a path in Q is an edge, then it is an edge between two label classes and contained
in E(G) \ E(H). By the property (2), these two label classes are complete in G.
We label each end vertex of a path in Q as the label of H, We consider the
auxiliary multigraph Aux(P1 ) and the auxiliary multigraph Aux(Q) by consid-
ering Q as a path-partition of the underlying graph on QQ V (Q). We obtain
a multigraph F from the disjoint union of Aux(P1 ) and Aux(Q) by identifying
each vi . Following the Hamiltonian cycle C, one easily checks that there is an
Eulerian trail which alternates between edges in Aux(P1 ) and edges in Aux(Q).
We will prove that if we replace Aux(P1 ) with Aux(P2 ) in F , then the
new graph also admits an Eulerian trail, because of the given conditions in
Proposition 1. To see this, we observe the following, which is a strengthening
of Eulers theorem on Eulerian trails. It is well known that a connected graph
contains an Eulerian trail if and only if every vertex has even degree. Moreover,
when edges are colored by two colors, say red and blue, and each vertex is incident
with the same number of edges for both colors, then we can nd an Eulerian
trail where the two colors appear alternatively. We call such an Eulerian trail a
red-blue alternating Eulerian trail. For a multigraph G colored by red and blue
and v V (G), let rdegG (v) denote the number of red edges incident with v, and
let bdegG (v) denote the number of blue edges incident with v.
Lemma 1 (). Let G be a connected multigraph whose edges are colored by red
and blue. Then G has a red-blue alternating Eulerian trail if and only if for every
vertex v, bdegG (v) = rdegG (v).
Indeed, when we replace Aux(P1 ) with Aux(P2 ) in F , the set of components
does not change (thus consists of one non-trivial component), and each vertex is
incident with same number of red and blue edges, and by Lemma 1, the resulting
graph has an Eulerian trail. We will show that one can construct a Hamiltonian
cycle of G from paths of P2 using the properties (1) and (2).
Motivated by Proposition 1, we dene in Section 4 an equivalence relation
between two sets of multigraphs on the same vertex set {v1 , . . . , vk }. We further
dene operations on those multigraphs, corresponding to procedures of updating
path-partitions, and prove that the equivalence between two sets is preserved
under such operations. These results will form the skeleton of the main algorithm.
Proof (Proof of Theorem 1). We assume that G has at least 3 vertices, otherwise
we can automatically say it is a No-instance. Since every k-expression can be
transformed into an irredundant k-expression in linear time, we may assume that
G is given with an irredundant k-expression. Let be the given irredundant k-
expression dening G, and T be the syntactic tree of . For every node t of T ,
let Gt be the subgraph of G dened at node t, and for each i {1, . . . , k}, let
Gt [i] be the subgraph of Gt induced by the vertices with label i.
For each node t and each vector (a1 , . . . , ak ) {0, 1, . . . , n}k, let c[t, (a1 , . . . , ak )]
be the set of all multigraphs F on the vertex set {v1 , . . . , vk } where
F = Aux(P) for some k-labeled path-partition P of Gt ,
for each i {1, . . . , k}, ai is the degree of vi in F .
Instead of computing the whole set c[t, (a1 , . . . , ak )], we will compute a subset
r[t, (a1 , . . . , ak )] of c[t, (a1 , . . . , ak )] of size 2O(k log k) such that r[t, (a1 , . . . , ak )]
c[t, (a1 , . . . , ak )].
We explain how to decide whether G has a Hamiltonian cycle. Let troot be
the root node of T , and let tlastjoin be the node taking the disjoint union of two
130 B. Bergougnoux et al.
graphs and closest to the root node. We can observe that G has a Hamiltonian
cycle if and only if there are some node t between troot and tlastjoin with child
t and a path-partition P of Gt such that t is a join node labeled by i,j ,
and degAux(P) (vi ) = degAux(P) (vj ) > 0 and degAux(P) (vi ) = 0 for all i
{1, . . . , k} \ {i, j}. This is equivalent to that c[t , (a1 , . . . , ak )] = for some vector
(a1 , . . . , ak ) where ai = aj > 0 and ai = 0 for all i {1, . . . , k} \ {i, j}.
Therefore, if there is a Hamiltonian cycle, then r[t , (a1 , . . . , ak )] = for such a
tuple of t, t , and (a1 , . . . , ak ), and we can correctly say that G has a Hamiltonian
cycle, and otherwise, there are no such tuples, and we can correctly say that G
has no Hamiltonian cycles.
Now, we explain how to recursively generate r[t, (a1 , . . . , ak )].
c[t,(a1 , . . . , ak )]
:= c[t1 , (a11 , . . . , a1k )]
c[t2 , (a21 , . . . , a2k )].
(a11 ,...,a1k )+(a21 ,...,a2k )=(a1 ,...,ak )
We assign
r[t, (a1 , . . . , ak )]
:= reduce r[t1 , (a11 , . . . , a1k )]
r[t2 , (a21 , . . . , a2k )] .
(a11 ,...,a1k )+(a21 ,...,a2k )=(a1 ,...,ak )
3. (Join node with the child t such that each vertex with label i is joined to
each vertex with label j)
Note that every path-partition of Gt is obtained from a path-partition of
Gt by adding some edges between end vertices of label i and end vertices of
label j. We can observe that when we add an edge between an end vertex
v of a path P1 with label i, and an end vertex w of a path P2 with label j,
these two paths P1 and P2 will be unied into a path whose end vertices are
end vertices of P1 and P2 other than v and w. Thus, it corresponds to the
operation +(i, j) on auxiliary multigraphs. We observe that
c[t,(a1 , . . . , ak )] := (c[t , (a1 , . . . , ak )] + (i, j)).
ai ai =aj aj =0
ax =ax for x = i, j
An optimal XP algorithm for Hamiltonian Cycle on graphs of bounded clique-width 131
We take all possible vectors (a1 , . . . , ak ) where ai ai = aj aj 0, and
for all t {1, . . . , k} \ {i, j}, at = at . Assume = ai ai . For each
{0, 1, . . . , n}, we assign
r := reduce( reduce(reduce(r[t , (a1 , . . . , ak )] + (i, j)) + (i, j)) + (i, j)),
4. (Renaming node with a child t such that the label of each vertex with label
i is changed to j)
Every path-partition of Gt is also a path-partition of Gt , and vice versa.
Since just labelings of vertices are changed, we can observe that if ai = 0,
then c[t, (a1 , . . . , ak )] is the empty set, and otherwise, we have
c[t,(a1 , . . . , ak )] := c[t , (a1 , . . . , ak )]|ij .
ax =ax for all x = i, j
ai +aj =aj
If ai = 0, then we assign the empty set to r[t, (a1 , . . . , ak )], and otherwise,
we assign
r[t,(a1 , . . . , ak )] := reduce r[t , (a1 , . . . , ak )]|ij .
ax =ax for all x = i, j
ai +aj =aj
One can prove by induction that r[t, (a1 , . . . , ak )] c[t, (a1 , . . . , ak )] for each t
and (a1 , . . . , ak ). Therefore, we can correctly decide whether G has a Hamiltonian
cycle or not using sets r[t, (a1 , . . . , ak )].
Running time. Each constructed set r[t, (a1 , . . . , ak )] consists of at most 2O(k log k)
graphs, as we keep at most one graph for each partition of {v1 , . . . , vk } after the
reduce operation. For the node taking the disjoint union of two graphs, for a xed
vector (a1 , . . . , ak ), there are nO(k) ways to take two vectors A1 and A2 such that
A1 + A2 = (a1 , . . . , ak ). So, we can update r[, ] in time nO(k) 2O(k log k) . For the
node joining edges between two classes, the value can be taken from 0 to n.
Since each operation +(i, j) take k 2 2O(k log k) time, we can update r[, ] in time
n2 2O(k log k) . Clearly, we can update r[, ] in time n 2O(k log k) for the relabeling
nodes. Therefore, we can solve Hamiltonian Cycle for G in time nO(k) .
6 More applications
Let q be a positive integer. The q-Cycle Covering problem asks for a given
graph G whether there is a set of at most q pairwise vertex-disjoint cycles in
132 B. Bergougnoux et al.
References
1. Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems re-
stricted to partial k-trees. Discrete Appl. Math. 23, 1124 (1989)
2. Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor.
Comput. Sci. 209, 145 (1998)
3. Courcelle, B.: The monadic second-order logic of graphs I: Recognizable sets of nite
graphs. Information and Computation 85, 1275 (1990)
4. Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization prob-
lems on graphs of bounded clique width. Theor. Comput. Sci. 33, 125150 (2000)
5. Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl.
Math. 101(1-3), 77114 (2000)
6. Diestel, R.: Graph Theory. No. 173 in Graduate Texts in Mathematics, Springer,
third edn. (2005)
7. Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on
clique-width bounded graphs in polynomial time. In: Graph-theoretic concepts in
computer science (Boltenhagen, 2001), Lecture Notes in Comput. Sci., vol. 2204,
pp. 117128. Springer, Berlin (2001)
8. Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-
width parameterizations. SIAM J. Comput. 39(5), 19411956 (2010)
9. Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower
bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541
1563 (2014)
Improved Algorithms for Computing
k-Sink on Dynamic Flow Path Networks
1 Introduction
Ford and Fulkerson [5] introduced the concept of dynamic ow which models
movement of commodities in a network. In this model, each vertex is assigned
some initial amount of supply, each edge has a capacity, which limits the rate
of commodity ow into it per unit time, and the transit time to traverse it.
One variant of the dynamic ow problem is the quickest transshipment problem,
where the source vertices have specied supplies and sink vertices have specied
demands. The problem is to send exactly the right amount of commodity out of
sources into sinks in minimum overall time. Hoppe and Tardos [12] provided a
polynomial time algorithm for this problem in the case where the transit times
are integral. However, the complexity of their algorithm is very high. Finding a
practical polynomial time solution to this problem is still open. The reader is
referred to a recent paper by Skutella [18] on dynamic ows.
This paper discusses a related problem, called the evacuation problem [8,
14], in which the supplies (i.e., evacuees) are discrete, and the sinks and their
demands are not specied. In fact, the locations of the sinks are the output of the
problem. Many disasters, such as earthquakes, nuclear plant accidents, volcanic
Partially supported by a Discovery Grant from NSERC of Canada
Partially supported by Hong Kong RGC GRF grant 16208415
Supported by JSPS KAKENHI Grant-in-Aid for Young Scientists (B) (17K12641)
Supported by JST CREST (JPMJCR1402)
eruptions, ooding, have struck in recent years in many parts of the world, and
it is recognized that orderly evacuation planning is urgently needed.
Mamada et al. [15] solved the 1-sink problem for the dynamic ow tree net-
works in O(n log2 n) time under the condition that only a vertex can be a sink,
where n is the number of vertices. When edge capacities are uniform, we have
presented O(n log n) time algorithms with a more relaxed condition that the
sink can be on an edge, as well as on a vertex [3, 10]. Dealing with congestion is
non-trivial even in path networks. On dynamic ow path networks with uniform
edge capacities, it is straightforward to compute the 1-sink in linear time, as
shown by Cheng et al. [4]. Arumugam et al. [1] showed that the k-sink problem
for dynamic ow path networks can be solved in O(kn log2 n) time, and when
the edge capacities are uniform Higashikawa et al. [11] showed that it can be
solved in O(kn) time.
In this paper we present two algorithms for the k-sink problem on dynamic
ow path networks with general edge capacities. A path network can model an
airplane aisle, a hall way in a building, a street, a highway, etc., to name a few.
Unlike the previous algorithm for the k-sink problem [1] which uses dynamic
programming, our algorithms adopt Megiddos parametric search [16] and the
sorted matrices introduced by Frederickson and Johnson [6, 7]. Together, they
outperform all other known algorithms, and they are the rst sub-quadratic
algorithms for any value of k. These improvements were made possible by our
method of merging evacuation times of subpaths stored in a hierarchical data
structure. We also present two algorithms for the dynamic ow path networks
with uniform edge capacities.
This paper is organized as follows. In the next section, we dene our model
and the terms that are used throughout the paper. Sec. 3 introduces a new
data structure, named the capacities and upper envelopes tree, which plays a
central role in the rest of the paper. In Sec. 4 we identify two important tasks
that form building blocks of our algorithms, and also discuss a feasibility test.
Sec. 5 presents several algorithms for uniform and general edge capacities. Fi-
nally, Sec. 6 concludes the paper.
Improved Algorithms for Computing k -Sink on Dynamic Flow Path Networks 135
2 Preliminaries
2.1 Denitions
Let P = (V, E) be a path network, whose vertices v1 , v2 , . . . , vn are arranged from
left to right in this order. For i = 1, 2, . . . , n, vertex vi has an integral weight
wi (> 0), representing the number of evacuees, and each edge ei = (vi , vi+1 ) has
a xed non-negative length li and an integral capacity ci , which is the upper limit
on the number of evacuees who can enter an edge per unit time. We assume that
a sink has innite capacity, so that the evacuees coming from the left and right
of a sink do not interfere with each other. An evacuation starts at the same time
from all the vertices, and all the evacuees from a vertex evacuate to the same
sink. This is called conuent ow in the parlance of the network ow theory.
This constraint is desirable in evacuation in order to avoid confusion among the
evacuees at a vertex as to which way they should move.
By x P , we mean that point x lies on either an edge or a vertex of P . For
two points a, b P , a b or b a means that a lies to the left of b. Let d(a, b)
denote the distance (sum of the edge lengths) between a and b. If a and/or b lies
on an edge, we use the prorated distance. The transit time for a unit distance
is denoted by , so that it takes d(a, b) time to travel from a to b, and is
independent of the edge. Let c(a, b) denote the minimum capacity of the edges
on the subpath of P between a and b. The point that is arbitrarily close to vi
on its left (resp. right) side is denoted by vi (resp. vi+ ). Let P [a, b] denote the
subpath of P between a and b satisfying a b. If a, b or both are excluded, we
denote them by P (a, b], P [a, b) or P (a, b), respectively. Let V [a, b] (resp. V (a, b],
V [a, b) or V (a, b)) denotes the set of vertices on P [a, b] (resp. P (a, b], P [a, b) or
P (a, b)). We introduce a weight array W [], dened by
W [i] wj , for i = 1, 2, . . . , n, (1)
vj V [v1 ,vi ]
8 14 5 10 7 15 8 12 7 3 10
weights
lengths 3 2 4 3 2 3 2 4 2 1 4
v1 v2 v3 v4 v5 v6 v7 v8 v9 x v10 v11
capacities
5 3 4 2 6 5 3 4 5 1
respectively. For convenience we sometimes refer to the rst (resp. second) term
in the righthand side of (2) and (3) as the distance time (resp. weight time).
Note that the distance time is linear in the distance to x. Consider an arbitrary
subpath P [vi , vj ], where i j.
Fig. 1 shows an example, where vertices v1 , v2 , v3 , . . . (represented by black
circles) have weights 8, 14, 5, . . ., and edges e1 , e2 , e3 , . . . have lengths 3, 2, 4, . . .
and capacities 5, 3, 4, . . . Point x is located on e9 = (v9 , v10 ) so that d(v9 , x) = 2
(represented by a white circle). Assuming = 1, let us compute the L-time to
x of vertex v5 on P [v2 , v7 ]. From d(v5 , x) = 13, W [v2 , v5 ] = 36 and c(v5 , x) = 3,
[2,7]
we obtain L (x, v5 ) = 25.
To be more precise, the weight time should be W [vi , vp ]/c(vp , x) and
W [vp , vj ]/c(x, vp ) in (2) and (3), respectively, since the evacuees are discrete
entities. Although only small modications are necessary to get exact solutions
as shown in [4], we use (2) and (3) for simplicity.
Lemma 1. [9] Let s be the sink for a subpath P [vi , vj ] of a path network P . The
evacuation completion time to s (vi vh s vh+1 vj ) for the evacuees on
P [vi , vj ] is given by
[i,h] [h+1,j]
[i,j] (s) max max {L (s, v)}, max {R (s, v )} . (4)
vV [vi ,s) v V (s,vj ]
[i,j]
Referring to (2) and (3), the vertex vp V [vi , vj ] that maximizes L (vj+ , vp )
[i,j]
(resp. R (vi , vp )) is called the L-critical vertex (resp. R-critical vertex) of
[i,j] [i,j]
P [vi , vj ], and is denoted by cL (resp. cR ). Note that (vj+ , vp ) (resp. (vi , vp ))
is used instead of (vj , vp ) (resp. (vi , vp )), and that we have d(vp , vj+ ) = d(vp , vj )
and c(vp , vj+ ) = min{c(vp , vj ), cj } (resp. d(vi , vp ) = d(vi , vp ) and c(vi , vp ) =
min{c(vi , vp ), ci1 }).
Using the example in Fig. 1 again, let us nd the L-critical vertex of P [v2 , v7 ].
[2,7] [2,7]
We rst compute L (v7+ , vp ) for p = 2, . . . , 7: L (v7+ , v2 ) = 14 + 14/2 = 21,
[2,7] + [2,7] + [2,7]
L (v7 , v3 ) = 12 + 19/2 = 21.5, L (v7 , v4 ) = 8 + 29/2 = 22.5, L (v7+ , v5 ) =
[2,7] [2,7]
5+36/3 = 17, L (v7+ , v6 ) = 3+51/3 = 20, and L (v7+ , v7 ) = 0+59/3 19.7.
[2,7]
Comparing these values, we obtain cL = v4 .
Improved Algorithms for Computing k -Sink on Dynamic Flow Path Networks 137
3 Data structures
A problem instance is said to be t-feasible if there are k sinks such that every
evacuee can reach a sink within time t. In our algorithms, we want to perform
t-feasibility tests for many dierent values of completion time t. Therefore, it is
worthwhile to spend some time during preprocessing to construct data structures
which facilitate these tests.
(vi , ) (vj , )
vi vl(u) vr(u) vj
Fig. 2. Illustration of a part of CUE tree T . The small gray disks represent nodes of
N [vi , vj ] and dashed circles enclose subpaths in P[vi , vj ].
u spans subpath P [vl(u) , vr(u) ]. At node u, we store l(u), r(u) and the capacity
c(vl(u) , vr(u) ) among others. This information at every node can be computed
bottom up in O(n) time by performing heap-like operations.
For two nodes u, u of T , let (u, u ) denote the path from u to u along
edges of T . Suppose that for an index pair (i, j) with 1 i j n, node is
5
We use the term node here to distinguish it from the vertices on the path. A
vertex, being a leaf of T , is considered a node, but an interior node of T is not a
vertex.
138 B. Bhattacharya et al.
[i,j]
In order to determine cL for a given pair (i, j), we need to compute
To facilitate such a computation for an arbitrary pair (i, j), at each node u,
we precompute and store two upper envelope functions associated with sub-
path P [vl(u) , vr(u) ]. Then for u N [vi , vj ] that spans vp , we have W [vi , vp ] =
W [vi , vl(u)1 ]+W [vl(u) , vp ] and c(vp , vj+1 ) = min{c(vp , vr(u)+1 ), c(vr(u)+1 , vj+1 )}.
Since (i, j), hence W [vi , vl(u)1 ] and c(vr(u)+1 , vj+1 ), is not known during pre-
processing, we replace these values with variables W and c, respectively, and
express the two upper envelopes stored at u as functions of W = W [vi , vl(u)1 ]
and c = c(vr(u)+1 , vj+1 ), respectively. We can now break (5) down into a number
of formulea, one for each u N [vi , vj ], which is given by
!
max d(vp , vr(u) ) + (W + W [vl(u) , vp ])/ min{c(vp , vr(u)+1 ), c} . (6)
vp V [vl(u) ,vr(u) ]
Using the concrete values of W and c, we can evaluate (5) by nding the maxi-
mum of the |N [vi , vj ]| = O(log n) values, computed by (6).
Note that c(vp , vr(u)+1 ) gets smaller as vp moves to the left. From (7) it is seen
u
that L,1 (W ) is the upper envelope of linear functions of W and each coecient
u
of W is positive, which means that L,1 (W ) is piecewise linear, continuous, and
increasing in W . Thus it can be encoded as a sequence of bending points. In
Case (ii), we have from (6)
u
!
L,2 (c) = max d(vp , vr(u) ) + W [vl(u) , vp ]/c . (9)
vp V [vl(u) ,vr(u) ]
Note that (9) was obtained from (6) by removing the term W/c, which does
u
not depend on vp . If we plot L,2 (c) vs. (1/c) as a graph, it is also piecewise
linear, continuous, and increasing in (1/c), and can be encoded as a sequence of
bending points.
Improved Algorithms for Computing k -Sink on Dynamic Flow Path Networks 139
u u
At node u we store both L,1 (W ) and L,2 (c) in encoded form with bending
points, which can be computed in O(r(u) l(u)) time. Similarly, in order to
[i,j]
determine cR for an arbitrary pair (i, j), we store two functions which are
u u u u
symmetric to L,1 (W ) and L,2 (c), respectively, named R,1 (W ) and R,2 (c),
in linear time. We can now prove the following lemma.
Lemma 2. Given a dynamic ow path network with n vertices, CUE tree T
with associated data can be constructed in O(n log n) time and O(n log n) space.
update cmin to the L.H.S. of (10), and u to up . If u = u and (10) holds, such
q does not exist. If (10) stops holding at some node u , then update u to ul .
While
min{cmin , c(vl(ur ) , vr(ur ) ), cr(ur )+1 } c, (11)
update cmin to the L.H.S. of (11) and u to ur . If (11) stops holding at some node
u , then update u to ur . This way we will eventually reach vq , if it exists, in
O(log n) time. If q exists, we partition P [vl(u) , vr(u) ] into two subpaths P [vl(u) , vq ]
and P [vq+1 , vr(u) ]. Letting V1 = V [vl(u) , vq ], V2 = V [vq+1 , vr(u) ], and W = W [vi ,
vl(u)1 ], we dene
u [l(u),r(u)] +
L,1 (W ) = max L (vr(u) , vp ) + W/c(vp , vr(u)+1 ) , (12)
vp V1
u
!
L,2 (c) = max d(vp , vr(u) ) + W [vl(u) , vp ]/c . (13)
vp V2
(b) If v1 V2 , we have
u
L,1 (W ) L,2
u
(c) + W/c. (16)
4 Building blocks
There are two useful tasks that we can call upon repeatedly. Given the starting
vertex va , the rst task is to nd the rightmost vertex vd such that all the
evacuees on V [va , vd ] can evacuate to a sink within time t. The second task is to
nd the cost of the 1-sink on a given subpath P [vi , vj ]. To perform these tasks,
we start with more basic procedures.
Algorithm 1 1-Sink(t, va )
1. Compute an integer b by binary search over h with a h n such that
[a,b] [a,b+1]
the L-time of cL to vb+ does not exceed t but the L-time of cL +
to vb+1
exceeds t.
[a,b] [a,b]
2. Solve L (vb+ , cL ) + x = t, and place a sink s (vb , vb+1 ] satisfying
d(vb , s) = x.
3. If s (vb , vb+1 ), set c to b + 1. If s = vb+1 , set c to b + 2. Compute an integer
[c,d]
d by binary search over h with c h n such that the R-time of cR to s
[c,d+1]
does not exceed t but the R-time of cR to s exceeds t.
[c,h]
the R-time of cR to s for h = c, c + 1, . . . one by one, instead of binary search.
Then, the computations of L-time and R-time are invoked at most n times during
a t-feasibility test. Since each computation of L-time or R-time takes O(log2 n)
time by Lemma 4, the total time is O(n log2 n) in this way.
5 Optimization
5.1 Parametric search approach
Lemma 12. [1] If t-feasibility test can be tested in (t) time, then the k-sink
can be found in O(k(t) log n) time, excluding the preprocessing time.
By Lemma 2 it takes O(n log n) time to construct T with weight and capacity
data, and (t) = O(k log3 n) by Lemma 7. Lemma 12 thus implies
Theorem 1. Given a dynamic ow path network with n vertices, we can nd
an optimal k-sink in O(n log n + k 2 log4 n) time.
Applying Megiddos main theorem in [16] to Lemma 11, we obtain
Theorem 2. Given a dynamic ow path network with n vertices and uniform
edge capacities, we can nd an optimal k-sink in O(n + k 2 log2 n) time.
Improved Algorithms for Computing k -Sink on Dynamic Flow Path Networks 143
Let OP T (l, r) denote the evacuation time for the optimal 1-sink on subpath
P [vl , vr ]. Dene an n n matrix A whose entry (i, j) entry is given by
OPT (n i + 1, j) if n i + 1 j
A[i, j] = (17)
0 otherwise.
It is clear that matrix A includes OPT (l, r) for every pair of integers (l, r)
such that 1 l r n. There exists a pair (l, r) such that OPT (l, r) is
the evacuation time for the optimal k-sink on the whole path. Then the k-sink
location problem can be formulated as: Find the smallest A[i, j] such that the
given problem instance is A[i, j]-feasible. Note that we do not actually compute
all the elements of A[ ], but element A[i, j] is computed on demand as needed.
A matrix is called a sorted matrix if each row and column of it is sorted in the
nondecreasing order. In [6, 7], Frederickson and Johnson show how to search for
an element in a sorted matrix. The following lemma is implicit in their papers.
Lemma 13. Suppose that A[i, j] can be computed in g(n) time, and feasibility
can be tested in f (n) time with h(n) preprocessing time. Then we can solve the
k-sink problem in O(h(n) + ng(n) + f (n) log n) time.
Theorem 3. Given a dynamic path network with n vertices and general edge
capacities, we can nd an optimal k-sink in O(n log3 n) time.
In the uniform edge capacity case, we have h(n) = O(n) by Lemma 9, g(n) =
O(log n) by Lemma 10, and f (n) = O(n) by Lemma 11. Lemma 13 thus implies
Theorem 4. Given a dynamic path network with n vertices and uniform edge
capacities, we can nd the k-sink in O(n log n) time.
We have presented more ecient algorithms than the existing ones to solve the
k-sink problem on dynamic ow path networks. Due to lack of space, we could
not present all the proofs. All our results are valid if the model is changed slightly,
so that the weights and edge capacities are not restricted to be integers. Then
it becomes conuent transshipment problem.
For dynamic ow tree networks with uniform edge capacities, it is known
that computing evacuation time to a vertex can be transformed to that on a
path network [13]. We believe that our method is applicable to each spine,
which is a path in the spine decomposition of a tree [2], and we think we may be
able to solve the k-sink problem on dynamic ow tree networks more eciently.
This is work in progress.
144 B. Bhattacharya et al.
References
1. G. P. Arumugam, J. Augustine, M. J. Golin, and P. Srikanthan. A polynomial time
algorithm for minimax-regret evacuation on a dynamic path. arXiv:1404,5448v1,
2014.
2. R. Benkoczi, B. Bhattacharya, M. Chrobak, L. Larmore, and W. Rytter. Faster
algorithms for k-median problems in trees. Mathematical Foundations of Computer
Science, Springer-Verlag, LNCS 2747:218227, 2003.
3. Binay Bhattacharya and Tsunehiko Kameda. Improved algorithms for computing
minmax regret sinks on path and tree networks. Theoretical Computer Science,
607:411425, Nov. 2015.
4. S. W. Cheng, Y. Higashikawa, N. Katoh, G. Ni, B. Su, and Y. Xu. Minimax
regret 1-sink location problem in dynamic path networks. In Proc. Annual Conf.
on Theory and Applications of Models of Computation (T-H.H. Chan, L.C. Lau,
and L. Trevisan, Eds.), Springer-Verlag, volume LNCS 7876, pages 121132, 2013.
5. L. R. Ford and D. R. Fulkerson. Constructing maximal dynamic ows from static
ows. Operations research, 6(3):419433, 1958.
6. G. N. Frederickson. Optimal algorithms for tree partitioning. In Proc. 2nd ACM-
SIAM Symp. Discrete Algorithms, pages 168177, 1991.
7. G. N. Frederickson and D. B. Johnson. Finding kth paths and p-centers by gener-
ating and searching good data structures. J. Algorithms, 4:6180, 1983.
8. H.W. Hamacher and S.A. Tjandra. Mathematical modeling of evacuation prob-
lems: a state of the art. in: Pedestrian and Evacuation Dynamics, Springer Verlag,,
pages 227266, 2002.
9. Y. Higashikawa. Studies on the space exploration and the sink location under
incomplete information towards applications to evacuation planning. PhD thesis,
Kyoto University, Japan, 2014.
10. Y. Higashikawa, M. J. Golin, and N. Katoh. Minimax regret sink location problem
in dynamic tree networks with uniform capacity. J. of Graph Algorithms and
Applications, 18.4:539555, 2014.
11. Y. Higashikawa, M. J. Golin, and N. Katoh. Multiple sink location problems in
dynamic path networks. Theoretical Computer Science, 607:215, 2015.
12. B. Hoppe and E. Tardos. The quickest transshipment problem. Mathematics of
Operations Research, 25(1):3662, 2000.
13. N. Kamiyama, N. Katoh, and A. Takizawa. An ecient algorithm for evacuation
problem in dynamic network ows with uniform arc capacity. IEICE Transactions,
89-D(8):23722379, 2006.
14. S. Mamada, K. Makino, and S. Fujishige. Optimal sink location problem for dy-
namic ows in a tree network. IEICE Trans. Fundamentals, E85-A:10201025,
2002.
15. S. Mamada, T. Uno, K. Makino, and S. Fujishige. An O(n log2 n) algorithm for
a sink location problem in dynamic tree networks. Discrete Applied Mathematics,
154:23872401, 2006.
16. N. Megiddo. Combinatorial optimization with rational objective functions. Math.
Oper. Res., 4:414424, 1979.
17. N. Megiddo and A. Tamir. New results on the complexity of p-center problems.
SIAM J. Comput., 12:751758, 1983.
18. M. Skutella. An introduction to network ows over time. In Research Trends in
Combinatorial Optimization, pages 451482. Springer, 2009.
A 2-Approximation for the Height of Maximal
Outerplanar Graph Drawings
1 Introduction
Graph drawing is the art of creating a picture of a graph that is visually appeal-
ing. In this paper, we are interested in drawings of so-called outerplanar graphs,
i.e., graphs that can be drawn in the plane such that no two edges have a point
in common (except at common endpoints) and all vertices are incident to the
outerface. All drawings are required to be planar, i.e., to have no crossing. The
drawing model used is that of at visibility representations where vertices are
horizontal segments and edges are horizontal or vertical segments, but any such
drawing can be transformed into a poly-line drawing (or even a straight-line
drawing if the width is of no concern) without adding height [6].
Every planar graph with n vertices has a straight-line drawing in an n n-
grid [19,9]. Minimizing the area is NP-complete [17], even for outerplanar graphs
[7]. In this paper, we focus on minimizing just one direction of a drawing (we use
the height; minimizing the width is equivalent after rotation). It is not known
whether minimizing the height of a planar drawing is NP-hard (the closest related
result concerns minimizing the height if edges must connect adjacent rows [16]).
Given the height H, testing whether a planar drawing of height H exists is xed
parameter tractable in H [12], but the run-time is exceedingly large in H. As
such, approximation algorithms for the height of planar drawings are of interest.
TB supported by NSERC. Part of this work appeared as PDs Masters thesis [10].
It is known that any graph G with a planar drawing of height H has pw(G)
H [13], where pw(G) is the so-called pathwidth of G. This makes the path-
width a useful parameter for approximating the height of a planar graph draw-
ing. For a tree T , Suderman gave an algorithm to draw T with height at
most 32 pw(T ) [20], making this an asymptotic 32 -approximation algorithm. It
was discovered later that optimum-height drawings can be found eciently for
trees [18]. Approximation-algorithms for the height or width of order-preserving
and/or upward tree drawing have also been investigated [1,2,8].
For outerplanar graphs, the rst author gave two results that will be improved
upon in this paper. In particular, every maximal outerplanar graph has a drawing
of height at most 3 log n1 [3], or alternatively of height 4pw(G)3 [5]. Note that
the second result gives a 4-approximation on the height of drawing outerplanar
graphs, and improving this 4 is the main objective of this paper. A number
of results for drawing outerplanar graphs have been developed since paper [3].
In particular, any outerplanar graph with maximum degree admits a planar
straight-line drawing with area O(n1.48 ) [15], or with area O(n log n) [14].
The former bound was improved to O(n1.48 ) area[11]. Also, every so-called
balanced outerplanar graph can be drawn in an O( n) O( n)-grid [11].
In this paper, we present a 2-approximation algorithm for the height of planar
drawings of maximal outerplanar graphs. The key ingredient is to dene the
so-called umbrella depth ud(G) in Section 3. In Section 4, we show that any
outerplanar graph G has a planar drawing of height at most 2ud(G) + 1. This
algorithm is a relatively minor modication of the one in [5], albeit described
dierently. The bulk of the work for proving a better approximation factor hence
lies in proving a better lower bound, which we do in Section 5: Any maximal
outerplanar graph G with a planar drawing of height H has ud(G) H 1.
2 Preliminaries
r2
r2
2
r1 r1
2
1 1
(a) (b)
See also Figure 2(a). For such an umbrella U , the fan at u is the outerplanar
path that starts at an edge (u, x) of the handle P , contains all neighbours of
u, and that is minimal with respect to these constraints. If all neighbours of u
belong to P , then the fan at u is empty. Dene the fan at v similarly, using v.
Any edge (a, b) of U that is a cutting edge of G, but not of U , is called
an anchor-edge of U in G. (In the standard embedding, such edges are on the
outerface of U but not on the outerface of G.) The hanging subgraph with respect
to anchor-edge (a, b) of U in G is the cut-component Sa,b of G with respect to
cutting-edge (a, b) that does not contain the cap (u, v) of U . We often omit of
U in G when umbrella and super-graph are clear from the context.
u v u v
a b
x
(a) (b)
Figure 2: (a) An umbrella system of depth 3. The root umbrella is shaded, with
its handle darker shaded. (b) The same graph has a bonnet system of depth 2,
with the root bonnet shaded and its ribbon darker shaded.
See also Figure 2(a). A graph may have many dierent umbrella systems
with the same root-edge. Dene ud(G; u, v) (the (rooted) umbrella depth of G)
to be the minimum depth over all umbrella systems with root-edge (u, v). Note
that the umbrella depth depends on the choice of the root-edge; dene the free
umbrella depth ud(G) := udfree (G) to be the minimum umbrella depth over all
A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings 149
possible root-edges. (One can show that the free umbrella depth is at most one
unit less than the rooted umbrella depth for any choice of root-edge; see [10].)
Bonnets: A bonnet is a generalization of an umbrella that allows two handles,
as long as they go to dierent sides of the interior face at (u, v). Thus, condition
(2) of the denition of an umbrella gets replaced by
2. There exists a non-empty outerplanar path P U (the ribbon) that connects
two non-cutting edges and contains u, v and their common neighbour.
Other than that, bonnets are dened exactly like umbrellas. See also Figure 2(b).
We dene bonnet system, root bonnet, etc., exactly as for an umbrella system,
except that bonnet is substituted for umbrella everywhere. Let bd(G; u, v)
(the rooted bonnet-depth of G) be the minimum possible depth of a bonnet
system with root-edge (u, v), and let bdfree (G) = bd(G) be the minimum bonnet-
depth over all choices of root-edge. Since any umbrella is a bonnet, we have
bd(G) ud(G).
By denition the root bonnet U0 must contain all edges incident to the ends
u, v of the root-edge. If follows that no edge incident to u or v can be an anchor-
edge of U0 , else the hanging subgraph at it would contain further neighbours of
u (resp. v). We note this trivial but useful fact for future reference:
Observation 1 In a bonnet system with root-edge (u, v), no edge incident to u
or v is an anchor-edge of the root bonnet.
Lemma 1. Let U0 be the root bonnet of a bonnet system with root-edge (u, v).
Then there exists a at visibility representation of U0 on three layers such that
1. (u, v) spans the top layer of .
2. Any anchor-edge of U0 is drawn horizontally in the middle or bottom layer.
the regions of faces that u and v are incident to. Similarly create segments for
all other vertices. The placement for the vertices is uniquely determined by the
standard planar embedding, except for the vertices incident to f1 and fk . We
place those vertices such that the leftmost/rightmost vertical edge is not an
anchor-edge. To see that this is possible, recall that P connects two non-cutting
edges e1 , e2 of G that are incident to f1 and fk . If e1
= (u, v), then choose the
layer for the vertices of f1 such that e1 is drawn vertically. If e1 = (u, v), then one
of its ends (say u) is the degree-2 vertex on f1 and drawn in the top-left corner.
The other edge e incident to u is not an anchor-edge of U by Observation 1, and
we draw e vertically. So the leftmost vertical edge is either a non-cutting edge
(hence not an anchor-edge) or edge e (which is not an anchor-edge). We proceed
similarly at fk so that the rightmost vertical edge is not an anchor-edge. Finally
all other vertical edges are cutting edges of U0 and hence not anchor-edges.
The drawing of P obtained in this rst step has (u, v) in the top layer. As a
second step, we now release (u, v) as in [5]. This operation adds a layer above
the drawing, moves (u, v) into it, and re-routes edges at u and v by expanding
vertical ones and turning horizontal ones into vertical ones. In the result, (u, v)
spans the top layer. See Figure 3(b) for an illustration and [5] for details.
u v
fan at v
br
u v br fan at u
rest of P
e f1 f2 f3 f4 rest of P e2
a
a
(c) Adding the fans. The resulting drawing is not in
(a) Drawing the ribbon. the standard embedding.
u v
x y
u v Sa,b
new layers
br
rest of P Sx,y
a a b
As the third and nal step, we add the fans. Consider the fan at v, and let
(v, br ) be the edge that it has in common with the ribbon P . Assume rst that
(v, br ) was drawn horizontally after the rst step, see Figure 3(a). After releasing
(u, v) therefore no edge at br attaches on its left, see Figure 3(b). Into this space
A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings 151
we insert, after adding columns, the remaining vertices of the fan at v, in order
in which they appear around v in the standard embedding. See Figure 3(c)).
Else, (v, br ) was drawn vertically after the rst step. (Figure 3(c) does not
illustrate this case for v, but illustrates the corresponding case for u.) Since the
drawing of the rst step is in the standard embedding, and (v, br ) is on the
outerface of the ribbon, therefore (v, br ) must be the rightmost vertical edge.
We can then simply place the vertices of the fan to the right of br and extend v.
The fan at u is placed in a symmetric fashion. It remains to show that all
anchor-edges are horizontal and in the bottom two layers. We ensured that this
is the case in the rst step. Releasing (u, v) adds more vertical edges, but all of
them are incident to u or v and not anchor-edges by Observation 1. Likewise,
all vertical edges added when inserting the fans are incident to u or v. The only
horizontal edge in the top layer is (u, v), which is not an anchor-edge.
Proof. We show by induction that any graph with a bonnet system U of depth
H has a drawing of height 2H + 1 where the root-edge (u, v) spans the top
layer. This proves the theorem when using a bonnet system U of depth bdfree (G).
Let U0 be the root bonnet of the bonnet system, and draw U0 on 3 layers
using Lemma 1. Thus (u, v) spans the top and any anchor-edge (a, b) of U0
is drawn as a horizontal edge in the bottom two layers of 0 . If H = 1 then
there are no hanging subgraphs and we are done. Else add 2H 2 layers to 0
between the middle and bottom layers. For each anchor-edge (a, b) of U0 , the
hanging subgraph Sa,b of U0 has a bonnet system of depth at most H 1 with
root-edge (a, b). By induction Sa,b has a drawing 1 on at most 2H 1 layers
with (a, b) spanning the top layer.
If (a, b) is in the bottom layer of 0 , then we can rotate (and reect, if
necessary) 1 so that (a, b) is in the bottom layer of 1 and the left-to-right
order of a and b in 1 is the same as their left-to-right order in 0 . This updated
drawing of 1 can then be inserted in the space between (a, b) in 0 . This ts
because 1 has height at most 2H 1, and in the insertion process we can re-use
the layer spanned by (a, b). If (a, b) is in the middle layer of U0 , then we can
reect 1 (if necessary) so that (a, b) has the same left-to-right order in 1 as in
0 . This updated drawing of 1 can then be inserted in the space between (a, b)
in 0 . See Figure 3(d). Since we added 2H 2 layers to a drawing of height 3,
the total height of the nal drawing is 2H + 1 as desired.
Comparison to [5]: The algorithm in [5] has only two small dierences. The
main one is that it does not do the third step when drawing the root bonnet,
thus it draws the ribbon but not the fans. Thus in the induction step our algo-
rithm always draws at least as much as the one in [5]. Secondly, [5] uses a special
construction if pw(G) = 1 to save a constant number of levels. This could easily
be done for our algorithm as well in the case where pw(G) = 1 but bd(G) = 2.
As such, our construction never has worse height (and frequently it is better).
Comparison to [3]: One can argue that bd(G) log(n + 1) (see [10]). Since
[3] uses 3 log n 1 levels while ours uses 2bd(G) + 1 2 log(n + 1) + 1 levels, the
upper bound on the height is better for n 9.
B = B A
1 1 1
w r1 1 w r1
2
2 r2 2 2 r2
(a) (b)
Figure 4: w has a right escape path, (1 , 2 ) is left-free and (r1 , r2 ) is right-free.
After ipping the cutting component at (1 , 2 ), the non-cutting edge (1 , 2 )
becomes left-free.
edge. This does not exist in all drawings (see e.g. Figure 4(a)), but as we show
now, we can modify the drawing without increasing the height such that such an
edge exists. To be able to apply it later, we must also show that this modication
does not destroy a given escape path.
Lemma 2. Let be a at visibility representation of a maximal outerplanar
graph G.
1. Let (r1 , r2 ) be a right-free edge of , and let w be a vertex that has a right
escape path. Then there exists a drawing in which w has a right escape
path, (r1 , r2 ) is a right-free edge, and there exists a left-free edge that is not
a cutting edge of G.
2. Let (1 , 2 ) be a left-free edge of , and let w be a vertex that has a left
escape path. Then there exists a drawing in which w has a left escape
path, (1 , 2 ) is a left-free edge, and there exists a right-free edge that is not
a cutting edge of G.
In either case, the y-coordinates of all vertices in are unchanged in , and
in particular both drawings have the same height.
Proof. We prove the claim by induction on n and show only the rst claim (the
other is symmetric). Let (1 , 2 ) be the leftmost vertical edge of ; this is left-free
as argued above. If (1 , 2 ) is not a cutting edge of G, then we are done with
= . This holds in particular if n = 3 because then G has no cutting edge.
So assume n 4 and (1 , 2 ) is a cutting edge of G. Let A and B be the cut-
components of (1 , 2 ), named such that w A. Let A [resp. B ] be the drawing
of A [B] induced by . Edge (1 , 2 ) is left-free for both A and B . Reect B
horizontally (this makes (1 , 2 ) right-free) to obtain B . By induction, we can
create a drawing B from B in which (1 , 2 ) is right-free and there is a left-free
edge (1 , 2 ) that is not a cutting edge of B. We have (1 , 2 )
= (1 , 2 ), because
the common neighbour of 1 , 2 in B forces a vertex or edge to reside to the left
of the right-free edge (1 , 2 ). So (1 , 2 ) is not a cutting edge of G either.
As in Figure 4(b), create a new drawing that places B to the left of A and
extends 1 and 2 to join the two copies; this is possible since (1 , 2 ) has the
154 T. Biedl and P. Demontigny
We are now ready to prove the lower bound if there is an escape path.
u v
u
P1
Sa,b
b 1
Sa,b v
a P2 1
a
b 2
1
2 2
Now consider any hanging subgraph Sa,b of U0 with anchor-edge (a, b). No
edge incident to v is an anchor-edge, and neither is (1 , 2 ), since it is not a
cutting edge. So (a, b) is an edge of P1 or P2 (say P1 ) that is not incident to v.
A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings 155
Therefore (a, b) (and with it Sa,b ) is vertex-disjoint from P2 . It follows that the
drawing S of Sa,b induced by is disjoint from the dividing path 2 . Since
2 connects a point on the left boundary with a point on the right boundary,
therefore S must be entirely above or entirely below 2 , say it is above. Since
2 has all bends at points with integral y-coordinate, therefore the bottom layer
of is not available for S , and S has height at most H 1 as desired.
Recall that (a, b) belongs to P1 and is not incident to v. After possible re-
naming of a and b, we may assume that b is closer to 1 along P1 than a. Then
the sub-path of P1 from b to 1 is interior-disjoint from Sa,b . The part of 1
corresponding to this path is a left escape path from b that resides within the
top H 1 layers, because it does not contain v and hence is disjoint from 2 .
We can hence apply induction to Sa,b to obtain an umbrella system of depth at
most H 2 with root-edge (a, b). Repeating this for all hanging subgraphs, and
combining the resulting umbrella systems with U0 , gives the result.
Theorem 2. Let G be a maximal outerplanar graph. If G has a at visibility
representation of height H, then udfree (G) H 1.
Proof. Using Lemma 2, we can convert into a drawing of the same height in
which some edge (u, v) is a right-free non-cutting edge. This implies that there is
a right escape path from v, and by Lemma 3 we can nd an umbrella system of
G with root-edge (u, v) and depth H 1. So udfree (G) ud(G; u, v ) H 1.
References
1. Md. J. Alam, Md. A.H. Samee, M. Rabbi, , and Md. S. Rahman. Minimum-layer
upward drawings of trees. J. Graph Algorithms Appl., 14(2):245267, 2010.
2. J. Batzill and T. Biedl. Order-preserving drawings of trees with approximately
optimal height (and small width), 2016. CoRR 1606.02233 [cs.CG]. In submission.
3. T. Biedl. Drawing outer-planar graphs in O(n log n) area. In S. Kobourov and
M. Goodrich, editors, Graph Drawing (GD01), volume 2528 of LNCS, pages 54
65. Springer-Verlag, 2002. Full version included in [4].
4. T. Biedl. Small drawings of outerplanar graphs, series-parallel graphs, and other
planar graphs. Discrete and Computational Geometry, 45(1):141160, 2011.
5. T. Biedl. A 4-approximation algorithm for the height of drawing 2-connected out-
erplanar graphs. In T. Erlebach and G. Persiano, editors, Workshop on Approxi-
mation and Online Algorithms (WAOA12), volume 7846 of LNCS, pages 272285.
Springer-Verlag, 2013.
6. T. Biedl. Height-preserving transformations of planar graph drawings. In C. Dun-
can and A. Symvonis, editors, Graph Drawing (GD14), volume 8871 of LNCS,
pages 380391. Springer, 2014.
7. T. Biedl. On area-optimal planar grid-drawings. In J. Esparza, P. Fraigniaud,
T. Husfeldt, and E. Koutsoupias, editors, International Colloquium on Automata,
Languages and Programming (ICALP 14), volume 8572 of LNCS, pages 198210.
Springer-Verlag, 2014.
8. T. Biedl. Ideal tree-drawings of approximately optimal width (and small height).
Journal of Graph Algorithms and Applications, 21(4):631648, 2017.
9. H. de Fraysseix, J. Pach, , and R. Pollack. How to draw a planar graph on a grid.
Combinatorica, 10:4151, 1990.
10. P. Demontigny. A 2-approximation for the height of maximal outerplanar graphs.
Masters thesis, University of Waterloo, 2016. See also CoRR report 1702.01719.
11. G. Di Battista and F. Frati. Small area drawings of outerplanar graphs. Algorith-
mica, 54(1):2553, 2009.
12. V. Dujmovic, M. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura,
P. Ragde, F. Rosamond, S. Whitesides, , and D. Wood. On the parameterized
complexity of layered graph drawing. Algorithmica, 52:267292, 2008.
13. S. Felsner, G. Liotta, , and S. Wismath. Straight-line drawings on restricted integer
grids in two and three dimensions. J. Graph Alg. Appl, 7(4):335362, 2003.
14. F. Frati. Straight-line drawings of outerplanar graphs in O(dn log n) area. Comput.
Geom., 45(9):524533, 2012.
15. A. Garg and A. Rusu. Area-ecient planar straight-line drawings of outerplanar
graphs. Discrete Applied Mathematics, 155(9):11161140, 2007.
16. L.S. Heath and A.L. Rosenberg. Laying out graphs using queues. SIAM Journal
on Computing, 21(5):927958, 1992.
17. M. Krug and D. Wagner. Minimizing the area for planar straight-line grid drawings.
In S. Hong, T. Nishizeki, and W. Quan, editors, Graph Drawing (GD07), volume
4875 of LNCS, pages 207212. Springer-Verlag, 2007.
18. D. Mondal, Md. J. Alam, , and Md. S. Rahman. Minimum-layer drawings of trees.
In N. Katoh and A. Kumar, editors, Algorithms and Computations (WALCOM
2011), volume 6552 of LNCS, pages 221232. Springer, 2011.
19. W. Schnyder. Embedding planar graphs on the grid. In ACM-SIAM Symposium
on Discrete Algorithms (SODA 90), pages 138148, 1990.
20. M. Suderman. Pathwidth and layered drawings of trees. Intl. J. Comp. Geom.
Appl, 14(3):203225, 2004.
Splitting B2 -VPG Graphs into Outer-string and
Co-comparability Graphs
1 Introduction
L ML MR R
Our proof is constructive, and nds the partition within O(log n) recursions.
In each recursion we must nd the median m and then determine which objects
intersect the line m. If we presort three lists of the objects (once by x-coordinate
of the vertical segment, once by leftmost x-coordinate, and once by rightmost
x-coordinate), and pass these lists along as parameters, then each recursion
can be done in O(n) time, without linear-time median-nding. The presorting
takes O(N + n log n) time, where N is the total number of segments in the
representation. Hence the run-time to nd the partition is O(N + n log n).
The above results were for single-vertical graphs. However, the main focus of
this paper is Bk -VPG-graphs, for k 2. Clearly B1 -VPG graphs are single-
vertical by denition. It is not obvious whether B2 -VPG graphs are single-
vertical graphs or not. Note that a B2 -VPG representation may not be a single-
vertical representationit may consist of both curves with two horizontal seg-
ments and curves with two vertical segments (so no rotation of the representation
can give a single-vertical representation). However, we can still handle them by
doubling the number of graphs into which we split.
We now show that by doing further splits, we can actually decompose B2 -VPG
graphs into so-called co-comparability graphs of poset dimension 3 (dened for-
mally below). While we require more subgraphs for such a split, the advantage is
that numerous problems are polynomial for such co-comparability graphs, while
for outer-string we know of no problem other than weighted independent set
that is poly-time solvable.
We rst give an outline of the approach. Given a B2 -VPG-graph, we rst
use Lemma 3 to split it into two single-vertical B2 -VPG-graphs. Given a single-
vertical B2 -VPG-graph, we next use a technique much like the one of Theorem 1
to split it into log n single-vertical B2 -VPG-graphs that are centered in some
sense. Any such graph can easily be edge-partitioned into two B1 -VPG-graphs
that are grounded in some sense. We then apply the technique of Theorem 1
again (but in the other direction) to split a grounded B1 -VPG-graph into log n
B1 -VPG-graphs that are cornered in some sense. The latter graphs can be
shown to be permutation graphs. This gives the result after arguing that the
edge-partition can be un-done at the cost of combining permutation graphs into
co-comparability graphs.
We assume for this section that the B2 -VPG representation is in general
position in the sense that no two horizontal or vertical segments overlap each
other. Since curves do not overlap or touch, this is not a restriction for B2 -VPG
representations.
We start by dening the graph classes that we use in this section only. A graph
G with vertices {1, . . . , n} is called a permutation graph if there exist two permu-
tations 1 , 2 of {1, . . . , n} such that (i, j) is an edge of G if and only if 1 lists
i, j in the opposite order as 2 does. Put dierently, if we place 1 (1), . . . , 1 (n)
at points along a horizontal line, and 2 (1), . . . , 2 (n) at points along a parallel
horizontal line, and use the line segment (1 (i), 2 (i)) to represent vertex i, then
the graph is the intersection graph of these segments.
A co-comparability graph G is a graph whose complement can be directed
in an acyclic transitive fashion. Rather than dening these terms, we describe
here only the restricted type of co-comparability graphs that we are interested
in. A graph G with vertices {1, . . . , n} is called a co-comparability graph of poset
dimension k if there exist k permutations 1 , . . . , k such that (i, j) is an edge if
and only if there are two permutations that list i and j in opposite order. (See
Golumbic et al. [5] for more on these characterizations.) Note that a permutation
graph is a co-comparability graph of poset dimension 2.
162 T. Biedl and M. Derka
Proof. Since the curves have only one bend, the intersections with r1 and r2
determine the curve of each vertex. In particular, two curves intersect if and
only if the two orders along r1 and r2 are not the same, which is to say, if their
orders are dierent in the two permutations of the vertices dened by the orders
along the rays. Hence using these orders shows that G is a permutation graph.
Proof. A single curve with one bend is always cornered, so the claim is easily
shown for n 4 where max{1, 2 log n} n. For n 5, it will be helpful to
Splitting B2-VPG Graphs into Outer-string and Co-comparability Graphs 163
split R rst into two sets, those curves of the form |h and those that form h| (no
other shapes can exist in a grounded B1 -VPG-representation). The result follows
if we show that each of them can be split into log n many cornered B1 -VPG-
representations.
So assume that R consists of only |hs. We apply essentially the same idea as
in Theorem 1. Let again m be the vertical line along the median of x-coordinates
of vertical segments of curves. Let M be all those curves that intersect m. Since
curves are |hs, any curve in M intersects H to the left of m, and intersects
m above H . Hence taking the two rays along H and m emanating from their
common point shows that M is cornered.
m
m
lh GL GR lh
We then recurse both in the subgraph L of vertices entirely left of m and the
subgraph R of vertices entirely right of m. Each of them is split recursively into
at most max{1, log(n/2)} = log n 1 subgraphs that are cornered. We must now
argue how to combine two such subgraphs GL and GR (of vertices from L and
R) such that they are cornered while modifying curves only in the permitted
way.
Translate curves of GL upward such that the lowest horizontal segment of
GL is above the highest horizontal segment of GR . Extend the vertical segments
of GL so that they again intersect H . Extend horizontal segments of both GL
and GR rightward until they all intersect one vertical line segment. The resulting
representation satises all conditions.
Since we obtain at most log n 1 such cornered representations from the
curves in R L, we can add M to it and the result follows.
Corollary 7. Let G be a graph with a grounded B1 -VPG representation. Then
the vertices of G can be partitioned into at most max{1, 2 log n} sets such that
the subgraph induced by each is a permutation graph.
a permutation 1 along the vertical ray and 2 along H . Similarly the parts
of curves below H dene two permutations, say 2 along H and 3 along
some vertical downward ray. But the split into cornered B1 -VPG-representation
ensured that the intersections along H did not changed, so 2 = 2 . The three
permutations 1 , 2 , 3 together hence dene a co-comparability graph of poset
dimension 3 as desired.
We can do slightly better if the representation is additionally 1-string.
Corollary 9. Let G be a graph with a single-vertical centered 1-string B2 -VPG
representation.Then the vertices of Gcan be partitioned into at most max{1, 4 log2 n}
sets such that the subgraph induced by each is a permutation graph.
Proof. The split is exactly the same as in Lemma 8. Consider one of the sub-
graphs Gi and the permutations 1 , 2 , 3 that came with it, where 2 is the
permutation of curves along the centering line H . We claim that Gi is a per-
mutation graph, using 1 , 3 as the two permutations. Clearly if (u, v) is not an
edge of Gi , then all of 1 , 2 , 3 list u and v in the same order. If (u, v) is an
edge of Gi , then two of 1 , 2 , 3 list u, v in opposite order. We claim that 1
and 3 list u, v in opposite order. For if not, say u comes before v in both 1 and
3 , then (to represent edge (u, v)) we must have u after v in 2 . But then the
curves of u and v intersect both above and below H , contradicting that we have
a 1-string representation. So the two permutations 1 , 3 dene graph Gi .
4 Applications
We now show how Theorem 1 and 11 can be used for improved approximation
algorithms for B2 -VPG-graphs. The techniques used here are virtually the same
as the one by Keil and Stewart [7] and require two things. First, the problem
considered needs to be solvable on the special graphs class (such as outer-string
graph or co-comparability graph or permutation graph) that we use. Second,
the problem must be hereditary in the sense that a solution in a graph implies
a solution in an induced subgraph, and solutions in induced subgraphs can be
used to obtain a decent solution in the original graph.
We demonstrate this in detail using weighted independent set, which Keil
et al. showed to be polynomial-time solvable in outer-string graphs [6]. Recall
that this is the problem, given a graph with vertex-weights, of nding a subset
I of vertices
that has no edges between them. The objective is to maximize
w(I) := vI w(v), where w(v) denotes the weight of vertex v. The run-time to
solve weighted independent set in outer-string graphs is O(N 3 ), where N is the
number of segments in the given outer-string representation.
Splitting B2-VPG Graphs into Outer-string and Co-comparability Graphs 167
Theorem 13. There exists a (2 log n)-approximation algorithm for weighted in-
dependent set on single-vertical graphs with run-time O(N 3 ), where N is the total
number of segments used among all single-vertical objects.
Proof. If n = 1, then the unique vertex is the maximum weight independent set.
Else, use Theorem 1 to partition the vertices of the given graph G into at most
2 log n sets, each of which induces an outer-string graph, and nd the largest
weighted independent set in each applying the algorithm of Keil et al. If Gi had
an outer-string representation with Ni segments in total, then this takes time
O( Ni3 ) time. Note that if a single-vertical object consisted of one vertical
and horizontal segments, then we can trace around it with a curve with O()
segments. Hence all curves together have O(N ) segments and the total run-time
is O(N 3 ).
Let Ii be the maximum-weight independent set in Gi , and return as set I
the set in I1 , . . . , Ik that has the maximum weight. To argue the approximation-
factor, let I be the maximum-weight independent set of G, and dene Ii to
be all those elements of I that belong to Ri , for i = 1, . . . , k. Clearly Ii is an
independent set of Gi , and so w(Ii ) w(Ii ). But on the other hand maxi w(Ii )
w(I )/k since we split I into k sets. Therefore w(I) = maxi w(Ii ) w(I )/k,
and so w(I) is within a factor of k 2 log n of the optimum.
We note here that the best polynomial algorithm for independent set in
general string graphs achieves an approximation factor of O(n ), under the as-
sumption that any two strings cross each other at most a constant number of
times [3]. This algorithm only works for unweighted independent set; we are not
aware of any approximation results for weighted independent set in arbitrary
string graphs.
Because B2 -VPG-graphs can be vertex-split into two single-vertical B2 -VPG-
representations, and the total number of segments used is O(n), we also get:
Corollary 14. There exists a (4 log n)-approximation algorithm for weighted in-
dependent set on B2 -VPG-graphs with run-time O(n3 ).
Another hereditary problem is colouring: Find the minimum number k such
that we can assign numbers in {1, . . . , k} to vertices such that no two adjacent
vertices receive the same number. Fox and Pach [3] pointed out that if we have
a c-approximation algorithm for Independent Set, then we can use it to ob-
tain an O(c log n)-approximation algorithm for colouring. Therefore our result
also immediately implies an O(log2 n)-approximation algorithm for colouring in
single-vertical graphs and B2 -VPG-graphs.
Another hereditary problem is weighted clique: Find the maximum-weight
subset of vertices such that any two of them are adjacent. (This is indepen-
dent set in the complement graph.) Clique is NP-hard in outer-string graphs
even in its unweighted version [2]. For this reason, we use the split into co-
comparability graphs instead; weighted clique can be solved in quadratic time in
co-comparability graphs (because weighted independent set is linear-time solv-
able in comparability graphs [4]). Weighted clique is also linear-time solvable on
permutation graphs [4]. We therefore have:
168 T. Biedl and M. Derka
5 Conclusions
We presented a technique for decomposing single-vertical graphs into outer-string
subgraphs, B2 -VPG-graphs into co-comparability graphs, and 1-string B2 -VPG-
graphs into permutation graphs. We then used these results to obtain approxi-
mation algorithms for hereditary problems, such as weighted independent set.
As for open problems, we are very interested in approximation algorithms
for Bk -VPG graphs, where k is a constant. Also, if curves are not required to
be orthogonal, but have few bends, are there approximation algorithms better
than those for arbitrary string graphs?
References
1. Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit
Vogtenhuber. Intersection graphs of rays and grounded segments. Technical Report
1612.03638 [cs.DM], ArXiV, 2016.
2. Sergio Cabello, Jean Cardinal and Stefan Langerman. The Clique Problem in Ray
Intersection Graphs. Discrete & Computational Geometry 50(3), 771783, 2013.
3. Jacob Fox and Janos Pach. Computing the independence number of intersection
graphs. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-
SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California,
USA, January 23-25, 2011, pages 11611165. SIAM, 2011.
4. M. C. Golumbic. Algorithmic graph theory and perfect graphs. Academic Press, New
York, 1st edition, 1980.
5. Martin Charles Golumbic, Doron Rotem, and Jorge Urrutia. Comparability graphs
and intersection graphs. Discrete Mathematics, 43(1):3746, 1983.
6. J. Mark Keil, Joseph S. B. Mitchell, Dinabandhu Pradhan, and Martin Vatshelle. An
algorithm for the maximum weight independent set problem on outerstring graphs.
Comput. Geom., 60:1925, 2017.
7. J. Mark Keil and Lorna Stewart. Approximating the minimum clique cover and
other hard problems in subtree lament graphs. Discrete Applied Mathematics,
154(14):19831995, 2006.
8. Abhiruk Lahiri, Joydeep Mukherjee, and C. R. Subramanian. Maximum indepen-
dent set on B1 -VPG graphs. In Zaixin Lu, Donghyun Kim, Weili Wu, Wei Li,
and Ding-Zhu Du, editors, Combinatorial Optimization and Applications (COCOA
2015), volume 9486 of Lecture Notes in Computer Science, pages 633646. Springer,
2015.
A Deterministic Algorithm
for Online Steiner Tree Leasing
1 Introduction
valid only for a single terminal and cannot be reused by subsequent ones. This
variant is called online single-source rent-or-buy [3,10,11,12,15,17,21] and is also
equivalent to the le replication problem.
Note that the rent-or-buy variant is still incremental: bought edges persist in
the graph till the end and if a request to connect a specic terminal appears
suciently many times in the input any reasonable algorithm nally buys
a path connecting this terminal to the root r.
The goal is to minimize the competitive ratio, dened as a worst-case ratio of the
cost of an online algorithm to the cost of the optimal oine solution (denoted
Opt) on the same input.
This tree T is a hierarchically separated tree (HST), whose leaves are requested
terminals and whose distances dominate graph distances. By showing that our
algorithm is O(L)-competitive against Opt on T , for any choice of T , we obtain
that it is O(L log k)-competitive against Opt on the original graph G. The
details of this reduction are presented in Sect. 2.
We emphasize that the competitive ratio of our algorithm is a function of the
number of dierent terminals, k, and not the number of nodes in the graph, n,
as it is the case for the randomized algorithm of [19]. In fact, our algorithm and
its analysis work without changes also in any (innite) metric space, e.g., on the
Euclidean plane; in the paper, we use the graph terminology for simplicity.
Other network design problems were also studied in leasing context. In par-
ticular, a randomized O(log L log n)-competitive algorithm was given for the
Online Steiner Forest Leasing by Meyerson [19]. Deterministic algorithms for
this problem are known only for the rent-or-buy subcase, for which an opti-
mal competitive ratio of O(log k) was achieved by Umboh [21]. Other problems
include the facility location [1,20] and the set cover [2].
The leasing setting was also applied to oine scenarios of the problems above
by Anthony and Gupta [6], who showed an interesting reduction between leasing
and stochastic optimization variants.
2 HST Embeddings
In this section, we show how to use hierarchically separated trees (HSTs) for the
analysis of an algorithm for the OSTL problem. Unlike many online construc-
tions for network design problems (see, e.g., [8,19]), here HSTs are not used for
an algorithm construction. Moreover, in our analysis, an HST will approximate
not the whole graph, but only the subgraph spanned by terminals.
1. The leaves of T are exactly the nodes of X and they are on the same level.
2. The distance from any leaf of T to its parent is 1.
3. The edge lengths increase by a factor of 2 on any leaf-to-root path.
4. dT dominates dG , i.e., dT (u, v) dG (u, v) for any pair of nodes u, v X.
1
For analysis, we may always scale the instance, so that this property holds.
A Deterministic Algorithm for Online Steiner Tree Leasing 173
Fix now any instance I = (G, dG , r, L; ) of the OSTL and let (T, dT ) be any
dominating HST embedding of terminals of I. Let IT = (T, dT , r, L; ) be the
instance I, where graph G was replaced by tree T with distances given by dT .
While estimating Opt(I) directly may be quite involved, lower-bounding
Opt(IT ) is much easier. In particular, for each request t there is a unique path
in T connecting t with r. As dT dominates dG , it is also feasible to compare
the cost of an online algorithm on I to Opt(IT ). Finally, it is possible to relate
Opt(IT ) to Opt(I) as stated in the following lemma, due to Umboh [21].
Proof. Fix any dominating HST embedding (T, dT ) of terminals X. The solution
Opt(I) is a schedule that leases particular edges of G at particular times. Let
Off(IT ) be an oine solution that, for any leased edge e = (u, v) in Opt(I),
leases all edges on the unique path in T from u to v, using the same lease
type. While it is not necessary for the proof, it is worth observing that, by the
domination property (cf. Denition 1), Opt(I) Off(IT ).
By the FRT approximation [14], there exists a probability distribution D
over dominating HST embeddings (T, dT ) of X, such that ET D [dT (u, v)]
O(log |X|) dG (u, v) for all u, v X. This relation summed over all edges (u, v)
used in the solution of Opt(I) yields that
The lemma can be generalized to any network design problem whose objective
function is a linear combination of edge lengths. In Sect. 4, we will construct an
algorithm for the OSTL which is O(L)-competitive against the cost of Opt on
any HST embedding. By Lemma 2, this algorithm is O(L log k)-competitive.
3 Interval Model
In this section, we make several assumptions on the available leases. At the
expense of a constant increase of the competitive ratio, they will make the con-
struction of our algorithm easier. Similar assumptions were also made for the
parking permit problem [19].
Denition 3. In the interval model, the following conditions hold for the input
instance.
Costs factors and durations of all leases are powers of two.
174 M. Bienkowski et al.
Lease types are sorted both by their costs and durations, i.e., if < , then
D < D and C < C .
Fix any lease type and let Jm = [m D , (m + 1) D ) for any m N.
For any time t and any edge, there is a unique lease of type that can be
acquired by an algorithm: it is the lease for period Jm containing t.
The last property of the interval model means that, unlike the standard
leasing model outlined in Sect. 1.1, if an algorithm leases an edge at a time t
using a lease type L, such transaction may occur within the lease duration.
Hence, the acquired lease may expire earlier than at time t + D . We also dene
J [t] to be the period Jm containing time t.
Observation 4. In the interval model, when lease of type expires, all leases
of smaller types expire as well.
Lemma 5. Any (online or oine) algorithm for the original leasing model can
be transformed into an algorithm for the interval model (and back) without chang-
ing its cost by more than a constant factor.
The lemma above follows by standard rounding arguments (its proof is omit-
ted; see [19] for a similar argument). Hence, if an algorithm is R-competitive for
the interval model, it is O(R)-competitive for the original leasing model. There-
fore, we will assume the interval model in the remaining part of the paper.
4 Algorithm Construction
We present our algorithm Accumulate-and-Lease-Greedily (Alg). For sim-
plicity of the description, we assume that a given graph G is complete (with the
metric given by dG ). Such assumption is without loss of generality, as leasing
the edge (u, v) can be always replaced by leasing a shortest path connecting u
and v.
We will say that an edge e is -leased at time t, if an algorithm leased e for
period J [t] using lease type . Additionally, a request t is -leased if at time t
an algorithm -leases an edge e = (t , u) for some u.
By F [t] and Fm we denote the set of all requests that arrived during J [t]
and Jm , respectively. Furthermore, T [t] denotes the set of requests that are
connected, at time t, to the root r using edges of lease types at least .
High-level idea. In the execution of Alg, at any time t, the set of all currently
leased edges will be a single (possibly empty) tree, called the Steiner tree of Alg.
Furthermore, on any path from the root r that consists of leased edges, the closer
we are to the root, the longer leases we have. In eect, T [t] always forms a tree.
Moreover, when leases expire, the set of leased edges shrinks, but it remains
connected.
When a request t arrives, we check whether we can aord a lease for t ,
starting from the longest (and the most expensive) available lease: We compute
the distance d from t to T [t]. Then, we check if there were suciently many
requests served recently in a small (compared to d) neighborhood of t . If
so, then we connect t to T [t] using lease type .
A Deterministic Algorithm for Online Steiner Tree Leasing 175
Note that the terminals of Nt are not necessarily connected to the Steiner
tree of Alg at time t. If the number of requests in Nt is at least C /C1 , then Alg
-leases the edge (t , x ) and sets the class of t to j. Otherwise, Alg proceeds
to cheaper lease types. If no lease type satises the condition |Nt | C /C1 ,
Alg eventually 1-leases the edge (t , x1 ). Note that Alg leases exactly one edge
for each terminal that is not connected to the tree at the time of its arrival.
Pseudocode of Alg is given in Algorithm 1. We recall the property of Alg
stated earlier in its informal description.
Observation 6. For any time t and lease type L, T [t] is a single tree.
5 Analysis
its neighbor set. We denote the set of all requests of class j by Wj . Additionally,
let Wj consist of all requests from Wj that were -leased.
A brief idea of the proof is as follows. Suppose each request t Wj receives
a credit of C1 2j when it arrives. If t was -leased, the actual cost paid by
Alg was C 2j . While the latter amount can be much larger for an individual
request t , in Sect. 5.1, we show that, for any xed lease type , the total cost
paid for -leased edges is bounded by the sum of all requests credits. In Sect. 5.2,
we exploit properties of dominating HST embeddings to show how all credits can
be charged (up to constant factors) to the leasing costs Opt pays for particular
edges of the tree T . Altogether, this will show that Alg(I) O(L) Opt(IT ).
Along with Lemma 2, this will bound the competitive ratio of Alg (see Sect. 5.3).
Proof. Without loss of generality, s < t. We will prove the lemma by contradic-
tion. Assume there exists a request u Ns Nt .
By the denition of neighbor sets, u F [s] F [t]. In the interval model,
there are only two possibilities: either periods J [s] and J [t] are equal or they
are disjoint. As in the latter case the corresponding sets F [s] and F [t] would
be disjoint as well, it holds that J [s] = J [t].
As the leases of type that Alg bought for t and s started and expired
at the same time, s was in the tree T [t] when t arrived. Thus, the dis-
tance between t and the tree T [t] was at most dG (t , s ). From the trian-
gle inequality and diameters of sets Ns and Nt , it follows that dG (t , s )
dG (t , u ) + dG (u , s ) 2j2 + 2j2 = 2j1 . Hence, the request t would be
of class j 1 or lower, which would contradict its choice.
Proof. The lemma follows trivially for = 1, and therefore we assume that 2.
We look at any request t Wj and its neighbor set Nt . As t is of class j,
N contains requests only of class j, i.e., Nt Wj .
t
By Lemma 7, the neighbor
sets of all requests from Wj are disjoint, and hence t W |Nt | |Wj |.
j
t
As Alg -leases requestt , its neighbor set N contains at least C /C1
requests. Therefore, |Wj | t W |N | t W C /C1 = |Wj | C /C1 .
t
j j
Lemma 9. For any input I, it holds that Alg(I) L j |Wj | C1 2j .
Proof. The cost of serving any request t Wj is at most C 2j . Using Lemma 8,
we obtain Alg(I) L j |Wj | C 2j L j |Wj | C1 2j .
A Deterministic Algorithm for Online Steiner Tree Leasing 177
Fig. 1. An example of an HST embedding. Square nodes (leaves of the HST) repre-
sent terminals from an input sequence (including root r). Edge e is a 2-level edge (of
length 22 ). D(e) is the set of leaves below edge e.
Proof. We rst assume that j 1 and we will show that |1 (e) Fm |
C /C1 + 1 2 C /C1 .
For a contradiction, assume that 1 (e) Fm contains more than b =
C /C1 + 1 requests. Let s and t be the b-th and the (b + 1)-th of them,
respectively. By Lemma 11, all requests of 1 (e) are of class j + 3 and are
contained in D(e). By Observation 10, they are all within a distance of 2j+1
from s in the graph. Therefore, Ns , the neighbor set of s considered by Alg,
contains all previous requests from 1 (e) Fm (there are b 1 = C /C1 many
of them). The condition at Line 8 of Algorithm 1 is thus fullled, and therefore
Alg buys a lease of type at least for s .
In eect, when t arrives, s is in T [t]. Hence, the distance from t to the
tree T [t] in the graph is at most dG (t , s ) dT (t , s ) 2j+1 . Therefore,
the class of t is at most j + 1, which contradicts the choice of t .
The analysis above can be extended to any 0-level edge e. Because D(e) for
e E0 contains exactly one terminal, all requests from 1 (e) Fm are always
contained in the appropriate neighbor set. This implies that |1 (e) Fm
3
Wi | 2 C /C1 for any class i {0, 1, 2, 3}. As 1 (e) = D(e) i=0 Wi , we
obtain |1 (e) Fm | 4 2 C /C1 .
Lemma 13. Fix a j-level edge e of T. Then, |1 (e)| C1 2j 8 Opt(e).
Proof. By Lemma 11, for each request t in 1 (e), Opt has to have edge e
leased at time t, as e lies on the only path between t and the root r (see also
Fig. 1).
Let P (e) be the set
of all pairs (, m), such that Opt -leases e for period Jm .
That is, Opt(e) = (,m)P (e) C 2 . In the optimal solution Jm periods are
j
pairwise disjoint for all pairs (, m) in P (e), and hence so are sets Fm . Thus,
|1 (e)| C1 2j = |1 (e) Fm | C1 2j
(,m)P (e)
8 C 2j = 8 Opt(e) ,
(,m)P (e)
6 Conclusions
We showed that the technique of analyzing greedy algorithms using HSTs can be
also applied to the leasing variant of the online Steiner tree (the OSTL problem).
A natural research direction is to employ it for other leasing variants of graph
problems, such as Steiner forest or facility location.
Closing the gap between the current upper and lower bounds for the deter-
ministic algorithms solving the OSTL problem (O(L log k) and (L + log k),
respectively) is an intriguing open problem. In particular, it seems that improv-
ing the competitive ratio requires a very careful interplay between path-choosing
and lease-upgrade routines. We remark that analogous gaps exist also for ran-
domized algorithms for the OSTL problem and for a leasing variant of the facility
location problem [20].
References
1. Absho, S., Kling, P., Markarian, C., Meyer auf der Heide, F., Pietrzyk, P.: Towards
the price of leasing online. Journal of Combinatorial Optimization pp. 120 (2015)
2. Absho, S., Markarian, C., Meyer auf der Heide, F.: Randomized online algorithms
for set cover leasing problems. In: Proc. 8th Int. Conf. on Combinatorial Optimiza-
tion and Applications (COCOA). pp. 2534 (2014)
3. Albers, S., Koga, H.: New on-line algorithms for the page replication problem.
Journal of Algorithms 27(1), 7596 (1998)
180 M. Bienkowski et al.
4. Alon, N., Azar, Y.: On-line Steiner trees in the Euclidean plane. In: Proc. 8th ACM
Symp. on Computational Geometry (SoCG). pp. 337343 (1992)
5. Angelopoulos, S.: On the competitiveness of the online asymmetric and Euclidean
Steiner tree problems. In: Proc. 7th Workshop on Approximation and Online Al-
gorithms (WAOA). pp. 112 (2009)
6. Anthony, B.M., Gupta, A.: Infrastructure leasing problems. In: Proc. 12th Int.
Conf. on Integer Programming and Combinatorial Optimization (IPCO). pp. 424
438 (2007)
7. Armbrust, M., Fox, A., Grith, R., Joseph, A.D., Katz, R.H., Konwinski, A.,
Lee, G., Patterson, D.A., Rabkin, A., Stoica, I., Zaharia, M.: Above the clouds: A
Berkeley view of cloud computing. Tech. Rep. UCB/EECS-2009-28, EECS Depart-
ment, University of California, Berkeley (2009), https://www2.eecs.berkeley.
edu/Pubs/TechRpts/2009/EECS-2009-28.pdf
8. Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: Proc. 38th IEEE Symp.
on Foundations of Computer Science (FOCS). pp. 542547 (1997)
9. Awerbuch, B., Azar, Y., Bartal, Y.: On-line generalized Steiner problem. Theoret-
ical Computer Science 324(23), 313324 (2004)
10. Awerbuch, B., Bartal, Y., Fiat, A.: Competitive distributed le allocation. In: Proc.
25th ACM Symp. on Theory of Computing (STOC). pp. 164173 (1993)
11. Bartal, Y., Fiat, A., Rabani, Y.: Competitive algorithms for distributed data man-
agement. Journal of Computer and System Sciences 51(3), 341358 (1995)
12. Black, D.L., Sleator, D.D.: Competitive algorithms for replication and migra-
tion problems. Tech. Rep. CMU-CS-89-201, Department of Computer Science,
Carnegie-Mellon University (1989)
13. Chowdhury, N.M.K., Boutaba, R.: A survey of network virtualization. Computer
Networks 54(5), 862876 (2010)
14. Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary
metrics by tree metrics. Journal of Computer and System Sciences 69(3), 485497
(2004)
15. Fleischer, R., Glazek, W., Seiden, S.S.: New results for online page replication.
Theoretical Computer Science 324(23), 219251 (2004)
16. Imase, M., Waxman, B.M.: Dynamic Steiner tree problem. SIAM Journal on Dis-
crete Mathematics 4(3), 369384 (1991)
17. Lund, C., Reingold, N., Westbrook, J., Yan, D.C.K.: Competitive on-line algo-
rithms for distributed data management. SIAM Journal on Computing 28(3), 1086
1111 (1999)
18. Matsubayashi, A.: Non-greedy online Steiner trees on outerplanar graphs. In: Proc.
14th Workshop on Approximation and Online Algorithms (WAOA). pp. 129141
(2016)
19. Meyerson, A.: The parking permit problem. In: Proc. 46th IEEE Symp. on Foun-
dations of Computer Science (FOCS). pp. 274284 (2005)
20. Nagarajan, C., Williamson, D.P.: Oine and online facility leasing. Discrete Op-
timization 10(4), 361370 (2013)
21. Umboh, S.: Online network design algorithms via hierarchical decompositions. In:
Proc. 26th ACM-SIAM Symp. on Discrete Algorithms (SODA). pp. 13731387
(2015)
22. Westbrook, J., Yan, D.C.K.: The performance of greedy algorithms for the on-line
Steiner tree and related problems. Mathematical Systems Theory 28(5), 451468
(1995)
23. Wu, W., Huang, Y.: Steiner trees. In: Encyclopedia of Algorithms, pp. 21022107
(2016)
The I/O Complexity of Strassens Matrix
Multiplication with Recomputation
Abstract. A tight ((n/ M )log2 7 M ) lower bound is derived on the
I/O complexity of Strassens algorithm to multiply two n n matrices,
in a two-level storage hierarchy with M words of fast memory. A proof
technique is introduced, which exploits the Grigorievs ow of the matrix
multiplication function as well as some combinatorial properties of the
Strassen computational directed acyclic graph (CDAG). Applications to
parallel computation are also developed. The result generalizes a similar
bound previously obtained under the constraint of no-recomputation,
that is, that intermediate results cannot be computed more than once.
1 Introduction
Data movement is increasingly playing a major role in the performance of
computing systems, in terms of both time and energy. This technological trend [1]
is destined to continue, since the very fundamental physical limitations on
minimum device size and on maximum message speed lead to inherent costs
when moving data, whether across the levels of a hierarchical memory system
or between processing elements of a parallel system [2]. The communication
requirements of algorithms have been the target of considerable research in the
last four decades; however, obtaining signicant lower bounds based on such
requirements remains an important and challenging task.
In this paper, we focus on the I/O complexity of Strassens matrix multiplica-
tion algorithm. Matrix multiplication is a pervasive primitive utilized in many
applications. Strassen [3] showed that two n n matrices can be multiplied with
O(n ) operations, where = log2 7 2.8074, hence with asymptotically fewer
than the n3 arithmetic operations required by the straightforward implementation
of the denition of matrix multiplication. This result has motivated a number of
eorts which have lead to increasingly faster algorithms, at least asymptotically,
with the current record being at < 2.3728639 [4].
This work was supported, in part, by MIUR of Italy under project AMANDA
2012C4E3KT 004 and by the University of Padova under projects CPDA121378/12,
and CPDA152255/15.
Previous and Related Work: I/O complexity has been introduced in the
seminal work by Hong and Kung [5]; it is essentially the number of data transfers
between the two levels of a memory hierarchy with a fast memory of M words and
a slow memory with an unbounded number of words. Hong and Kung presented
techniques to develop lower bounds to the I/O complexity of computations
modeled by computational directed acyclic graphs (CDAGs). The resulting lower
bounds apply to all the schedules of the given CDAG, including those with
recomputation, that is, where some vertices of the CDAG
are evaluated multiple
3
times. Among other results, they established an n / M lower bound to
the I/O complexity of the denition-based matrix multiplication algorithm,
which matched a known upper bound [6]. The techniques of [5] have also been
extended to obtain tight communication bounds for the denition-based matrix
multiplication in some parallel settings [79] and for the special case of sparse
matrix multiplication [10]. Ballard et al. generalized the results on matrix
multiplication of Hong and Kung [5] in [11, 12] by using the approach proposed
in [8] based on the Loomis-Whitney geometric theorem [13, 14]. The same papers
present tight I/O complexity bounds for various classical linear algebra algorithms,
for problems such as LU/Cholesky/LDLT/QR factorization and eigenvalues and
singular values computation.
It is natural to wonder what is the impact of Strassens reduction of the
number of arithmetic operations on the number of data transfers. In an important
contribution, Ballard et al. [15], obtained an ((n/ M )log2 7 M ) I/O lower bound
for Strassens algorithm, using the edge expansion approach. The authors extend
their technique to a class of Strassen-like fast multiplication algorithms and to
fast recursive multiplication algorithms for rectangular matrices [16]. This result
was later generalized to a broader class of Strassen-like algorithms by Scott
et. al [17] using the path routing technique. In [18] (Chap. 4.5), De Stefani
presented an alternative technique for obtaining I/O lower bounds for a large
class of Strassen-like algorithms characterized by a recursive structure. This result
combines the concept of Grigorievs ow of a function and the dichotomy width
technique [19]; it generalizes previous results and simplies the analysis.
A parallel, communication avoiding implementation of Strassens algorithm
whose performance matches the known lower bound [15, 17], was proposed by
Ballard et al. [20]. A communication ecient algorithm for the special case of
sparse matrices based on Strassens algorithm was presented in [21].
On the impact of recomputation: The edge expansion technique of [15],
the path routing technique of [17], and the closed dichotomy width technique
of [19] all yield I/O lower bounds that apply only to computational schedules for
which no intermediate result is ever computed more than once (nr-computations).
While it is of interest to know what is the I/O complexity achievable by nr-
computations, it is also important to investigate what can be achieved with
recomputation. In fact, for some CDAGs, recomputing intermediate values reduces
the space and/or the I/O complexity of an algorithm [22]. In [23], it is shown
that some algorithms admit a portable schedule (i.e., a schedule which achieves
optimal performance across memory hierarchies with dierent access costs) only
The I/O Complexity of Strassen's Matrix Multiplication with Recomputation 183
Fig. 1: Basic building blocks of Strassens CDAG. EncA and EncB are isomorphic.
A1,1 A1,2 A2,1 A2,2 B1,1 B1,2 B2,1 B2,2 A1,1 A1,2 A2,1 A2,2 B1,1 B1,2 B2,1 B2,2
Fig. 2: Black vertices represent combinations of the input values from the factor
matrices A and B which are used as input values for the sub-problems Mi ;
Grey vertices represent the output of the seven sub-problems which are used to
compute the output values of the product matrix C.
Lemma 1. Let H nn denote the CDAG of Strassens algorithm for input matri-
ces of size n n. For 0 i log n 1, there are exactly 7i disjoint sub-CDAGs
H n/2 n/2 .
i i
Lemma 2. Given an encoder CDAG, for any subset Y of its output vertices,
there exists a subset X of its input vertices, with min{|Y |, 1 + (|Y | 1) /2}
|X| |Y |, such that there exist |X| vertex-disjoint paths connecting the vertices
in X to vertices in Y .
We refer the reader to the extended on-line version of this paper [29] for a detailed
presentation of Strassens algorithm and for the proofs of Lemmas 1 and 2.
Model: We assume that sequential computations are executed on a system
with a two-level memory hierarchy consisting of a fast memory or cache of size
M , measured in words, and a slow memory of unlimited size. A memory word
can store at most one value from R. An operation can be executed only if all its
operands are in cache. Data can be moved from the slow memory to the cache by
read operations, and, in the other direction, by write operations. Read and write
operations are also called I/O operations. We assume the input data to be stored
in slow memory at the beginning of the computation. The evaluation of a CDAG
in this model can be analyzed by means of the red-blue pebble game [5]. The
number of I/O operations executed when evaluating a CDAG depends on the
computational schedule, that is, on the order in which vertices are evaluated and
on which values are kept in/discarded from cache. The I/O complexity IOG (M )
of a CDAG G is dened as the minimum number of I/O operations over all
possible computational schedules.
We also consider a parallel model where P processors, each with a local
memory of size M , are connected by a network. We assume that the input
is initially distributed among the processors, thus requiring that M P 2n2 .
Processors can exchange point-to-point messages among each other. For this
model, we derive lower bounds to the number of words that must be either sent
or received by at least one processor during the CDAG evaluation.
Grigorievs ow and dominator sets: The concept of dominator set was
originally introduced in [5]. We use the following, slightly dierent, denition:
Denition 1 (Dominator set). Given a CDAG G = (V, E), let I V denote
the set of input vertices. A set D V is a dominator set for V V with respect
to I I if every path from a vertex in I to a vertex in V contains at least a
vertex of D. When I = I, D is simply referred as a dominator set for V V .
The ow of a function was introduced by Grigoriev [27]. We use a revised
formulation by Savage [28]. The ow is an inherent property of a function, not of
a specic algorithm by which the function may be computed.
Denition 2 (Grigorievs ow). A function f : Rp Rq has a w (u, v)
Grigorievs ow if for all subsets X1 and Y1 , of its p input and q output variables,
186 G. Bilardi and L. De Stefani
vertices in Zi via paths with no vertex in Qi . In the sequel, the set Y referred
to in the statement will be identied as a suitable subset of 7i=1 Yi so that
property (b) will be automatically satised. Towards property (a), we observe
by the inductive hypothesis that vertices in Yi can be connected to a subset Ki
of the input vertices of Hinn with |Ki | = |Yi | using vertex-disjoint paths. Since
the sub-CDAGs Hinn are vertex-disjoint, so are the paths $ connecting vertices in
Yi to vertices in Ki . It remains to show that at least 4 M (|Z| 2|Q|) of these
paths can be extended to X while maintaining them vertex-disjoint.
In Strassens CDAG H 2n2n (Sect. 2), vertices in X corresponding to input
matrix A (resp., B) are connected to vertices in K1 , K2 , . . . , K7 by means of
n2 encoding sub-CDAGs EncA (resp., EncB ). None of these 2n2 encoding sub-
CDAGs share any input or output vertices. No two output vertices of the same
encoder sub-CDAG belong to the same sub-CDAG Hinn . This fact ensures that
for a single sub-CDAG Hinn it is possible to connect all the vertices in Ki to a
subset of the vertices in X via vertex-disjoint paths.
For each of the 2n2 encoder sub-CDAGs, let us consider the vector yj {0, 1}7
such that yj [i] = 1 i the corresponding i-th output vertex (respectively according
to the numbering indicated in Fig. 1a or Fig. 1b) is in Ki . Therefore, |yj |
equals the number of output vertices of the j-th encoder sub-CDAG which
are in K. From Lemma 2, for each encoder sub-CDAG there exists a subset
Xj X of the input vertices of the j-th encoder sub-CDAG for which it is
possible to connect each vertex in Xj to a distinct output vertex of the j-th
encoder sub-CDAG using vertex-disjoint paths, each constituted by a singular
edge with min{|yj |, 1 + (|yj | 1) /2} |Xj | |yj |. Therefore, the number
of vertex-disjoint paths connecting vertices in X to vertices in 7i=1 Ki is at
2n2 2n2
least j=1 min{|yj |, 1 + (|yj | 1) /2} under the constraint that j=1 yj [i] =
4 M i . Let us assume, w.l.o.g., that 1 2 . . . 7 . As previously stated, it
is possible to connect all vertices in K1 to vertices in X through vertex-disjoint
paths. Consider now all possible dispositions of the vertices in 7i=2 Ki over
the outputs of the 2n2 encoder sub-CDAGs. Recall that the output vertices
of an encoder sub-CDAG belong each to a dierent H nn sub-CDAG. From
Lemma 2, we have that for each encoder, there exists a subset Xj X of
the input vertices of the j-th encoder sub-CDAG with |Xj | min |yj |, 1 +
7
(|yj | 1) /2 yj [1] + i=2 yj [i] /2, for which it is possible to connect all
vertices in Xj to |Xj | distinct output vertices of the j-th encoder sub-CDAG
which are in 7i=1 Ki using |Xj |, thus using vertex-disjoint paths. As all the
Enc sub-CDAGs are vertex-disjoint, we can add their contributions so that the
number of vertex-disjoint paths connecting vertices in X to vertices in 7i=1 Ki is
1
7 7
at least |K1 | + 2 i=2 |Ki | = 4 M 1 + 12 i=2 i . Squaring this quantity
leads to:
" " ##2 " 7 #2
7 7 $
$ 1 $ $ 1 $
4 M 1 + i = 16M 1 + 1 i + i ,
2 i=2 i=2
2 i=2
The I/O Complexity of Strassen's Matrix Multiplication with Recomputation 189
since, by assumption, 1 . . . 7 , we have: 1 i i for i = 2, . . . , 7. Thus:
" " ##2
$ 7
1 $ 7 $ 2
4 M 1 + i 16M i 4 M (|Z| 2|Q|) .
2 i=2 i=1
$
Thus,there are at least 4 M (|Z| 2|Q|) vertex-disjoint paths connecting vertices
in X to vertices in 7i=2 Ki as desired.
Lemma 7. For 1 M n2 /4, and for any subset Z Z in H nn with
|Z| = 4M , any dominator set D of Z satises |D| |Z|/2 = 2M .
Proof. Suppose for contradiction that D is a dominator set for Z in H nn
such that |D| 2M 1. Let D D be the subset of the vertices
of D
composed by vertices which are not internal to the sub-CDAGs H 2 M 2 M .
From Lemma $ 6, with Q = D \ D , there exist X X and Y Y with |X| =
|Y | 4 M (|Z| 2 (|D| |D |)) such that vertices in X are connected to
vertices in Y by vertex-disjoint paths. Hence, each vertex in D can be on
at most one of these
$ paths. Thus, there exists X X and Y Y with
|X | = |Y | = 4 M (|Z| 2 (|D| |D |)) |D | paths from X to Y with
no vertex in D . From Lemma 6, we also have that all vertices in Y , and, hence,
in Y , are connected to some vertex in Z by a path with no vertex in D \ D .
Thus, there are at least paths connecting vertices in X X to vertices in
Z with no vertex in D. We shall now show that the contradiction assumption
|D| 2M 1 implies > 0:
$ 2
4 M (|Z| 2 (|D| |D |)) = 16M (|Z| 2 (|D| |D |)) ,
= 16M (|Z| 2|D|) + 32M |D |.
Again, |D| 2M 1 implies M (|Z| 2 (|D| |D |)) > 0. Hence, we can take
the square root on both sides of (3) and conclude that > 0. Therefore, for
|D| 2M 1 there are at least > 0 paths connecting a global input vertex
to a vertex in Z with no vertex in D, contradicting the assumption that D is a
dominator of Z.
Lemma 7 provides us with the tools required to obtain our main result.
Theorem 1 (Lower bound I/O complexity Strassens algorithm). The
I/O-complexity of Strassens algorithm to multiply two matrices A, B Rnn ,
on a sequential machine with cache of size M n2 , satises:
log2 7
1 n
IOH nn (M ) M. (4)
7 M
190 G. Bilardi and L. De Stefani
Proof. We start by proving (4). Let n = 2a and M = 2b for some a, b N.
At least 3n2 3M I/O operations are necessary in order to read the 2n2 input
values from slow memory to the cache and to write the n2 output
values to the
slow memory. The bound in (4) is therefore veried if n 2 M .
log2 7
For n 4 M , let Z denote the set of output vertices of the n/(2 M )
sub-CDAGs H 2 M 2 M of H nn . Let C be any computation schedule for the se-
quential execution of Strassens algorithm using a cache of size M . We partition C
into segments C1 , C2 , . . . such that during each Ci exactly 4M distinct vertices in Z
log 7
(denoted as Zi ) are evaluated for the rst time. Since |Z| = 4M n/(2 M ) ,
log 7
there are n/(2 M ) such segments. Below we show that the number qi of
I/O operations executed during each Ci satises qi M , from which (4) follows.
To bound qi , consider the set Di of vertices of H nn corresponding to the at
most M values stored in the cache at the beginning of Ci and to the at most qi
values loaded into the cache from the slow memory during Ci by means of a read
I/O operation. Clearly, |Di | M + qi . In order for the 4M values from Zi to be
computed during Ci there cannot be any path connecting any vertex in Zi to any
input vertex of H nn which does not have at least one vertex in Di ; that is, Di
has to be a dominator set of Zi . We recall that |Zi | = 4M and, from Lemma 7,
we have that any subset of 4M elements of Z has dominator size at least 2M ,
whence M + qi |Di | 2M , which implies qi M as stated above.
The proof for the bound for the parallel model in (5), follows a similar strategy:
At least one of the P processors being used, denoted as P , must compute at
log 7
least |Z|/P = 4M n/(2 M ) /P values corresponding to vertices in Z. The
bound follows by applying the same argument discussed for the sequential case to
the computation executed by P (details the extended on-line version [29]).
Ballard et al. [20] presented a version of Strassens algorithm whose I/O cost
matches the lower bound of Theorem 1 to within a constant factor. Therefore, our
bound is asymptotically tight, and the algorithm in [20] is asymptotically I/O opti-
mal. Since in this algorithm no intermediate result is recomputed, recomputation
can lead at most to a constant factor reduction of the I/O complexity.
The lower bound of Theorem 1 generalizes to ((n/ M )log2 7 M B ) in the
External Memory Model introduced by Aggarwal and Vitter [31], where B 1
values can be moved between cache and consecutive slow memory locations with
a single I/O operation.
The I/O Complexity of Strassen's Matrix Multiplication with Recomputation 191
4 Conclusion
This work has contributed to the characterization of the I/O complexity of
Strassens algorithm by establishing asymptotically tight lower bounds that
hold even when recomputation is allowed. Our technique exploits the recursive
nature of the CDAG, which makes it promising for the analysis of other recursive
algorithms, e.g., for fast rectangular matrix multiplication [32].
The relationship we have exploited between dominator size and Grigorievs ow
points at connections between I/O complexity, (pebbling) space-time tradeos [28],
and VLSI area-time tradeos [33]; these connections deserve further attention.
Some CDAGs for which non-trivial I/O complexity lower bounds are known
only in the case of no recomputations are described in [19]. These CDAGs are of
interest in the limiting technology model, dened by fundamental limitations
on device size and message speed, as they allow for speedups super-linear in the
number of processors. Whether such speedups hold even when recomputation is
allowed remains an open question, which our new technique might help answer.
While we know that recomputation may reduce the I/O complexity of some
CDAGs, we are far from a characterization of those CDAGs for which recompu-
tation is eective. This broad goal remains a challenge for any attempt toward a
general theory of the communication requirements of computations.
References
1. Patterson, C.A., Snir, M., Graham, S.L.: Getting Up to Speed:: The Future of
Supercomputing. National Academies Press (2005)
2. Bilardi, G., Preparata, F.P.: Horizons of parallel computation. Journal of Parallel
and Distributed Computing 27(2) (1995) 172182
3. Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik 13(4)
(1969) 354356
4. Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proc. ACM
ISSAC, ACM (2014) 296303
5. Hong, J., Kung, H.: I/o complexity: The red-blue pebble game. In: Proc. ACM
STOC, ACM (1981) 326333
6. Cannon, L.E.: A cellular computer to implement the Kalman lter algorithm.
Technical report, DTIC Document (1969)
7. Ballard, G., Demmel, J., Holtz, O., Lipshitz, B., Schwartz, O.: Brief announce-
ment: strong scaling of matrix multiplication algorithms and memory-independent
communication lower bounds. In: Proc. ACM SPAA, ACM (2012) 7779
8. Irony, D., Toledo, S., Tiskin, A.: Communication lower bounds for distributed-
memory matrix multiplication. Journal of Parallel and Distributed Computing
64(9) (2004) 10171026
9. Scquizzato, M., Silvestri, F.: Communication lower bounds for distributed-memory
computations. arXiv preprint arXiv:1307.1805 (2013)
10. Pagh, R., Stockel, M.: The input/output complexity of sparse matrix multiplication.
In: Proc. ESA, Springer (2014) 750761
11. Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Minimizing communication in
numerical linear algebra. SIAM Journal on Matrix Analysis and Applications 32(3)
(2011) 866901
192 G. Bilardi and L. De Stefani
12. Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Communication-optimal parallel
and sequential Cholesky decomposition. SIAM Journal on Scientic Computing
32(6) (2010) 34953523
13. Loomis, L.H., Whitney, H.: An inequality related to the isoperimetric inequality.
Bull. Amer. Math. Soc. 55(10) (10 1949) 961962
14. V. A. Zalgaller, A. B. Sossinsky, Y.D.B. The American Mathematical Monthly
96(6) (1989) 544546
15. Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Graph expansion and communi-
cation costs of fast matrix multiplication. JACM 59(6) (2012) 32
16. Ballard, G., Demmel, J., Holtz, O., Lipshitz, B., Schwartz, O.: Graph expansion
analysis for communication costs of fast rectangular matrix multiplication. In:
Design and Analysis of Algorithms. Springer (2012) 1336
17. Scott, J., Holtz, O., Schwartz, O.: Matrix multiplication I/O complexity by Path
Routing. In: Proc. ACM SPAA. (2015) 3545
18. De Stefani, L.: On space constrained computations. PhD thesis, University of
Padova (2016)
19. Bilardi, G., Preparata, F.: Processor-time trade os under bounded speed message
propagation. Lower Bounds. Theory of Computing Systems 32(5) (1999) 531559
20. Ballard, G., Demmel, J., H., O., Lipshitz, B., Schwartz, O.: Communication-optimal
parallel algorithm for Strassens matrix multiplication. In: Proc. ACM SPAA. (2012)
193204
21. Jacob, R., Stockel, M.: Fast output-sensitive matrix multiplication. In: Proc. ESA.
Springer (2015) 766778
22. Savage, J.E.: Extending the Hong-Kung model to memory hierarchies. In: Com-
puting and Combinatorics. Springer (1995) 270281
23. Bilardi, G., Peserico, E.: A characterization of temporal locality and its portability
across memory hierarchies. In: Automata, Languages and Programming. Springer
(2001) 128139
24. Koch, R.R., Leighton, F.T., Maggs, B.M., Rao, S.B., Rosenberg, A.L., Schwabe,
E.J.: Work-preserving emulations of xed-connection networks. JACM 44(1) (1997)
104147
25. Bhatt, S.N., Bilardi, G., Pucci, G.: Area-time tradeos for universal VLSI circuits.
Theoret. Comput. Sci. 408(2-3) (2008) 143150
26. Bilardi, G., Pietracaprina, A., DAlberto, P.: On the space and access complexity of
computation DAGs. In: Graph-Theoretic Concepts in Computer Science, Springer
(2000) 4758
27. Grigorev, D.Y.: Application of separability and independence notions for proving
lower bounds of circuit complexity. Zapiski Nauchnykh Seminarov POMI 60 (1976)
3848
28. Savage, J.E.: Models of Computation: Exploring the Power of Computing. 1st edn.
Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA (1997)
29. Bilardi, G., Stefani, L.D.: The i/o complexity of strassens matrix multiplication
with recomputation. arXiv preprint arXiv:1605.02224 (2016)
30. Ranjan, D., Savage, J.E., Zubair, M.: Upper and lower I/O bounds for pebbling
r-pyramids. Journal of Discrete Algorithms 14 (2012) 212
31. Aggarwal, A., Vitter, Jerey, S.: The input/output complexity of sorting and
related problems. Commun. ACM 31(9) (September 1988) 11161127
32. Le Gall, F.: Faster algorithms for rectangular matrix multiplication. In: Proc. IEEE
FOCS, IEEE (2012) 514523
33. Thompson, C.: Area-time complexity for VLSI. In: Proc. ACM STOC, ACM (1979)
8188
Maximum Plane Trees in Multipartite
Geometric Graphs
1 Introduction
Let P be a set of n points in the plane in general position, i.e., no three points
are collinear. Let K(P ) be the complete geometric graph with vertex set P . It
is well known that the standard minimum spanning tree (MinST) problem in
K(P ) can be solved in (n log n) time. Also, any minimum spanning tree in
K(P ) is plane, i.e., its edges do not cross each other. The maximum spanning
tree (MaxST) problem is the problem of computing a spanning tree in K(P )
whose total edge length is maximum. Monma et al. [5] showed that this problem
1
Carleton University, Ottawa. Supported by NSERC. [email protected], kim-
[email protected], {jit, anil, michiel}@scs.carleton.ca
2
University of Ottawa, Ottawa. Supported by NSERC. [email protected]
3
University of California, Irvine. Supported by NSF grant CCF-1228639. epp-
[email protected]
2 Preliminaries
For any two points p and q in the plane, we refer to the line segment between
p and q as pq, and to the Euclidean distance between p and q as |pq|. The lune
between p and q, which we denote by lune(p, q), is the intersection of the two
disks of radius |pq| that are centered at p and q.
For a point set P , the diameter of P is the maximum Euclidean distance
between any two points of P . A pair of points that realizes the diameter of P is
referred to as a diametral pair.
Let G be a geometric graph with colored vertices. We denote by L(G) the
total Euclidean length of the edges of G. A star is a tree with one internal node,
which we refer to as the center of the star. For a color c, a c-star in G is a star
whose center is colored c and the colors of its leaves are dierent from c.
Proof. Let Cp and Cq be the two disks of radius |pq| that are centered at p and
q, respectively. Since (p, q) is a diameter of B, all blue points lie in lune(p, q);
see Figure 2(a).
r r
q
p q p q p q
1
f (r) p x
f (r) 1
f (r)
3
Cp Cq
s s
(a) (b) (c)
Fig. 2. Illustration of Lemmas 1 and 2: r is a red point, and p, q, f (r) are blue points.
For any red point r R, let f (r) denote its neighbor in FB . Recall that f (r)
is the farthest blue point to r, and note that f (r) is in lune(p, q). See Figure 2(a).
Maximum Plane Trees in Multipartite Geometric Graphs 197
We are going to show that |rf (r)| 23 (|rp| + |rq|). Depending on whether or
not r lune(p, q) we consider the following two cases.
r lune(p, q). Without loss of generality assume that pq has unit length, pq
is horizontal, r is above pq, and r is closer to q than to p. If f (r) is on or
above pq, then |rf (r)| is smaller than |pq|, and hence smaller than |rp| + |rq|.
Assume f (r) is below pq. Let s be the intersection point of the boundaries
of Cp and Cq that is below pq as in Figure 2(b).
Extend the line segment sp from the endpoint p. Let p be the point on the
extended line that is closest to r. Dene q similarly. Note that |rp | |rp|
and |rq | |rq|. Based on this and Claim 1, in order to show that |rf (r)|
2 (|rp| + |rq|), it suces to show that |rs| 2 (|rp | + |rq |). Let = rsq,
3 3
and note that 0 6 ; see Figure 2(c). Since the triangles rsp and
rsq are right-angled and spq is equilateral, we have |rq | = |rs| sin
and |rp | = |rs| sin(/3 ). Thus,
3
|rq | + |rp | = |rs| (sin + sin(/3 )) 2
|rs|,
where the inequality is valid because sin + sin(/3 ) is at least 3/2
for all 0 6 . This implies that |rs| 23 (|rp | + |rq |).
198 A. Biniaz et al.
Dene
$ $
f (x, ) = 1 + x2 2x cos(/3 ) + 1 + x2 2x cos x. (3)
EB , and EG form a forest in which each component is a red-star, a blue-star,
and a green-star, respectively. Let LR , LB , and LG denote the total lengths of
the edges of ER , EB , and EG , respectively. Let LE denote the total length of
the edges in E . Then,
L = LR + LB + LG + LE .
We consider the following two cases depending on where or not LE is larger than
max{LR , LB , LG }.
which implies that the longest of Sb and Sb has length at least 18 L .
The point set {p, q, r, r , b, b , g, g } can be computed in O(n log n) time, and thus,
the running time of the algorithm follows.
In this section we study the MaxPST problem, a special case of the Max-k-PST
problem where every input point has a unique color. Formally, given a set P
of points in the plane in general position and we want to compute a maximum
plane spanning tree in K(P ). We revisit this problem which was rst studied by
Alon, Rajagopalan and Suri (1993), and then by Dumitrescu and Toth (2010).
Alon et al. [1] presented an approximation algorithm with ratio 1/2 for this
problem. In fact they proved that the length of the longest star in K(P ) is at
least 0.5 times the length of an optimal tree; this bound is tight for a longest
star. Dumitrescu and Toth [4] improved the approximation ratio to 0.502. They
proved that the length of the longest double-star in K(P ) (a double-star is a tree
with two internal nodes) is at least 0.502 times the length of an optimal solution.
They left as an open problem a more precise