This paper studies MPCv5+, which is to cover as many vertices as possible in a given graph G=(V,E) by vertex-disjoint 5+-paths (i.e., paths each with at least five vertices). MPCv5+ is NP-hard and admits an existing local-search-based approximation algorithm which achieves a ratio of [Formula presented] and runs in O(|V|6) time. In this paper, we present a new approximation algorithm for MPCv5+ which achieves a ratio of 2.511 and runs in O(|V|2.5|E|2) time. Unlike the previous algorithm, the new algorithm is based on maximum matching, maximum path-cycle cover, and recursion. © 2025 The Author(s)

The problem studied in this paper is to find a collection of vertex-disjoint paths in a given graph G = ( V , E ) such that each path has length at least k , called a long path, and the total number of edges on these paths is maximized. The problem is NP-hard for any fixed k or when k is part of the input, by a reduction from the Hamiltonian path problem. Berman and Karpinski presented a 7/6-approximation algorithm for k = 1 , but for a general k ≥ 2 , there is no approximation algorithm directly for the problem. We present the first local search ( 0.4394 k + O ( 1 ) ) -approximation algorithm for any fixed k ≥ 1 , and a 1.4254-approximation algorithm for k = 2 built on top of a maximum triangle-free path-cycle cover.

We study a variant of the well-known Path Cover problem where the candidate paths in a solution have orders up to a fixed integer k . In Path Cover, one finds a minimum number of vertex-disjoint paths in an input graph to cover all the vertices; in our variant, not all paths but only those short ones, i.e., containing up to k vertices, can be used as candidates. The problem is NP-hard when k ≥ 3 ; in the literature, there exist quite a number of approximation algorithms, especially for small k 's. We present an improved k 3 -approximation algorithm for k ∈ { 6 , 7 , 8 } , an improved 55 31 -approximation algorithm for k = 5 , and an improved 8 5 -approximation algorithm for k = 4 . The novelty inside these improved algorithms is observing a close connection between an optimal path cover and a certain polynomial-time computed edge set.

Given a digraph G=(V,E), the k-path partition problem aims to find a minimum collection of vertex-disjoint directed paths, each of order at most k, to cover all the vertices of V. The problem has various applications in facility location, network monitoring, transportation networks and others. Its special case on undirected graphs is NP-hard when k≥3, and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k/2-approximation algorithm, for any k≥3, based on a novel concept of enlarging walk to minimize the number of singletons in the k-path partition. Secondly, for k=3, we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13/9-approximation algorithm. Lastly, for any k≥7, we present an improved (k+2)/3-approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process.

Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose. The problem of computing the rSPR distance of two given trees has many applications but is NP-hard. Accordingly, a number of programs have been developed for solving the problem either exactly or approximately. In this paper, we develop two new programs, one of which solves the problem exactly and outperforms the previous best (namely, Whidden et al.'s rSPR-v1.3.0) significantly, while the other solves the problem approximately and outputs significantly better lower and upper bounds on the rSPR distance of the two given trees than the previous best due to Schalekamp et al. Our programs can be downloaded at http://rnc.r.dendai.ac.jp/rspr.html.

The problem of computing the rSPR distance of two phylogenetic trees (denoted by RDC) is NP-hard and so is the problem of computing the hybridization number of two phylogenetic trees (denoted by HNC). Since they are important problems in phylogenetics, they have been studied extensively in the literature. Indeed, quite a number of exact or approximation algorithms have been designed and implemented for them. In this paper, we design and implement one exact algorithm for HNC and several approximation algorithms for RDC and HNC. Our experimental results show that the resulting exact program is much faster (namely, more than 80 times faster for the easiest dataset used in the experiments) than the previous best and its superiority in speed becomes even more significant for more difficult instances. Moreover, the resulting approximation programs output much better results than the previous bests; indeed, the outputs are always nearly optimal and often optimal. Of particular interest is the usage of the Monte Carlo tree search (MCTS) method in the design of our approximation algorithms. Our experimental results show that with MCTS, we can often solve HNC exactly within short time.

BACKGROUND: The haplotype assembly problem for diploid is to find a pair of haplotypes from a given set of aligned Single Nucleotide Polymorphism (SNP) fragments (reads). It has many applications in association studies, drug design, and genetic research. Since this problem is computationally hard, both heuristic and exact algorithms have been designed for it. Although exact algorithms are much slower, they are still of great interest because they usually output significantly better solutions than heuristic algorithms in terms of popular measures such as the Minimum Error Correction (MEC) score, the number of switch errors, and the QAN50 score. Exact algorithms are also valuable because they can be used to witness how good a heuristic algorithm is. The best known exact algorithm is based on integer linear programming (ILP) and it is known that ILP can also be used to improve the output quality of every heuristic algorithm with a little decline in speed. Therefore, faster ILP models for the problem are highly demanded. RESULTS: As in previous studies, we consider not only the general case of the problem but also its all-heterozygous case where we assume that if a column of the input read matrix contains at least one 0 and one 1, then it corresponds to a heterozygous SNP site. For both cases, we design new ILP models for the haplotype assembly problem which aim at minimizing the MEC score. The new models are theoretically better because they contain significantly fewer constraints. More importantly, our experimental results show that for both simulated and real datasets, the new model for the all-heterozygous (respectively, general) case can usually be solved via CPLEX (an ILP solver) at least 5 times (respectively, twice) faster than the previous bests. Indeed, the running time can sometimes be 41 times better. CONCLUSIONS: This paper proposes a new ILP model for the haplotype assembly problem and its all-heterozygous case, respectively. Experiments with both real and simulated datasets show that the new models can be solved within much shorter time by CPLEX than the previous bests. We believe that the models can be used to improve heuristic algorithms as well.

Reconstruction of ancestral relationships among genera, species, and populations is a core task in evolutionary biology. At the population level, pedigrees have been commonly used. Reconstruction of pedigree is required in practice due to legal or medical reasons. Pedigrees are very important to geneticists for inferring haplotype segments, recombination, and allele sharing status with which disease loci can be identified. Evaluating reconstruction methods requires comparing the inferred pedigree and the known pedigrees. Moreover, comparison of pedigrees is required in studying relationships among crops such as maize, wheat and barley, etc. In this paper, we discuss three models for comparison of pedigrees, the maximum pedigree isomorphism problem, the maximum paternal-path-preserved mapping problem, and the minimum edge-cutting mapping problem. For the maximum pedigree isomorphism problem, we prove that the problem is NP-hard and give a fixed-parameter algorithm for the problem. For the maximum paternal-path-preserved mapping problem, we give a dynamic-programming algorithm to find the mapping that preserves the maximum number of paternal paths between the two input pedigrees. For the minimum edge-cutting mapping problem, we prove that the problem is NP-hard and give a fixed-parameter algorithm with running time , where is the number of vertices in the two input pedigrees and is the number of edges to be cut. This algorithm is useful in practice when comparing two similar pedigrees.

This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Previously, Tofigh et al. [20] gave a fixed-parameter algorithm for this problem that runs in O(m + 3kn) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between Sand G. In this paper, by refining their algorithm, we obtain a new one for the same problem that finds and outputs the solutions in a compact form within O(mn2+ 3k) time.

MOTIVATION: Haplotypes play a crucial role in genetic analysis and have many applications such as gene disease diagnoses, association studies, ancestry inference and so forth. The development of DNA sequencing technologies makes it possible to obtain haplotypes from a set of aligned reads originated from both copies of a chromosome of a single individual. This approach is often known as haplotype assembly. Exact algorithms that can give optimal solutions to the haplotype assembly problem are highly demanded. Unfortunately, previous algorithms for this problem either fail to output optimal solutions or take too long time even executed on a PC cluster. RESULTS: We develop an approach to finding optimal solutions for the haplotype assembly problem under the minimum-error-correction (MEC) model. Most of the previous approaches assume that the columns in the input matrix correspond to (putative) heterozygous sites. This all-heterozygous assumption is correct for most columns, but it may be incorrect for a small number of columns. In this article, we consider the MEC model with or without the all-heterozygous assumption. In our approach, we first use new methods to decompose the input read matrix into small independent blocks and then model the problem for each block as an integer linear programming problem, which is then solved by an integer linear programming solver. We have tested our program on a single PC [a Linux (x64) desktop PC with i7-3960X CPU], using the filtered HuRef and the NA 12878 datasets (after applying some variant calling methods). With the all-heterozygous assumption, our approach can optimally solve the whole HuRef data set within a total time of 31 h (26 h for the most difficult block of the 15th chromosome and only 5 h for the other blocks). To our knowledge, this is the first time that MEC optimal solutions are completely obtained for the filtered HuRef dataset. Moreover, in the general case (without the all-heterozygous assumption), for the HuRef dataset our approach can optimally solve all the chromosomes except the most difficult block in chromosome 15 within a total time of 12 days. For both of the HuRef and NA12878 datasets, the optimal costs in the general case are sometimes much smaller than those in the all-heterozygous case. This implies that some columns in the input matrix (after applying certain variant calling methods) still correspond to false-heterozygous sites. AVAILABILITY: Our program, the optimal solutions found for the HuRef dataset available at http://rnc.r.dendai.ac.jp/hapAssembly.html.

BACKGROUND: Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to combine the two phylogenetic trees into a hybridization network with the fewest hybridization events. This leads to three computational problems, namely, the problem of computing the minimum size of a hybridization network, the problem of constructing one minimum hybridization network, and the problem of enumerating a representative set of minimum hybridization networks. The previously best software tools for these problems (namely, Chen and Wang's HybridNet and Albrecht et al.'s Dendroscope 3) run very slowly for large instances that cannot be reduced to relatively small instances. Indeed, when the minimum size of a hybridization network of two given trees is larger than 23 and the problem for the trees cannot be reduced to relatively smaller independent subproblems, then HybridNet almost always takes longer than 1 day and Dendroscope 3 often fails to complete. Thus, a faster software tool for the problems is in need. RESULTS: We develop a software tool in ANSI C, named FastHN, for the following problems: Computing the minimum size of a hybridization network, constructing one minimum hybridization network, and enumerating a representative set of minimum hybridization networks. We obtain FastHN by refining HybridNet with three ideas. The first idea is to preprocess the input trees so that the trees become smaller or the problem becomes to solve two or more relatively smaller independent subproblems. The second idea is to use a fast algorithm for computing the rSPR distance of two given phylognetic trees to cut more branches of the search tree in the exhaustive-search stage of the algorithm. The third idea is that during the exhaustive-search stage of the algorithm, we find two sibling leaves in one of the two forests (obtained from the given trees by cutting some edges) such that they are as far as possible in the other forest. As the result, FastHN always runs much faster than HybridNet. Unlike Dendroscope 3, FastHN is a single-threaded program. Despite this disadvantage, our experimental data shows that FastHN runs substantially faster than the multi-threaded Dendroscope 3 on a PC with multiple cores. Indeed, FastHN can finish within 16 minutes (on average on a Windows-7 (x64) desktop PC with i7-2600 CPU) even if the minimum size of a hybridization network of two given trees is about 25, the trees each have 100 leaves, and the problem for the input trees cannot be reduced to two or more independent subproblems via cluster reductions. It is also worth mentioning that like HybridNet, FastHN does not use much memory (indeed, the amount of memory is at most quadratic in the input size). In contrast, Dendroscope 3 uses a huge amount of memory. Executables of FastHN for Windows XP (x86), Windows 7 (x64), Linux, and Mac OS are available (see the Results and discussion section for details). CONCLUSIONS: For both biological datasets and simulated datasets, our experimental results show that FastHN runs substantially faster than HybridNet and Dendroscope 3. The superiority of FastHN in speed over the previous tools becomes more significant as the hybridization number becomes larger. In addition, FastHN uses much less memory than Dendroscope 3 and uses the same amount of memory as HybridNet.

We give a fixed-parameter algorithm for the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications, gene losses, and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Our algorithm can work for the weighted version of the problem, where the costs of a gene duplication, a gene loss, and an LGT are left to the user's discretion. The algorithm runs in O(m + 3(k/c)n) time, where m is the number of vertices in S, n is the number of vertices in G, c is the smaller between a gene duplication cost and an LGT cost, and k is the minimum cost of an LCA-reconciliation between S and G. The time complexity is indeed better if the cost of a gene loss is greater than 0. In particular, when the cost of a gene loss is at least 0.614c, the running time of the algorithm is O(m + 2.78(k/c)n).

A reticulate network N of multiple phylogenetic trees may have vertices with two or more parents (called reticulation vertices). There are two ways to define the reticulation number of N. One is to define it as the number of reticulation vertices in N; in this case, a reticulate network with the smallest reticulation number is called an optimal type-I reticulate network of the trees. The other is to define it as the total number of parents of reticulation vertices in N minus the number of reticulation vertices in N; in this case, a reticulate network with the smallest reticulation number is called an optimal type-II reticulate network of the trees. In this paper, we present a fast algorithm for constructing one or all optimal type-I reticulate networks of multiple phylogenetic trees. We then use the algorithm together with other ideas to obtain an algorithm for estimating a lower bound on the reticulation number of an optimal type-II reticulate network of the input trees. To our knowledge, these are the first fast algorithms for the problems. Our experimental data shows that our algorithms can construct optimal type-I reticulate networks rapidly and can compute better lower bounds for optimal type-II reticulate networks within much shorter time than the previously best program.

Linkage analysis serves as a way of finding locations of genes that cause genetic diseases. Linkage studies have facilitated the identification of several hundreds of human genes that can harbor mutations which by themselves lead to a disease phenotype. The fundamental problem in linkage analysis is to identify regions whose allele is shared by all or almost all affected members but by none or few unaffected members. Almost all the existing methods for linkage analysis are for families with clearly given pedigrees. Little work has been done for the case where the sampled individuals are closely related, but their pedigree is not known. This situation occurs very often when the individuals share a common ancestor at least six generations ago. Solving this case will tremendously extend the use of linkage analysis for finding genes that cause genetic diseases. In this paper, we propose a mathematical model (the shared center problem) for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. We show the NP-completeness of the shared center problem and present a ratio-2 polynomial-time approximation algorithm for its minimization version (called the closest shared center problem). We then convert the approximation algorithm into a heuristic algorithm for the shared center problem. Based on this heuristic, we finally design a heuristic algorithm for mutation region detection. We further implement the algorithms to obtain a software package. Our experimental data show that the software is both fast and accurate. The package is available at >;http://www.cs.cityu.edu.hk/~lwang/software/LDWP/ for noncommercial use.

We present two parameterized algorithms for the closest string problem. The first runs in O(nL + nd · 17.97d) time for DNA strings and in O(nL + nd · 61.86d) time for protein strings, where n is the number of input strings, L is the length of each input string, and d is the given upper bound on the number of mismatches between the center string and each input string. The second runs in O(nL + nd · 13.92d) time for DNA strings and in O(nL + nd · 47.21d) time for protein strings. We then extend the first algorithm to a new parameterized algorithm for the closest substring problem that runs in O((n - 1)m2(L + d · 17.97d · m[log2(d+1)])) time for DNA strings and in O((n - 1)m2(L + d · 61.86d · m[log2(d+1)])) time for protein strings, where n is the number of input strings, L is the length of the center substring, L - 1 + m is the maximum length of a single input string, and d is the given upper bound on the number of mismatches between the center substring and at least one substring of each input string. All the algorithms significantly improve the previous bests. To verify experimentally the theoretical improvements in the time complexity, we implement our algorithm in C and apply the resulting program to the planted (L, d)-motif problem proposed by Pevzner and Sze in 2000. We compare our program with the previously best exact program for the problem, namely PMSPrune (designed by Davila et al. in 2007). Our experimental data show that our program runs faster for practical cases and also for several challenging cases. Our algorithm uses less memory too.

MOTIVATIONS: When reticulation events occur, the evolutionary history of a set of existing species can be represented by a hybridization network instead of an evolutionary tree. When studying the evolutionary history of a set of existing species, one can obtain a phylogenetic tree of the set of species with high confidence by looking at a segment of sequences or a set of genes. When looking at another segment of sequences, a different phylogenetic tree can be obtained with high confidence too. This indicates that reticulation events may occur. Thus, we have the following problem: given two rooted phylogenetic trees on a set of species that correctly represent the tree-like evolution of different parts of their genomes, what is the hybridization network with the smallest number of reticulation events to explain the evolution of the set of species under consideration? RESULTS: We develop a program, named HybridNet, for constructing a hybridization network with the minimum number of reticulate vertices from two input trees. We first implement the O(3(d) n)-time algorithm by Whidden et al. for computing a maximum (acyclic) agreement forest. Our program can output all the maximum (acyclic) agreement forests. We then augment the program so that it can construct an optimal hybridization network for each given maximum acyclic agreement forest. To our knowledge, this is the first time that optimal hybridization networks can be rapidly constructed. AVAILABILITY: The program is available for non-commercial use, at http://www.cs.cityu.edu.hk/∼lwang/software/Hn/treeComp.html.

Some genetic diseases in human beings are dominated by short sequences repeated consecutively called tandem repeats. Once a region containing tandem repeats is found, it is of great interest to study the history of creating the repeats. The computational problem of reconstructing the duplication history of tandem repeats has been studied extensively in the literature. Almost all previous studies focused on the simplest case where the size of each duplication block is 1. Only recently we succeeded in giving the first polynomial-time approximation algorithm with a guaranteed ratio for a more general case where the size of each duplication block is at most 2; the algorithm achieves a ratio of 6 and runs in O(n{11}) time. In this paper, we present two new polynomial-time approximation algorithms for this more general case. One of them achieves a ratio of 5 and runs in O(n{9}) time, while the other achieves a ratio of 2.5 + epsilon for any constant epsilon > 0 but runs slower.

Given a planar graph $\Ggg$ and a sequence ${\CC}_1,\ldots,{\CC}_q$, where each ${\CC}_i$ is a family of vertex subsets of $\Ggg$, we wish to find a plane embedding of $\Ggg$, if any exists, such that, for each $i\in\{1,\ldots,q\}$, there is a face F i in the embedding whose boundary contains at least one vertex from each set in CC i . This problem has applications in the recovery of topological information from geographical data and the design of constrained layouts in VLSI. Let $\inputsize$ be the input size,i.e., the total number of vertices and edges in $\Ggg$ and the families CC i , counting multiplicity. We show that this problem is NP-complete in general. We also show that it is solvable in $O(\inputsize\log \inputsize)$ time for the special case in which, for each input family CC i , each set in CC i induces a connected subgraph of the input graph $\Ggg$. Note that the classical problem of simply finding a planar embedding is a further special case of this case with q=0. Therefore, the processing of the additional constraints CC 1 , . . .,CC q incurs only a logarithmic factor of overhead.

Given a set of species and their similarity data, an important problem in evolutionary biology is how to reconstruct a phylogeny (also called evolutionary tree) so that species are close in the phylogeny if and only if they have high similarity. Assume that the similarity data are represented as a graph G = (V, E), where each vertex represents a species and two vertices are adjacent if they represent species of high similarity. The phylogeny reconstruction problem can then be abstracted as the problem of finding a (phylogenetic) tree T from the given graph G such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e., leaves) of T are exactly the elements of V, and (3) $(u, v) \in E$ if and only if $d_T(u, v) \le k$ for some fixed threshold k, where d T (u,v) denotes the distance between u and v in tree T. This is called the phylogenetic kth root problem (PRk), and such a tree T, if it exists, is called a phylogenetic kth root of graph G. The computational complexity of PRk} is open, except for $k \le 4$. In this paper, we investigate PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. Our main contribution is a linear-time algorithm that determines if G has such a phylogenetic kth root, and if so, demonstrates one. On the other hand, because in practice the collected similarity data are usually not perfect and may contain errors, we propose to study a generalized version of PRk where the output phylogeny is required only to be an approximate root of the input graph. We show that this and other related problems are computationally intractable.

We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge , as planarity requires). Such adjacencies define a map graph . We give an NP characterization for such graphs, derive some consequences regarding sparsity and coloring, and survey some algorithmic results.

This paper answers an open question in the design of complimentary metal-oxide semiconductor VLSI circuits. The question asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding ${\cal E}$ such that ${\cal E}$ has an Euler trail P = e 1 e 2 ... e m and its dual graph has an Euler trail $P^*=e^*_1 e^*_2 \ldots e^*_m$, where $e^*_i$ is the dual edge of e i for i=1,2,...,m. This paper answers this question in the affirmative by presenting a linear-time algorithm.

We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points. In contrast to the classical technique of DeMillo, Lipton, Schwartz, and Zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits. Consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology. To demonstrate the methodology, we discuss two nontrivial applications. The first is to decide whether a graph has a perfect matching in parallel. Our new NC algorithm uses fewer random bits while doing less work than the previously best NC algorithm by Chari, Rohatgi, and Srinivasan. The second application is to test the equality of two multisets of integers. Our new algorithm improves upon the previously best algorithms by Blum and Kannan and can speed up their checking algorithm for sorting programs on a large range of inputs.

The paper answers an open question in the design of complimentary metal-oxide semiconductor (CMOS) VLSI circuits. It asks whether a polynomial-time algorithm can decide if a given planar graph has a plane embedding /spl epsiv/ such that /spl epsiv/ has a Euler trail P=e/sub 1/e/sub 2/...e/sub m/ and its dual graph has a Euler trail P*=e/sub 1/*e/sub 2/*...e/sub m/* where e/sub i/* is the dual edge of e/sub i/ for i=1, 2, ..., m. The paper answers this question in the affirmative by presenting a linear-time algorithm.

The traveling salesman problem on an n-point convex polygon and the minimum latency tour problem for n points on a straight line are two basic problems in graph theory and have been studied in the past. Previously, it was known that both problems can be solved in O(n 2 ) time. However, whether they can be solved in o(n 2 ) time was left open by Marcotte and Suri [SIAM J. Comput., 20 (1991), pp. 405--422] and Afrati et al. [Informatique Theorique Appl., 20 (1986), pp. 79--87], respectively. In this paper we show that both problems can be solved in O(n log n) time by reducing them to the following problem: Given an edge-weighted complete bipartite digraph G=(X, Y, E) with X={x 0 , . . ., x n } and Y={y 0 , . . ., y m }, we wish to find the shortest path from x 0 to x n in G. This new problem requires $\Omega(nm)$ time to solve in general, but we show that it can be solved in O(n + m log n) time if the weight matrices A and B of G are both concave, where for $0\leq i\leq n$ and $0\leq j\leq m$, A[i,j] and B[j,i] are the weights of the edges (x i , y j ) and (y j , x i ) in G, respectively. As demonstrated in this paper, the new problem is a powerful tool and we believe that it can be used to solve more problems.

We introduce and study a modified notion of planarity, in which two regions of a map are considered adjacent when they share any point of their boundaries (not an edge, as standard planarity requires).We seek to characterize the abstract graphs realized by such map adjacencies.We prove some preliiinary properGs of such graphs, and give a polynomial time algorithm for the following restricted problem: given an abstract graph, decide whether it is realized by a map in which at most four regions meet at any point.The general recognition problem remains open. 1 Introduction 1.1 Motivation: Topological Inference Suppose that you are told t.hat four planar regions relate in the following way: A is inside B; B overlaps G; C touches D on t.he outside; D overlaps B; D is disjoint from A; and C overlaps A. All four planar regions are "bubbles" with no holes (to be rigorous: disc homeomorphs).Is this possible?If so, we would like a model, a picture of four regions so related; if not, a proof of impossibility.This deceptively simple estension of propositional logic is known as the topological inference problem [5], and its special cases, extensions, and variants are studied in the area of geographic information systems [3, 4, 10, 5, 111.Despite much effort (and claims in t.he literature [12, 41.. .),no decision algorithm and f&rite asiomatization for this problem is known -although t,he problem becomes both finitely axiomatizable and polynomial-time decidable in any number of dimensions ot,her than two.In fact, the following special

. We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero. The methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points. In contrast to the classical technique of DeMillo, Lipton, Schwartz, and Zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits. Consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology. To demonstrate the methodology, we discuss two nontrivial applications. The first is to decide whether a graph has a perfect matching in parallel. Our new NC algorithm uses fewer random bits while doing less work than the previously best NC algorithm by Chari, Rohatgi, and Srinivasan. The second application is to test the equality of two multisets of integers. Our new algorithm improves upon the previously best algorithms ...