WALCOM: Algorithms and Computation

A graph is planar if it can be drawn or embedded in the plane so that no two edges intersect geometrically except at a vertex to which they are both incident. A plane graph is a planar graph with a fixed planar embedding in the plane. A drawing problem X for a plane graph G asks to determine whether G has a drawing D satisfying a set P of given properties and to find D if it exists. The corresponding problem for a planar graph G asks to determine whether G has a planar embedding \(\varGamma \) such that \(\varGamma \) has a drawing D satisfying the set P of properties and find D if it exists. If every embedding of G has a drawing D satisfying P, then the problem is trivial, i.e., the problem for plane graphs and that for planar graphs are the same. Otherwise, the problem for planar graphs becomes difficult even if an efficient solution of the problem for a plane graph exists since a planar graph may have an exponential number of planar embeddings. Various techniques are found in literature that are used to solve the drawing problems for planar graphs. In this paper we review three of the widely used techniques, namely, (i) reduction to planarity testing, (ii) incremental modification and (iii) SPQR-tree decomposition.

The Separator Theorem states that any planar graph G with n vertices has a separator of size \(O(\sqrt{n})\), that is, a set S of \(O(\sqrt{n})\) vertices of G such that by removing S, G is split into disconnected subgraphs of almost equal size, say, each having more than n/3 vertices. A separator algorithm is an algorithm that computes a separator for a given planar graph. We consider two algorithms that have been developed recently by the author and his colleagues [4, 6] for designing a “sublinear-space” and polynomial-time separator algorithm.

Galled trees are studied as a recombination model in theoretical population genetics. Tree-child networks, reticulation-visible networks and tree-based networks can be considered as the generalizations of galled trees through relaxing a structural condition. Although these networks are simple, their topological structures have yet to be fully understood. Here, recent progresses in the tree and cluster containment problems and network counting problems are summarized.

We consider a distributed system of \(n\ge 3\) opaque robots deployed in the Euclidean plane. If three robots lie on a line, the middle robot obstructs the visions of the two other robots. The mutual visibility problem requires the robots to form a configuration in which no three robots are collinear i.e., all the robots in the system are mutually visible. Robots work without any centralized control. We considers the FSTATE computational model in which each robot is endowed with an additional constant amount of persistent memory to retain some information of their previous states [3]. This information is not available to the other robots in the system. Except from this persistent memory, the robots are oblivious i.e., they do not carry forward any other information from their previous computational cycles. The robots do not have any explicit message passing capabilities. Under these weak settings, we present a deterministic distributed algorithm to solve the mutual visibility problem for a set of synchronous robots using only 1 bit of persistent memory. The proposed algorithm solves the mutual visibility problem in 2 rounds and guarantees collision-free movements for the robots. The algorithm is optimum in terms of round complexity, the amount of memory for the FSTATE computational model and number of movements for the robots.

Let P be an x-monotone orthogonal polygon with n vertices. We call P a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizontal chord from the left boundary to the right boundary. Two points p and q in P are co-visible if and only if the (axis-parallel) rectangle spanned by p and q completely lies in P. In the r-visibility graph G(P) of P, we connect two vertices of P with an edge if and only if they are co-visible. We consider routing with preprocessing in G(P). We may preprocess P to obtain a label and a routing table for each vertex of P. Then, we must be able to route a packet between any two vertices s and t of P, where each step may use only the label of the target node t, the routing table and the neighborhood of the current node, and the packet header. The routing problem has been studied extensively for general graphs, where truly compact and efficient routing schemes with polylogartihmic routing tables have turned out to be impossible. Thus, special graph classes are of interest.

We present a routing scheme for double histograms that sends any data packet along a path of length at most twice the (unweighted) shortest path distance between the endpoints. The labels, routing tables, and headers need \(O(\log n)\) bits. For the simple histograms, we obtain a routing scheme with optimal routing paths, \(O(\log n)\)-bit labels, one-bit routing tables, and no headers.

We address the problem of designing microfluidic chips for sample preparation, a crucial step in many experimental processes in chemical and biological sciences. One of the objectives of sample preparation is to dilute the sample fluid, called reactant, using another fluid called buffer, to produce desired volumes of fluid with prespecified reactant concentrations. In our model these fluids are manipulated in discrete volumes called droplets. The dilution process is represented by a mixing graph whose nodes represent 1–1 micro-mixers and edges represent channels for transporting fluids. We focus on designing such mixing graphs when the given sample (also referred to as the target) consists of a single-droplet, and the objective is to minimize total fluid waste. Our main contribution is an efficient algorithm called \(\texttt {RPRIS}\) that guarantees a better provable worst-case bound on waste and significantly outperforms state-of-the-art algorithms in experimental comparison.

A factor W of a string X is called a cover of X, if X can be constructed by concatenations and superpositions of W. Breslauer (IPL, 1992) proposed a well-known \(\mathcal {O}(n)\)-time algorithm that computes the shortest cover of every prefix of a string of length n. We show an \(\mathcal {O}(n \log n)\)-time algorithm that computes the shortest cover of every cyclic shift of a string and an \(\mathcal {O}(n)\)-time algorithm that computes the shortest among these covers. A related problem is the number of different lengths of shortest covers of cyclic shifts of the same string of length n. We show that this number is \(\varOmega (\log n)\).

We introduce and study the 1-planar packing problem: Given k graphs with n vertices \(G_1, \dots , G_k\), find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each \(G_i\) is a tree and \(k=3\). We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with \(n \ge 12\) vertices admits a 1-planar packing, while such a packing does not exist if \(n \le 10\).

Consider a graph with a rotation system, namely, for every vertex, a circular ordering of the incident edges. Given such a graph, an angle cover maps every vertex to a pair of consecutive edges in the ordering – an angle – such that each edge participates in at least one such pair. We show that any graph of maximum degree 4 admits an angle cover, give a poly-time algorithm for deciding if a graph with no degree-3 vertices has an angle-cover, and prove that, given a graph of maximum degree 5, it is NP-hard to decide whether it admits an angle cover. We also consider extensions of the angle cover problem where every vertex selects a fixed number \(a>1\) of angles or where an angle consists of more than two consecutive edges. We show an application of angle covers to the problem of deciding if the 2-blowup of a planar graph has isomorphic thickness 2.

Cartesian tree matching is the problem of finding all substrings in a given text which have the same Cartesian trees as that of a given pattern. In this paper, we deal with Cartesian tree matching for the case of multiple patterns. We present two fingerprinting methods, i.e., the parent-distance encoding and the binary encoding. By combining an efficient fingerprinting method and a conventional multiple string matching algorithm, we can efficiently solve multiple pattern Cartesian tree matching. We propose three practical algorithms for multiple pattern Cartesian tree matching based on the Wu-Manber algorithm, the Rabin-Karp algorithm, and the Alpha Skip Search algorithm, respectively. In the experiments we compare our solutions against the previous algorithm [18]. Our solutions run faster than the previous algorithm as the pattern lengths increase. Especially, our algorithm based on Wu-Manber runs up to 33 times faster.

Given a set of patterns called a dictionary and a text, the dictionary matching problem is a task to find all occurrence positions of all patterns in the text. The dictionary matching problem can be solved efficiently by using the Aho-Corasick algorithm. Recently, Matsuoka et al. [TCS, 2016] proposed a generalization of pattern matching problem under substring consistent equivalence relations and presented a generalization of the Knuth-Morris-Pratt algorithm to solve this problem. An equivalence relation \(\approx \) is a substring consistent equivalence relation (SCER) if for two strings X, Y, \(X \approx Y\) implies \(|X| = |Y|\) and \(X[i:j] \approx Y[i:j]\) for all \(1 \le i \le j \le |X|\). In this paper, we propose a generalization of the dictionary matching problem and present a generalization of the Aho-Corasick algorithm for the dictionary matching under SCER. We present an algorithm that constructs SCER automata and an algorithm that performs dictionary matching under SCER by using the automata. Moreover, we show the time and space complexity of our algorithms with respect to the size of input strings.

A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The k -Path Vertex Cover Reconfiguration (k -PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of k -PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: \(\mathsf {TS}\), \(\mathsf {TJ}\), and \(\mathsf {TAR}\). The problem for \(k=2\), known as the Vertex Cover Reconfiguration (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for k -PVCR. In particular, we prove a complexity dichotomy for k -PVCR on general graphs: on those whose maximum degree is 3 (and even planar), the problem is \(\mathtt {PSPACE}\)-complete, while on those whose maximum degree is 2 (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for k -PVCR on trees under each of \(\mathsf {TJ}\) and \(\mathsf {TAR}\). Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. The chromatic art gallery problem is to find a guard set for P such that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons with r-visibility when the number of colors is \(k=2\). Here, two points are r-visible if the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is an r-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is \(k=2\).

We study the Maximum Bipartite Subgraph (MBS) problem, which is defined as follows. Given a set S of n geometric objects in the plane, we want to compute a maximum-size subset \(S'\subseteq S\) such that the intersection graph of the objects in \(S'\) is bipartite. We first show that the \(\texttt {MBS}\) problem is \(\texttt {NP}\)-hard on geometric graphs for which the maximum independent set is \(\texttt {NP}\)-hard (hence, it is \(\texttt {NP}\)-hard even on unit squares and unit disks). On the algorithmic side, we first give a simple \(\mathcal {O}(n)\)-time algorithm that solves the \(\texttt {MBS}\) problem on a set of n intervals. Then, we give an \(\mathcal {O}(n^2)\)-time algorithm that computes a near-optimal solution for the problem on circular-arc graphs. Moreover, for the approximability of the problem, we first present a \(\texttt {PTAS}\) for the problem on unit squares and unit disks. Then, we present efficient approximation algorithms with small-constant factors for the problem on unit squares, unit disks and unit-height rectangles. Finally, we study a closely related geometric problem, called Maximum Triangle-free Subgraph (\({{\texttt {\textit{MTFS}}}}\)), where the objective is the same as that of \(\texttt {MBS}\) except the intersection graph induced by the set \(S'\) needs to be triangle-free only (instead of being bipartite).

The resolution of a drawing plays a crucial role when defining criteria for its quality. In the past, grid resolution, edge-length resolution, angular resolution and crossing resolution have been investigated. In this paper, we investigate the stub resolution, a recently introduced criterion for nonplanar drawings. A crossed edge is divided into parts, called stubs, which should not be too short for the sake of readability. Thus, the stub resolution of a drawing is defined as the minimum ratio between the length of a stub and the length of the entire edge, over all the edges of the drawing. We consider 1-planar graphs and we explore scenarios in which near optimal stub resolution, i.e. arbitrarily close to \(\frac{1}{2}\), can be obtained in drawings with zero, one, or two bends per edge, as well as further resolution criteria, such as angular and crossing resolution. In particular, our main contributions are as follows: (i) Every 1-planar graph with independent crossing edges has a straight-line drawing with near optimal stub resolution; (ii) Every 1-planar graph has a 1-bend drawing with near optimal stub resolution.

The dispersion problem on graphs asks \(k\le n\) robots initially placed arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to many other fundamental robot coordination problems, such as exploration, scattering, load balancing, relocation of self-driven electric cars (robots) to recharge stations (nodes), etc. The objective in this problem is to simultaneously minimize (or provide trade-off between) two fundamental performance metrics: (i) time to achieve dispersion and (ii) memory requirement at each robot. The existing algorithms for trees and arbitrary graphs either minimize time or memory but not both. In this paper, we consider for the very first time the dispersion problem on a grid graph embedded in the Euclidean plane and present solutions that simultaneously minimize both the metrics. The grid graph is appealing as it naturally discretizes the 2-dimensional Euclidean plane and finds applications in many real-life robotic systems. Particularly, we provide two deterministic algorithms on an anonymous grid graph that achieve simultaneously optimal bounds for both the metrics.

We study three fundamental geometric optimization problems – independent set, piercing set, and dominating set – on sets of axis-parallel segments in the plane. We consider special cases in which the segments are either unit length or they are anchored on an inclined line (a line with slope \(-1\)). When the segments are anchored on both sides, we prove that all three problems are NP-complete (Throughout, we refer to NP-completeness of problems, as the decision versions of the NP-hard optimization problems we consider are all readily seen to be in NP.); NP-completeness was known for the corresponding problems with axis-parallel rectangles anchored on an inclined line (Correa et al. [4], Mudgal and Pandit [9], Pandit [10]). Further, we prove that the dominating set problem with unit segments in the plane is NP-complete. When the input segments are anchored on one side of the inclined line, there are polynomial-time algorithms for the independent set and piercing set problems.

Given graphs G and H, we propose a method to implicitly enumerate topological-minor-embeddings of H in G using decision diagrams. We show a useful application of our method to enumerating subgraphs characterized by forbidden topological minors, that is, planar, outerplanar, series-parallel, and cactus subgraphs. Computational experiments show that our method can find all planar subgraphs in a given graph at most five orders of magnitude faster than a naive backtracking-based method.

In the Partition Into Complementary Subgraphs (Comp-Sub) problem we are given a graph \(G=(V,E)\), and an edge set property \(\varPi \), and asked whether G can be decomposed into two graphs, H and its complement \(\overline{H}\), for some graph H, in such a way that the edge cut-set (of the cut) \([V(H),V(\overline{H})]\) satisfies property \(\varPi \). Such a problem is motivated by the fact that several parameterized problems are trivially fixed-parameter tractable when the input graph G is decomposable into two complementary subgraphs. In addition, it generalizes the recognition of complementary prism graphs, and it is related to graph isomorphism when the desired cut-set is empty, Comp-Sub(\(\emptyset \)). In this paper we are particularly interested in the case \(\textsc {Comp}\)-\(\textsc {Sub}(\emptyset )\), where the decomposition also partitions the set of edges of G into E(H) and \(E(\overline{H})\). We show that \(\textsc {Comp}\)-\(\textsc {Sub}(\emptyset )\) is \(\mathsf{GI}\)-complete on chordal graphs, but it becomes more tractable than Graph Isomorphism for several subclasses of chordal graphs. We present structural characterizations for split, starlike, block, and unit interval graphs. We also obtain complexity results for permutation graphs, cographs, comparability graphs, co-comparability graphs, interval graphs, co-interval graphs and strongly chordal graphs. Furthermore, we present some remarks when \(\varPi \) is a general edge set property and the case when the cut-set M induces a complete bipartite graph.

Given a set of edge pairs in a bipartite graph, we want to find a bipartite matching that includes a maximum number of those edge pairs. While the problem has many applications to wireless localization, to the best of our knowledge, there is no theoretical work for the problem. In this work, unless \(P = NP\), we show that there is no constant approximation for the problem. Suppose that k denotes the maximum number of input edge pairs such that a particular node can be in. Inspired by experimental results, we consider the case that k is small. While there is a simple polynomial-time algorithm for the problem when k is one, we show that the problem is NP-hard when k is greater than one. We also devise an efficient O(k)-approximation algorithm for the problem.

An r-partite tournament is a directed graph obtained by assigning a unique orientation to each edge of a complete undirected r-partite simple graph. Given a bipartite tournament T on n vertices, we explore the parameterized complexity of the problem of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k. Although the maximization version of this problem can be seen as the linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in bipartite tournaments, surprisingly no algorithmic results seem to exist. We show that this problem can be solved in \(2^{\mathcal {O}(k \log k)} n^{\mathcal {O}(1)}\) time and admits a kernel with \(\mathcal {O}(k^2)\) vertices.

Let \(S\subset [0,1]^2\) be a set of n points, randomly and uniformly selected. Let \(R\cup B\) be a random partition, or coloring, of S in which each point of S is included in R uniformly at random with probability 1/2. We study the random variable M(n) equal to the number of points of S that are covered by the rectangles of a maximum strong matching of S with axis-aligned rectangles. The matching consists of closed rectangles that cover exactly two points of S of the same color. A matching is strong if all its rectangles are pairwise disjoint. We prove that almost surely \(M(n)\ge 0.83\,n\) for n large enough. Our approach is based on modeling a deterministic greedy matching algorithm, that runs over the random point set, as a Markov chain.

Various network systems such as communication networks require survivability that is tolerance of attacks, failures, and accidents. Designing a network with high survivability is formulated as a survivable network design problem (SNDP). The input of the SNDP is a pair of an edge-weighted graph and a requirement of topology and survivability. For an edge subset of the graph, if it satisfies the requirement, we call it a desired edge subset (DES). The output of the SNDP is the minimum weight DES. Although the SNDP is an optimization problem, to simply solve it is not always desired in terms of the practical use: Designers sometimes want to test multiple DESs including non-optimal DESs, because the theoretical optimal DES is not always the practical best.

In this paper, instead of the optimization, we propose a method to enumerate all DESs with a compact data structure, called the zero-suppressed binary decision diagram (ZDD). Obtained ZDDs support practical network design by performing optimization, sampling, and filtering of DESs. The proposed method combines two typical techniques constructing ZDDs, called the frontier-based search (FBS) and the family algebra, and includes a novel operation on ZDDs. We demonstrate that our method works on various real-world instances of practical scales.

Given a graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G, if it exists. This problem is known to be NP-hard for bipartite planar graphs. In this paper, we study the approximability of the problem. We first show that, for any fixed \(\varepsilon > 0\), unless \(\mathrm{P} = \mathrm{NP}\), there exists no polynomial-time \(n^{1-\varepsilon }\)-approximation algorithm even for bipartite planar graphs. This gives a contrast to the existence of a polynomial-time 2-approximation algorithm for the original feedback vertex set problem on general graphs. We then give an \(\alpha (\mathrm{\Delta }-1)/2\)-approximation algorithm for bipartite graphs G of maximum degree \(\mathrm{\Delta }\), which runs in \(O(t(G)+\mathrm{\Delta }n)\) time, under the assumption that there is an \(\alpha \)-approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in O(t(G)) time.

Recently, a general framework for enumerating every element in a graph class was given. The main feature of this framework was that it was designed to enumerate only non-isomorphic graphs in a graph class. Applying this framework to the classes of interval graphs and permutation graphs, we gave efficient enumeration algorithms for these graph classes such that each element in the class was output in polynomial time delay. In this paper, we investigate the class of Ptolemaic graphs that consists of graphs that satisfy Ptolemy inequality for the distance. From the viewpoint of graph classes, it is an intersection of the class of chordal graphs and the class of distance-hereditary graphs. To enumerate Ptolemaic graphs, we need more tricks for applying the general framework. We develop an efficient enumeration algorithm for non-isomorphic Ptolemaic graphs.

We consider an efficient two-party protocol for securely computing the similarity of strings w.r.t. an extended edit distance measure. Here, two parties possessing strings x and y, respectively, want to jointly compute an approximate value for \(\mathrm {EDM}(x,y)\), the minimum number of edit operations including substring moves needed to transform x into y, without revealing any private information. Recently, the first secure two-party protocol for this was proposed, based on homomorphic encryption, but this approach is not suitable for long strings due to its high communication and round complexities. In this paper, we propose an improved algorithm that significantly reduces the round complexity without sacrificing its cryptographic strength. We examine the performance of our algorithm for DNA sequences compared to previous one.

In this paper we introduce the Maximum Happy Set problem (MaxHS) and study its parameterized complexity: For an undirected graph \(G = (V, E)\) and a subset \(S\subseteq V\) of vertices, a vertex v is happy if v and all its neighbors are in S; and otherwise unhappy. Given an undirected graph \(G = (V, E)\) and an integer k, the goal of MaxHS is to find a subset \(S\subseteq V\) of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard when parameterized by k. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by the tree-width, the clique-width and k, the neighborhood diversity, or the twin-cover number.

A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. The 1-planarity testing problem is NP-complete, even for restricted classes of graphs. We present the first general 1-planarity testing and embedding algorithm, and we experimentally investigate its feasibility in practice. The results suggest that our approach can be successfully applied to graphs with up to 30 vertices, while more sophisticated techniques are needed to attack larger graphs.

In this paper, we consider the reconfiguration problem of integer linear systems. In this problem, we are given an integer linear system I and two feasible solutions \(\varvec{s}\) and \(\varvec{t}\) of I, and then asked to transform \(\varvec{s}\) to \(\varvec{t}\) by changing a value of only one variable at a time, while maintaining a feasible solution of I throughout. Z(I) for I is the complexity index introduced by Kimura and Makino (Discrete Applied Mathematics 200:67–78, 2016), which is defined by the sign pattern of the input matrix. We analyze the complexity of the reconfiguration problem of integer linear systems based on the complexity index Z(I) of given I. We show that the problem is (i) solvable in constant time if Z(I) is less than one, (ii) weakly coNP-complete and pseudo-polynomially solvable if Z(I) is exactly one, and (iii) PSPACE-complete if Z(I) is greater than one. Since the complexity indices of Horn and two-variable-par-inequality integer linear systems are at most one, our results imply that the reconfiguration of these systems are in coNP and pseudo-polynomially solvable. Moreover, this is the first result that reveals coNP-completeness for a reconfiguration problem, to the best of our knowledge.

We introduce the Train Scheduling Problem which can be described as follows: Given m trains via their tracks, i.e., curves in the plane, and the trains’ lengths, we want to compute a schedule that moves collision-free and with limited speed the trains along their tracks such that the maximal travel time is minimized. We prove that there is no FPTAS for the Train Scheduling Problem unless P = NP. Furthermore, we provide near-optimal runtime algorithms extending existing schedules.