WALCOM: Algorithms and Computation

The social standing of individuals in a social network is typically determined locally according to the individual’s neighborhood or by a comparison between the individual and its neighbors. In this paper, we consider various criteria that measure social status and the extent in which individuals are satisfied with their social status. We study these criteria from the point of view of network realization: given a satisfaction specification, decide whether there exists a network realizing this specification.

Parameterized complexity is one of the most established algorithmic paradigms to deal with computationally hard problems. In the first two decades, the field largely focused on problems arising from studies of graphs and networks. However, lately the focus has changed substantially and it has started to permeate into other fields such as computational geometry, and computational social choice theory. In this article, we will survey some exciting developments in the emerging field of parameterized computational geometry through our contributions. We will focus on designing efficient parameterized algorithms on unit-disk graphs via new graph decomposition theorems.

Let C be a set of n customers and F be a set of m facilities. An r-gather clustering of C is a partition of the points in clusters such that each cluster contains at least r points. The r-gather clustering problem asks to find an r-gather clustering which minimizes the maximum distance between any two points in a cluster. An r-gathering of C is an assignment of each customer $$c \in C$$ to a facility $$f \in F$$ such that each open facility has zero or at least r customers. The r-gathering problem asks to find an r-gathering that minimizes the maximum distance between a customer and its facility. In this work we consider the r-gather clustering and r-gathering problems when the customers and the facilities are lying on a “star”. We show that the r-gather clustering problem and the r-gathering problem with points on a star with d rays can be solved in $$O(rn+(r+1)^ddr)$$ and $$O(n+r^2 m + d^2r^2 (d+\log m)+(r+1)^d2^d(r +d)d)$$ time respectively.

We study the k-center problem in a kinetic setting: given a set of continuously moving points P in the plane, determine a set of k (moving) disks that cover P at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model is very hard to work with. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of k-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution—the topological stability ratio—considering various metrics and various optimization criteria. For $$k = 2$$ we provide tight bounds, and for small $$k > 2$$ we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant k.

In this paper, we revisit the r-gathering problem. Given sets C and F of points on the plane and distance d(c, f) for each $$c \in C$$ and $$f\in F$$ , an r-gathering of C to F is an assignment A of C to open facilities $$F' \subseteq F$$ such that r or more members of C are assigned to each open facility. The cost of an r-gathering is $$\max _{c \in C}{d(c, A(c))}$$ . The r-gathering problem computes the r-gathering minimizing the cost. In this paper we study the r-gathering problem when C and F are on a line and present a $$O(|C| + |F|)$$ -time algorithm to solve the problem. Our solution is optimal since any algorithm needs to read C and F at least once.

An annulus is, informally, a ring-shaped region, often described by two concentric circles. The maximum-width empty annulus problem asks to find an annulus of a certain shape with the maximum possible width that avoids a given set of n points in the plane. This problem can also be interpreted as the problem of finding an optimal location of a ring-shaped obnoxious facility among the input points. In this paper, we study square and rectangular variants of the maximum-width empty anuulus problem, and present first nontrivial algorithms. Specifically, our algorithms run in $$O(n^3)$$ and $$O(n^2 \log n)$$ time for computing a maximum-width empty axis-parallel square and rectangular annulus, respectively. Both algorithms use only O(n) space.

In this work we study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we identify restrictions to the problem where it either remains NP-complete or has a polynomial time algorithm. First, we characterize the possibility of when an Aztec rectangle has an L-tromino tiling, and hence also an Aztec diamond; if an Aztec rectangle has an unknown number of defects or holes, however, the problem of deciding a tiling is NP-complete. Then, we study tilings of arbitrary regions where only $$180^\circ $$ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete; yet, if a region does not contain so-called “forbidden polyominoes” as subregions, then there exists a polynomial time algorithm for deciding a tiling.

We present the prefix Fréchet similarity as a new measure for similarity of curves which is e.g. motivated by evacuation analysis and defined as follows. Given two (polygonal) curves T and $$T'$$ , we ask for two prefix curves of T and $$T'$$ which have a Fréchet distance no larger than a given distance threshold $$\delta \ge 0$$ w.r.t. $$L_1$$ metric such that the sum of the prefix curves is maximal. As parameterized Fréchet measures as, e.g., the prefix Fréchet similarity are highly unstable w.r.t. to the value of the distance threshold $$\delta $$ , we give an algorithm that computes exactly the profile of the prefix Fréchet similarity, i.e., the complete functional relation between $$\delta $$ and the prefix Fréchet similarity of T and $$T'$$ . This is the first efficient algorithm for computing exactly the whole profile of a parametrized Fréchet distance.While the running time of our algorithm for computing the profile of the prefix Fréchet similarity is $$\mathcal {O}\left( n^3 \log n\right) $$ , we provide a lower bound of $$\varOmega (n^2)$$ for the running time of each algorithm computing the profile of the prefix Fréchet similarity, where n denotes the number of segments on T and $$T'$$ . This implies that our running time is at most a near linear factor away from being optimal.

Simple heuristics often show a remarkable performance in practice for optimization problems. Worst-case analysis often falls short of explaining this performance. Because of this, “beyond worst-case analysis” of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms.The instances of many optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained by Bringmann et al. (Algorithmica, 2013), who have used random shortest path metrics on complete graphs to analyze heuristics.The goal of this paper is to generalize these findings to non-complete graphs, especially Erdős–Rényi random graphs. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances, we prove that the greedy heuristic for the minimum distance maximum matching problem, the nearest neighbor and insertion heuristics for the traveling salesman problem, and a trivial heuristic for the k-median problem all achieve a constant expected approximation ratio. Additionally, we show a polynomial upper bound for the expected number of iterations of the 2-opt heuristic for the traveling salesman problem.

We study the problem to find a partition of a graph G with maximum social welfare based on social distance between vertices in G, called MaxSWP. This problem is known to be NP-hard in general. In this paper, we first give a complete characterization of optimal partitions of trees with small diameters. Then, by utilizing these results, we show that MaxSWP can be solved in linear time for trees. Moreover, we show that MaxSWP is NP-hard even for 4-regular graphs.

In this paper, we propose three conclusions for 1 × n maps with square/diagonal grid patterns. First, for a 1 × n map consisting of all the vertical creases and all the diagonal creases as well as a mountain-valley assignment, if it obeys the local flat-foldability, then it can always be globally flat-folded and one of its flat-folded state can be reached in O(n) time. Second, for a 1 × n map consisting of only square/diagonal grid pattern, it also can always be globally flat-folded and one of its flat-foldable state can be reached in O(n) time. We give theoretical proofs for both of them and propose corresponding algorithms. Then, we prove the NP-hardness of the problem of determining the global flat-foldability for a 1 × n map consisting of a square/diagonal grid pattern and a specific mountain-valley assignment. Also, we show that given an order of the faces for an m × n map with all the vertical creases and all the diagonal creases assigned to be mountains or valleys, we can determine its validity in O(mn) time.

We present a new model for hybrid planarity that relaxes existing hybrid representations. A graph $$G = (V,E)$$ is (k, p)-planar if V can be partitioned into clusters of size at most k such that G admits a drawing where: (i) each cluster is associated with a closed, bounded planar region, called a cluster region; (ii) cluster regions are pairwise disjoint, (iii) each vertex $$v \in V$$ is identified with at most p distinct points, called ports, on the boundary of its cluster region; (iv) each inter-cluster edge $$(u,v) \in E$$ is identified with a Jordan arc connecting a port of u to a port of v; (v) inter-cluster edges do not cross or intersect cluster regions except at their endpoints. We first tightly bound the number of edges in a (k, p)-planar graph with $$p<k$$ . We then prove that (4, 1)-planarity testing and (2, 2)-planarity testing are NP-complete problems. Finally, we prove that neither the class of (2, 2)-planar graphs nor the class of 1-planar graphs contains the other, indicating that the (k, p)-planar graphs are a large and novel class.

Let $$G=(V, E)$$ be a planar graph and let $$\mathcal V$$ be a partition of V. We refer to the graphs induced by the vertex sets in as clusters. Let $$\mathcal {D}_{\mathcal C}$$ be an arrangement of disks with a bijection between the disks and the clusters. Akitaya et al. [2] give an algorithm to test whether can be embedded onto $$\mathcal {D}_{\mathcal C}$$ with the additional constraint that edges are routed through a set of pipes between the disks. Based on such an embedding, we prove that every clustered graph and every disk arrangement without pipe-disk intersections has a planar straight-line drawing where every vertex is embedded in the disk corresponding to its cluster. This result can be seen as an extension of the result by Alam et al. [3] who solely consider biconnected clusters. Moreover, we prove that it is $$\mathcal {NP} $$ -hard to decide whether a clustered graph has such a straight-line drawing, if we permit pipe-disk intersections.

A vertex set $$U \subseteq V$$ of an undirected graph $$G=(V,E)$$ is a resolving set for G, if for every two distinct vertices $$u,v \in V$$ there is a vertex $$w \in U$$ such that the distance between u and w and the distance between v and w are different. The Metric Dimension of G is the size of a smallest resolving set for G. Deciding whether a given graph G has Metric Dimension at most k for some integer k is well-known to be NP-complete. A lot of research has been done to understand the complexity of this problem on restricted graph classes. In this paper, we decompose a graph into its so called extended biconnected components and present an efficient algorithm for computing the metric dimension for a class of graphs having a minimum resolving set with a bounded number of vertices in every extended biconnected component. Furthermore, we show that the decision problem Metric Dimension remains NP-complete when the above limitation is extended to usual biconnected components.

Let $$G=(V,E)$$ be a simple graph. A vertex $$v\in V$$ ve-dominates every edge uv incident to v, as well as every edge adjacent to these incident edges. A set $$D\subseteq V$$ is a double vertex-edge dominating set if every edge of E is ve-dominated by at least two vertices of D. The double vertex-edge dominating problem is to find a minimum double vertex-edge dominating set of G. In this paper, we show that minimum double vertex-edge dominating problem is NP-complete for chordal graphs. A linear time algorithm to find the minimum double vertex-edge dominating set for proper interval graphs is proposed. We also show that the minimum double vertex-edge domination problem cannot be approximated within $$(1-\varepsilon )\ln |V|$$ for any $$\varepsilon >0$$ unless NP $$\subseteq $$ DTIME $$(|V|^{O(\log \log |V|)})$$ . Finally, we prove that the minimum double vertex-edge domination problem is APX-complete for graphs with maximum degree 5.

If the degree of every vertex of a connected graph is even, then the graph has a circuit that contains all of edges, namely an Eulerian circuit. If the length of a shortest subcycle of an Eulerian circuit of a given graph is the largest, then the length is called the Eulerian recurrent length of the graph. For an odd integer n greater than or equal to 3, e(n) denotes the Eulerian recurrent length of $$K_n$$ , the complete graph with n vertices. Values e(n) for all odd integers n with $$3\leqq n\leqq 13$$ have been found by verification experiments using computers. If n is 7, 9, 11, or 13, then $$e(n) = n - 3$$ holds, for example. On the other hand, it has been shown that $$n - 4\leqq e(n)\leqq n - 2$$ holds for any odd integer n greater than or equal to 15 in previous researches. In this paper, it is proved that $$e(n)\leqq n - 3$$ holds for every odd integer n greater than or equal to 15. In the core part of the proof of the main theorem, an IP (integer programming) solver is used as the amount of computation is too large to be solved by hand.

In this paper, we consider the feasibility problem of integer linear systems where each inequality has at most two variables. Although the problem is known to be weakly NP-complete by Lagarias, it has many applications and, importantly, a large subclass of it admits (pseudo-)polynomial algorithms. Indeed, the problem is shown pseudo-polynomially solvable if every variable has upper and lower bounds by Hochbaum, Megiddo, Naor, and Tamir. However, determining the complexity of the general case, pseudo-polynomially solvable or strongly NP-complete, is a longstanding open problem. In this paper, we reveal a new efficiently solvable subclass of the problem. Namely, for the monotone case, i.e., when two coefficients of the two variables in each inequality are opposite signs, we associate a directed graph to any instance, and present an algorithm that runs in $$O(n \cdot s \cdot 2^{O(\ell \log \ell )} + n + m)$$ time, where s is the length of the input and $$\ell $$ is the maximum number of the vertices in any strongly connected component of the graph. If $$\ell $$ is a constant, the algorithm runs in polynomial time. From the result, it can be observed that the hardness of the feasibility problem lies on large strongly connected components of the graph.

In this paper, we introduce and study the multilevel-planarity testing problem, which is a generalization of upward planarity and level planarity. Let $$G = (V, E)$$ be a directed graph and let $$\ell : V \rightarrow \mathcal P(\mathbb Z)$$ be a function that assigns a finite set of integers to each vertex. A multilevel-planar drawing of G is a planar drawing of G such that the y-coordinate of each vertex $$v \in V$$ is $$y(v) \in \ell (v)$$ , and each edge is drawn as a strictly y-monotone curve.We present linear-time algorithms for testing multilevel planarity of embedded graphs with a single source and of oriented cycles. Complementing these algorithmic results, we show that multilevel-planarity testing is NP-complete even in very restricted cases.

Optimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum maximal solution (resp. maximum minimal solution). Such “flipping” of the objective function was done for many classical optimization problems. For example, Minimum Vertex Cover becomes Maximum Minimal Vertex Cover, Maximum Independent Set becomes Minimum Maximal Independent Set and so on. In this paper, we propose to study the weighted version of Maximum Minimal Edge Cover called Upper Edge Cover, a problem having application in genomic sequence alignment. It is well-known that Minimum Edge Cover is polynomial-time solvable and the “flipped” version is NP-hard, but constant approximable. We show that the weighted Upper Edge Cover is much more difficult than Upper Edge Cover because it is not $$O(\frac{1}{n^{1/2-\varepsilon }})$$ approximable, nor $$O(\frac{1}{\varDelta ^{1-\varepsilon }})$$ in edge-weighted graphs of size n and maximum degree $$\varDelta $$ respectively. Indeed, we give some hardness of approximation results for some special restricted graph classes such as bipartite graphs, split graphs and k-trees. We counter-balance these negative results by giving some positive approximation results in specific graph classes.

The automaton constrained tree knapsack problem is a variant of the knapsack problem in which the items are associated with the vertices of the tree, and we can select a subset of items that is accepted by a tree automaton. If the capacities or the profits of items are integers, it can be solved in pseudo-polynomial time by the dynamic programming algorithm. However, this algorithm has a quadratic pseudo-polynomial factor in its complexity because of the max-plus convolution. In this study, we propose a new dynamic programming technique, called heavy-light recursive dynamic programming, to obtain algorithms having linear pseudo-polynomial factors in the complexity. Such algorithms can be used for solving the problems with polynomially small capacities/profits efficiently, and used for deriving efficient fully polynomial-time approximation schemes. We also consider the k-subtree version problem that finds k disjoint subtrees and a solution in each subtree that maximizes total profit under a budget constraint. We show that this problem can be solved in almost the same complexity as the original problem.

We give approximation algorithms for matching two sets of line segments in constant dimension. We consider several versions of the problem: Hausdorff distance, bottleneck distance and largest common point set. We study these similarity measures under several sets of transformations: translations, rotations about a fixed point and rigid motions. As opposed to previous theoretical work on this problem, we match segments individually, in other words we regard our two input sets as sets of segments rather than unions of segments.

For a given polygon P and a polyhedron Q, the folding problem asks if Q can be obtained from P by folding it. This simple problem is quite complicated, and there is no known efficient algorithm that solves this problem in general. In this paper, we focus on the case that Q is a box, and the size of Q is not given. That is, input of the box folding problem is a polygon P, and it asks if P can fold to boxes of certain sizes. We note that there exist an infinite number of polygons P that can fold into three boxes of different sizes. In this paper, we give a pseudo polynomial time algorithm that computes all possible ways of folding of P to boxes.

With the advent of quantum computers, researchers are exploring if quantum mechanics can be leveraged to solve important problems in ways that may provide advantages not possible with conventional or classical methods. A previous work by O’Malley and Vesselinov in 2016 briefly explored using a quantum annealing machine for solving linear least squares problems for real numbers. They suggested that it is best suited for binary and sparse versions of the problem. In our work, we propose a more compact way to represent variables using two’s and one’s complement on a quantum annealer. We then do an in-depth theoretical analysis of this approach, showing the conditions for which this method may be able to outperform the traditional classical methods for solving general linear least squares problems. Finally, based on our analysis and observations, we discuss potentially promising areas of further research where quantum annealing can be especially beneficial.

Consensus tree is a phylogenetic tree that summarizes the branching information of a set of conflicting phylogenetic trees. Computing consensus tree is a major step in phylogenetic tree reconstruction. It also finds application in predicting a species tree from a set of gene trees. Here, we focus our study on one of the most frequently used consensus tree problem, called greedy consensus tree problem. Given k phylogenetic trees leaf-labeled by n taxa, previous best known algorithm for constructing a greedy consensus tree of these k trees runs in $$O(k n^{1.5} \log n)$$ time. Here, we describe an $$O(k^2 n)$$ -time solution. Our method is the fastest when $$k = O(\sqrt{n} \log n)$$ .Existing greedy consensus tree methods may not report the most resolved greedy consensus tree. Here, we propose a new computational problem called the maximum greedy consensus tree problem that aims to find the most resolved greedy consensus tree. We showed that this problem is NP-hard for $$k \ge 3$$ . We also give a polynomial time solution when $$k=2$$ and an approximation algorithm for $$k=3$$ .

We are studying the adaptive bitprobe model to store an arbitrary subset S of size at most five from a universe of size m and answer the membership queries of the form “Is x in S?” in two bitprobes. In this paper, we present a data structure for the aforementioned problem. Our data structure takes $$\mathcal {O}(m^{10/11})$$ space. This result improves the non-explicit result by Garg and Radhakrishnan [6] which takes $$\mathcal {O}(m^{20/21})$$ space, and the explicit result by Garg [5] which takes $$\mathcal {O}(m^{18/19})$$ space for the aforementioned set and query sizes.

V-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental V-comparison of strings can be done in linear time and constant space. V-order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and the Lyndon factorization, we in this paper make a first attempt to obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and the Lyndon factorization are matched by analogous V-order processing. We then apply the V-BWT to implement pattern matching in V-order after suitably modifying the FM-index.

Parallel parameterized complexity theory studies how fixed-parameter tractable (fpt) problems can be solved in parallel. Previous theoretical work focused on parallel algorithms that are very fast in principle, but did not take into account that when we only have a small number of processors (between 2 and, say, 1024), it is more important that the parallel algorithms are work-efficient. In the present paper we investigate how work-efficient fpt algorithms can be designed. We review standard methods from fpt theory, like kernelization, search trees, and interleaving, and prove trade-offs for them between work efficiency and runtime improvements. This results in a toolbox for developing work-efficient parallel fpt algorithms.

The Arbitrary Pattern Formation problem asks to design a distributed algorithm that allows a set of autonomous mobile robots to form any specific but arbitrary geometric pattern given as input. The problem has been extensively studied in literature in continuous domains. This paper investigates a discrete version of the problem where the robots are operating on a two dimensional infinite grid. The robots are assumed to be autonomous, identical, anonymous and oblivious. They operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not agree on any common global coordinate system or chirality. We have shown that a set of robots can form any arbitrary pattern, if their starting configuration is asymmetric.

In this article, we consider the problem of finding in three dimensions a minimum volume axis-parallel box into which a given set of unit size disks can be packed under translations. The problem is neither known to be NP-hard nor to be in NP. We give a constant factor approximation algorithm based on reduction to finding a shortest Hamiltonian path in a weighted graph. As a byproduct, we can show that there is no finite size container into which all unit disks can be packed simultaneously.

We study a class of geometric covering and packing problems for bounded closed regions on the plane. We are given a set of axis-parallel line segments that induce a planar subdivision with bounded (rectilinear) faces. We are interested in the following problems. (P1) Stabbing-Subdivision: Stab all closed bounded faces by selecting a minimum number of points in the plane. (P2) Independent-Subdivision: Select a maximum size collection of pairwise non-intersecting closed bounded faces. (P3) Dominating-Subdivision: Select a minimum size collection of bounded faces such that every other face has a non-empty intersection (i.e., sharing an edge or a vertex) with some selected face. We show that these problems are $$\mathsf { NP }$$ -hard. We even prove that these problems are $$\mathsf { NP }$$ -hard when we concentrate only on the rectangular faces of the subdivision. Further, we provide constant factor approximation algorithms for the Stabbing-Subdivision problem.

Set cover is a well-studied problem with application in many fields. A well-known variation of this problem is the Minimum Membership Set Cover problem. In this problem, given a set of points and a set of objects, the objective is to cover all points while minimizing the maximum number of objects that contain any one point. A dual of this problem is the Minimum Membership Hitting Set problem. In this problem, given a set of points and a set of objects, the objective is to stab all of the objects while minimizing the maximum number of points that an object contains. We study both of these variations in a geometric setting with various types of geometric objects in the plane, including axis-parallel line segments, axis-parallel strips, rectangles that are anchored on a horizontal line from one side, rectangles that are stabbed by a horizontal line, and rectangles that are anchored on one of two horizontal lines (i.e., each rectangle shares at least one boundary edge (top or bottom) with one of the input horizontal lines). For each of these problems either we prove NP-hardness or design a polynomial-time algorithm. More precisely, we show that it is NP-complete to decide whether there exists a solution with depth exactly 1 for either the Minimum Membership Set Cover or the Minimum Membership Hitting Set problem. We also provide approximation algorithms for some of the problems. In addition, we study a generalized version of the Minimum Membership Hitting Set problem.

Consider a capacitated version of the discrete unit disk cover problem as follows: consider a set $$P= \{p_1,p_2, \cdots ,p_n\}$$ of n customers and a set $$Q=\{q_1,q_2, \cdots ,q_m\}$$ of m service centers. A service center can provide service to at most $$\alpha ( \in \mathbb {N})$$ number of customers. Each $$q_i \in Q$$ $$(i=1,2, \cdots ,m)$$ has a preassigned set of customers to which it can provide service. The objective of the capacitated covering problem is to provide service to each customer in P by at least one service center in Q. In this paper, we consider the geometric version of the capacitated covering problem, where the set of customers and set of service centers are two point sets in the Euclidean plane. A service center can provide service to a customer if their Euclidean distance is less than or equal to 1. We call this problem as $$(\alpha , P, Q)$$ -covering problem. For the $$(\alpha , P, Q)$$ -covering problem, we propose an $$O(\alpha mn(m+n))$$ time algorithm to check feasible solution for a given instance. We also prove that the $$(\alpha , P, Q)$$ -covering problem is NP-complete for $$\alpha \ge 3$$ and it admits a PTAS.