Search

Given a road network modelled as a planar straight-line graph $G=(V,E)$ with $|V|=n$, let $(u,v)\in V\times V$, the shortest path (distance) between $u,v$ is denoted as $\delta_G(u,v)$. Let $\delta(G)=\max_{(u,v)}\delta_G(u,v)$, for $(u,v)\in V\times V$, which is called the diameter of $G$. Given a disconnected road network modelled as two disjoint trees $T_1$ and $T_2$, this paper first aims at inserting one and two edges (bridges) between them to minimize the (constrained) diameter $\delta(T_1\cup T_2\cup I_j)$ going through the inserted edges, where $I_j, j=1,2$, is the set of inserted edges with $|I_1|=1$ and $|I_2|=2$. The corresponding problems are called the {\em optimal bridge} and {\em twin bridges} problems. Since when more than one edge are inserted between two trees the resulting graph is becoming more complex, for the general network $G$ we consider the problem of inserting a minimum of $k$ edges such that the shortest distances between a set of $m$ pairs $P=\{(u_i,v_i)\mid u_i,v_i\in V, i\in [m]\}$, $\delta_G(u_i,v_i)$'s, are all decreased. The main results of this paper are summarized as follows: (1) We show that the optimal bridge problem can be solved in $O(n^2)$ time and that a variation of it has a near-quadratic lower bound unless SETH fails. The proof also implies that the famous 3-SUM problem does have a near-quadratic lower bound for large integers, e.g., each of the $n$ input integers has $\Omega(\log n)$ decimal digits. We then give a simple factor-2 $O(n\log n)$ time approximation algorithm for the optimal bridge problem. (2) We present an $O(n^4)$ time algorithm to solve the twin bridges problem, exploiting some new property not in the optimal bridge problem. (3) For the general problem of inserting $k$ edges to reduce the (graph) distances between $m$ given pairs, we show that the problem is NP-complete., Comment: 18 pages, 5 figures

Motivated by computing duplication patterns in sequences, a new fundamental problem called the longest subsequence-repeated subsequence (LSRS) is proposed. Given a sequence $S$ of length $n$, a letter-repeated subsequence is a subsequence of $S$ in the form of $x_1^{d_1}x_2^{d_2}\cdots x_k^{d_k}$ with $x_i$ a subsequence of $S$, $x_j\neq x_{j+1}$ and $d_i\geq 2$ for all $i$ in $[k]$ and $j$ in $[k-1]$. We first present an $O(n^6)$ time algorithm to compute the longest cubic subsequences of all the $O(n^2)$ substrings of $S$, improving the trivial $O(n^7)$ bound. Then, an $O(n^6)$ time algorithm for computing the longest subsequence-repeated subsequence (LSRS) of $S$ is obtained. Finally we focus on two variants of this problem. We first consider the constrained version when $\Sigma$ is unbounded, each letter appears in $S$ at most $d$ times and all the letters in $\Sigma$ must appear in the solution. We show that the problem is NP-hard for $d=4$, via a reduction from a special version of SAT (which is obtained from 3-COLORING). We then show that when each letter appears in $S$ at most $d=3$ times, then the problem is solvable in $O(n^5)$ time., Comment: 15 pages, 1 figure

In this paper, we start with a variation of the star cover problem called the Two-Squirrel problem. Given a set $P$ of $2n$ points in the plane, and two sites $c_1$ and $c_2$, compute two $n$-stars $S_1$ and $S_2$ centered at $c_1$ and $c_2$ respectively such that the maximum weight of $S_1$ and $S_2$ is minimized. This problem is strongly NP-hard by a reduction from Equal-size Set-Partition with Rationals. Then we consider two variations of the Two-Squirrel problem, namely the Two-MST and Two-TSP problem, which are both NP-hard. The NP-hardness for the latter is obvious while the former needs a non-trivial reduction from Equal-size Set-Partition with Rationals. In terms of approximation algorithms, for Two-MST and Two-TSP we give factor 3.6402 and $4+\varepsilon$ approximations respectively. Finally, we also show some interesting polynomial-time solvable cases for Two-MST., Comment: 17 pages, 7 figures

Sorting a permutation by reversals is a famous problem in genome rearrangements. Since 1997, quite some biological evidence were found that in many genomes the reversed regions are usually flanked by a pair of inverted repeats. This type of reversals are called symmetric reversals, which, unfortunately, were largely ignored until recently. In this paper, we investigate the problem of sorting by symmetric reversals, which requires a series of symmetric reversals to transform one chromosome $A$ into the another chromosome $B$. The decision problem of sorting by symmetric reversals is referred to as {\em SSR} (when the input chromosomes $A$ and $B$ are given, we use {\em SSR(A,B)}) and the corresponding optimization version (i.e., when the answer for {\em SSR(A,B)} is yes, using the minimum number of symmetric reversals to convert $A$ to $B$), is referred to as {\em SMSR(A,B)}. The main results of this paper are summarized as follows, where the input is a pair of chromosomes $A$ and $B$ with $n$ repeats. (1) We present an $O(n^2)$ time algorithm to solve the decision problem {\em SSR(A,B)}, i.e., determine whether a chromosome $A$ can be transformed into $B$ by a series of symmetric reversals. (2) We design an $O(n^2)$ time algorithm for a special 2-balanced case of {\em SMSR(A,B)}, where chromosomes $A$ and $B$ both have duplication number 2 and every repeat appears twice in different orientations in $A$ and $B$. (3) We show that SMSR is NP-hard even if the duplication number of the input chromosomes are at most 2, hence showing that the above positive optimization result is the best possible. As a by-product, we show that the \emph{minimum Steiner tree} problem on \emph{circle graphs} is NP-hard, settling the complexity status of a 38-year old open problem., Comment: 35 pages, 12 figures

Protein content in wheat plays a significant role when determining the price of wheat production. The Grain mixing problem aims to find the optimal bin pair combination with an appropriate mixing ratio to load each truck that will yield a maximum profit when sold to a set of local grain elevators. In this paper, we presented two complexity proofs for the grain mixing problem and showed that finding the optimal solutions for the grain mixing problem remains hard. These proofs follow a reduction from the $3$-dimensional matching ($3$-DM) problem and a more restricted version of the $3$-DM known as planar $3$-DM problem respectively. The complexity proofs do suggest that the exact algorithm to find the optimal solution for the grain mixing problem may be infeasible.

Given a sequence $S$ of length $n$, a letter-duplicated subsequence is a subsequence of $S$ in the form of $x_1^{d_1}x_2^{d_2}\cdots x_k^{d_k}$ with $x_i\in\Sigma$, $x_j\neq x_{j+1}$ and $d_i\geq 2$ for all $i$ in $[k]$ and $j$ in $[k-1]$. A linear time algorithm for computing the longest letter-duplicated subsequence (LLDS) of $S$ can be easily obtained. In this paper, we focus on two variants of this problem. We first consider the constrained version when $\Sigma$ is unbounded, each letter appears in $S$ at least 6 times and all the letters in $\Sigma$ must appear in the solution. We show that the problem is NP-hard (a further twist indicates that the problem does not admit any polynomial time approximation). The reduction is from possibly the simplest version of SAT that is NP-complete, $(\leq 2,1,\leq 3)$-SAT, where each variable appears at most twice positively and exact once negatively, and each clause contains at most three literals and some clauses must contain exactly two literals. (We hope that this technique will serve as a general tool to help us proving the NP-hardness for some more tricky sequence problems involving only one sequence -- much harder than with at least two input sequences, which we apply successfully at the end of the paper on some extra variations of the LLDS problem.) We then show that when each letter appears in $S$ at most 3 times, then the problem admits a factor $1.5-O(\frac{1}{n})$ approximation. Finally, we consider the weighted version, where the weight of a block $x_i^{d_i} (d_i\geq 2)$ could be any positive function which might not grow with $d_i$. We give a non-trivial $O(n^2)$ time dynamic programming algorithm for this version, i.e., computing an LD-subsequence of $S$ whose weight is maximized., Comment: 18 pages

Recently, due to the genomic sequence analysis in several types of cancer, the genomic data based on {\em copy number profiles} ({\em CNP} for short) are getting more and more popular. A CNP is a vector where each component is a non-negative integer representing the number of copies of a specific gene or segment of interest. In this paper, we present two streams of results. The first is the negative results on two open problems regarding the computational complexity of the Minimum Copy Number Generation (MCNG) problem posed by Qingge et al. in 2018. It was shown by Qingge et al. that the problem is NP-hard if the duplications are tandem and they left the open question of whether the problem remains NP-hard if arbitrary duplications are used. We answer this question affirmatively in this paper; in fact, we prove that it is NP-hard to even obtain a constant factor approximation. We also prove that the parameterized version is W[1]-hard, answering another open question by Qingge et al. The other result is positive and is based on a new (and more general) problem regarding CNP's. The \emph{Copy Number Profile Conforming (CNPC)} problem is formally defined as follows: given two CNP's $C_1$ and $C_2$, compute two strings $S_1$ and $S_2$ with $cnp(S_1)=C_1$ and $cnp(S_2)=C_2$ such that the distance between $S_1$ and $S_2$, $d(S_1,S_2)$, is minimized. Here, $d(S_1,S_2)$ is a very general term, which means it could be any genome rearrangement distance (like reversal, transposition, and tandem duplication, etc). We make the first step by showing that if $d(S_1,S_2)$ is measured by the breakpoint distance then the problem is polynomially solvable., Comment: 16 pages, 3 figures

Throughout this paper, a persistence diagram ${\cal P}$ is composed of a set $P$ of planar points (each corresponding to a topological feature) above the line $Y=X$, as well as the line $Y=X$ itself, i.e., ${\cal P}=P\cup\{(x,y)|y=x\}$. Given a set of persistence diagrams ${\cal P}_1,...,{\cal P}_m$, for the data reduction purpose, one way to summarize their topological features is to compute the {\em center} ${\cal C}$ of them first under the bottleneck distance. We consider two discrete versions and one continuous version. For technical reasons, we first focus on the case when $|P_i|$'s are all the same (i.e., all have the same size $n$), and the problem is to compute a center point set $C$ under the bottleneck matching distance. We show, by a non-trivial reduction from the Planar 3D-Matching problem, that this problem is NP-hard even when $m=3$ diagrams are given. This implies that the general center problem for persistence diagrams under the bottleneck distance, when $P_i$'s possibly have different sizes, is also NP-hard when $m\geq 3$. On the positive side, we show that this problem is polynomially solvable when $m=2$ and admits a factor-2 approximation for $m\geq 3$. These positive results hold for any $L_p$ metric when $P_i$'s are point sets of the same size, and also hold for the case when $P_i$'s have different sizes in the $L_\infty$ metric (i.e., for the Center Persistence Diagram problem). This is the best possible in polynomial time for the Center Persistence Diagram under the bottleneck distance unless P = NP. All these results hold for both of the discrete versions as well as the continuous version; in fact, the NP-hardness and approximation results also hold under the Wasserstein distance for the continuous version., Comment: 16 pages, 7 figures

In computational biology, tandem duplication is an important biological phenomenon which can occur either at the genome or at the DNA level. A tandem duplication takes a copy of a genome segment and inserts it right after the segment - this can be represented as the string operation $AXB \Rightarrow AXXB$. For example, Tandem exon duplications have been found in many species such as human, fly or worm, and have been largely studied in computational biology. The Tandem Duplication (TD) distance problem we investigate in this paper is defined as follows: given two strings $S$ and $T$ over the same alphabet, compute the smallest sequence of tandem duplications required to convert $S$ to $T$. The natural question of whether the TD distance can be computed in polynomial time was posed in 2004 by Leupold et al. and had remained open, despite the fact that tandem duplications have received much attention ever since. In this paper, we prove that this problem is NP-hard. We further show that this hardness holds even if all characters of $S$ are distinct. This is known as the exemplar TD distance, which is of special relevance in bioinformatics. One of the tools we develop for the reduction is a new problem called the Cost-Effective Subgraph, for which we obtain W[1]-hardness results that might be of independent interest. We finally show that computing the exemplar TD distance between $S$ and $T$ is fixed-parameter tractable. Our results open the door to many other questions, and we conclude with several open problems.

Persistence diagrams are important tools in the field of topological data analysis that describe the presence and magnitude of features in a filtered topological space. However, current approaches for comparing a persistence diagram to a set of other persistence diagrams is linear in the number of diagrams or do not offer performance guarantees. In this paper, we apply concepts from locality-sensitive hashing to support approximate nearest neighbor search in the space of persistence diagrams. Given a set $\Gamma$ of $n$ $(M,m)$-bounded persistence diagrams, each with at most $m$ points, we snap-round the points of each diagram to points on a cubical lattice and produce a key for each possible snap-rounding. Specifically, we fix a grid over each diagram at several resolutions and consider the snap-roundings of each diagram to the four nearest lattice points. Then, we propose a data structure with $\tau$ levels $\mathbb{D}_{\tau}$ that stores all snap-roundings of each persistence diagram in $\Gamma$ at each resolution. This data structure has size $O(n5^m\tau)$ to account for varying lattice resolutions as well as snap-roundings and the deletion of points with low persistence. To search for a persistence diagram, we compute a key for a query diagram by snapping each point to a lattice and deleting points of low persistence. Furthermore, as the lattice parameter decreases, searching our data structure yields a six-approximation of the nearest diagram in $\Gamma$ in $O((m\log{n}+m^2)\log\tau)$ time and a constant factor approximation of the $k$th nearest diagram in $O((m\log{n}+m^2+k)\log\tau)$ time.

Given a set of $n$ points $P$ in the plane, each colored with one of the $t$ given colors, a color-spanning set $S\subset P$ is a subset of $t$ points with distinct colors. The minimum diameter color-spanning set (MDCS) is a color-spanning set whose diameter is minimum (among all color-spanning sets of $P$). Somehow symmetrically, the largest closest pair color-spanning set (LCPCS) is a color-spanning set whose closest pair is the largest (among all color-spanning sets of $P$). Both MDCS and LCPCS have been shown to be NP-complete, but whether they are fixed-parameter tractable (FPT) when $t$ is a parameter is still open. Motivated by this question, we consider the FPT tractability of some matching problems under this color-spanning model, where $t=2k$ is the parameter. The problems are summarized as follows: (1) MinSum Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that their total edge length is minimized; (2) MaxMin Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that the minimum edge length is maximized; (3) MinMax Matching Color-Spanning Set, namely, computing a matching of $2k$ points with distinct colors such that the maximum edge length is minimized; and (4) $k$-Multicolored Independent Matching, namely, computing a matching of $2k$ vertices in a graph such that the vertices of the edges in the matching do not share common edges in the graph. We show that the first three problems are polynomially solvable (hence in FPT), while problem (4) is W[1]-hard., Comment: 12 pages, 2 figures, earlier version appeared in FAW'17

We study the problem of computing the upper bound of the discrete Fr\'{e}chet distance for imprecise input, and prove that the problem is NP-hard. This solves an open problem posed in 2010 by Ahn \emph{et al}. If shortcuts are allowed, we show that the upper bound of the discrete Fr\'{e}chet distance with shortcuts for imprecise input can be computed in polynomial time and we present several efficient algorithms., Comment: 15 pages, 8 figures

The problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones in 3D has led Bereg et al. to pose the Chain Pair Simplification problem (CPS). In this problem, given two polygonal chains $A$ and $B$ of lengths $m$ and $n$, respectively, one needs to simplify them simultaneously, such that each of the resulting simplified chains, $A'$ and $B'$, is of length at most $k$ and the discrete \frechet\ distance between $A'$ and $B'$ is at most $\delta$, where $k$ and $\delta$ are given parameters. In this paper we study the complexity of CPS under the discrete \frechet\ distance (CPS-3F), i.e., where the quality of the simplifications is also measured by the discrete \frechet\ distance. Since CPS-3F was posed in 2008, its complexity has remained open. However, it was believed to be \npc, since CPS under the Hausdorff distance (CPS-2H) was shown to be \npc. We first prove that the weighted version of CPS-3F is indeed weakly \npc\, even on the line, based on a reduction from the set partition problem. Then, we prove that CPS-3F is actually polynomially solvable, by presenting an $O(m^2n^2\min\{m,n\})$ time algorithm for the corresponding minimization problem. In fact, we prove a stronger statement, implying, for example, that if weights are assigned to the vertices of only one of the chains, then the problem remains polynomially solvable. We also study a few less rigid variants of CPS and present efficient solutions for them. Finally, we present some experimental results that suggest that (the minimization version of) CPS-3F is significantly better than previous algorithms for the motivating biological application.

In this paper we focus on the map matching problem where the goal is to find a path through a planar graph such that the path through the vertices closely matches a given polygonal curve. The map matching problem is usually approached with the Fr\'echet distance matching the edges of the path as well. Here, we formally define the discrete map matching problem based on the discrete Fr\'echet distance. We then look at the complexities of some variations of the problem which allow for vertices in the graph to be unique or reused, and whether there is a bound on the length of the path or the number of vertices from the graph used in the path. We prove several of these problems to be NP-complete, and then conclude the paper with some open questions.

We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that runs in time $O^{*}(\rho^k)$, where $\rho = \sqrt{\sqrt{2} + 1} \approx 1.555$ is the positive root of the polynomial $x^4-2x^2-1$. This improves the current-best algorithm of Chen et al. that runs in time $O^{*}(1.619^k)$. For the {\sc generalized multiway cut on trees} problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed; this answers an open question posed in a recent paper by Liu and Zhang. By reducing the {\sc generalized multiway cut on trees} problem to the {\sc multicut on trees} problem, our results give a parameterized algorithm that solves the {\sc generalized multiway cut on trees} problem in time $O^{*}(\rho^k)$, where $\rho = \sqrt{\sqrt{2} + 1} \approx 1.555$ time.

Pedigree graphs, or family trees, are typically constructed by an expensive process of examining genealogical records to determine which pairs of individuals are parent and child. New methods to automate this process take as input genetic data from a set of extant individuals and reconstruct ancestral individuals. There is a great need to evaluate the quality of these methods by comparing the estimated pedigree to the true pedigree. In this paper, we consider two main pedigree comparison problems. The first is the pedigree isomorphism problem, for which we present a linear-time algorithm for leaf-labeled pedigrees. The second is the pedigree edit distance problem, for which we present 1) several algorithms that are fast and exact in various special cases, and 2) a general, randomized heuristic algorithm. In the negative direction, we first prove that the pedigree isomorphism problem is as hard as the general graph isomorphism problem, and that the sub-pedigree isomorphism problem is NP-hard. We then show that the pedigree edit distance problem is APX-hard in general and NP-hard on leaf-labeled pedigrees. We use simulated pedigrees to compare our edit-distance algorithms to each other as well as to a branch-and-bound algorithm that always finds an optimal solution.

Motivated by modern applications like image processing and wireless sensor networks, we consider a variation of the famous Kepler Conjecture. Given any infinite set of unit balls covering the whole space, we want to know the optimal (lim sup) density of the volume which is covered by exactly one ball (i.e., the maximum such density over all unit ball covers, called the {\em optimal 1-density} and denoted as $\delta_d$, where $d$ is the dimension of the Euclidean space). We prove that in 2D the optimal 1-density $\delta_2=(3\sqrt(3)-\pi)/\pi \approx 0.6539$, which is achieved through a regular hexagonal covering. In 3D, the problem is widely open and we present a Dodecehadral Cover Conjecture which states that the optimal 1-density in 3D, $\delta_3$, is bounded from above by the 1-density of a unit ball whose Voronoi polyhedron is a regular dodecahedron of circum-radius one (determined by 12 extra unit balls). We show numerically that this 1-density $\delta_3(dc)\approx 0.315$., Comment: 11 pages, 4 figures

We show that given $m$ proteins (or protein backbones, which are modeled as 3D polygonal chains each of length O(n)) the problem of protein local structure alignment under the discrete Fr\'{e}chet distance is as hard as Independent Set. So the problem does not admit any approximation of factor $n^{1-\epsilon}$. This is the strongest negative result regarding the protein local structure alignment problem. On the other hand, if $m$ is a constant, then the problem can be solved in polygnomial time., Comment: 11 pages, 2 figures