Search

An edge coloring of a graph $G$ is to color all the edges in the graph such that adjacent edges receive different colors. It is acyclic if each cycle in the graph receives at least three colors. Fiam{č}ik (1978) and Alon, Sudakov and Zaks (2001) conjectured that every simple graph with maximum degree $Δ$ is acyclically edge $(Δ+ 2)$-colorable -- the well-known acyclic edge coloring conjecture (AECC). Despite many major breakthroughs and minor improvements, the conjecture remains open even for planar graphs. In this paper, we prove that planar graphs are acyclically edge $(Δ+ 5)$-colorable. Our proof has two main steps: Using discharging methods, we first show that every non-trivial planar graph must have one of the eight groups of well characterized local structures; and then acyclically edge color the graph using no more than $Δ+ 5$ colors by an induction on the number of edges., Full version with 120 pages

This paper deals with the problem of finding a collection of vertex-disjoint paths in a given graph G=(V,E) such that each path has at least four vertices and the total number of vertices in these paths is maximized. The problem is NP-hard and admits an approximation algorithm which achieves a ratio of 2 and runs in O(|V|^8) time. The known algorithm is based on time-consuming local search, and its authors ask whether one can design a better approximation algorithm by a completely different approach. In this paper, we answer their question in the affirmative by presenting a new approximation algorithm for the problem. Our algorithm achieves a ratio of 1.874 and runs in O(min{|E|^2|V|^2, |V|^5}) time. Unlike the previously best algorithm, ours starts with a maximum matching M of G and then tries to transform M into a solution by utilizing a maximum-weight path-cycle cover in a suitably constructed graph.

Given a directed graph $G = (V, E)$, the $k$-path partition problem is 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 and others. Its special case on undirected graphs has received much attention recently, but the general directed version is seemingly untouched in the literature. We present the first $k/2$-approximation algorithm, for any $k \ge 3$, based on a novel concept of augmenting path to minimize the number of singletons in the partition. When $k \ge 7$, we present an improved $(k+2)/3$-approximation algorithm based on the maximum path-cycle cover followed by a careful $2$-cycle elimination process. When $k = 3$, we define the second novel kind of augmenting paths and propose an improved $13/9$-approximation algorithm., Comment: Extended abstract to appear in FAW 2021

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

Path cover is a well-known intractable problem that finds a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the objective function is not the number of paths but the number of length-$0$ paths (that is, isolated vertices), turns out to be polynomial-time solvable. We further show that another variant, where the objective function is the total number of length-$0$ and length-$1$ paths, is also polynomial-time solvable. Both variants find applications in approximating the two-machine flow-shop scheduling problem in which job processing has constraints that are formulated as a conflict graph. For the unit jobs, we present a $4/3$-approximation algorithm for the scheduling problem with an arbitrary conflict graph, based on the exact algorithm for the variants of the path cover problem. For the arbitrary jobs while the conflict graph is the union of two disjoint cliques, that is, all the jobs can be partitioned into two groups such that the jobs in a group are pairwise conflicting, we present a simple $3/2$-approximation algorithm., Comment: 15 pages, 2 figures

A graph property is a set of graphs such that if the set contains some graphG then it also contains each isomorphic copy ofG (with the same vertex set). A graph propertyP onn vertices is said to be elusive, if every decision tree algorithm recognizingP must examine alln(n−1)/2, pairs of vertices in the worst case. Karp conjectured that every nontrivial monotone graph property is elusive. In this paper, this conjecture is proved for some cases. Especially, it is shown that if the abstract simplicial complex of a nontrivial monotone graph propertyP has dimension not exceeding 5, thenP is elusive.

In this paper, we consider Parallel Machines Scheduling with nonsimultaneous machine available time. We give the exact worst case performance bound of MLPT proposed by Lee. Furthermore, two other modified LPT algorithms are discussed. The paper is ended by numerical experiments of these algorithms.

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.

Technical report TR11-02. Given two genomic maps G1 and G2 each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G1 and G2 such that the resultant subsequences, denoted as G1* and G2*, can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved 7/3-approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a sequential amortization. | TRID-ID TR11-02

Technical report TR08-07. In gene expression microarray data analysis, biclustering has been demonstrated to be one of the most effective methods for discovering gene expression patterns under various conditions. We present in this study a framework to take advantage of the homogeneously expressed genes in biclusters to construct a classifier for sample class membership prediction. Extensive experiments on 8 real cancer microarray datasets (4 diagnostic and 4 prognostic) show that our proposed classifier performed superior in both cancer diagnosis and prognosis, the latter of which was regarded quite difficult previously. Additionally, our results demonstrate that sample classification accuracy can serve as a good subjective quality measure for biclusters. | TRID-ID TR08-07

Technical report TR06-10. Background: Accurately quantifying the signature information of chemical shifts provides a foundation for accurate and complete sequential resonance assignment in protein NMR spectroscopy. A nearly complete assignment is a prerequisite for three dimensional protein structure calculation. Methods: A number of filtering steps are applied to construct two training datasets using known protein NMR data for learning scoring schemes to quantify the signature information. The scoring schemes are learned through a naive Bayesian method to use both intra-residue and inter-residue chemical shifts and to use the intermediate neural network output from the secondary structure predictor PsiPred. Results: Two training datasets ALL and HOMO for scoring scheme learning were carefully constructed. Based on these two datasets, a total of 16 scoring schemes were proposed and examined. An extensive simulation study was set up to validate these scoring schemes and the one that performed the best was implemented into a web server, which is publicly accessible. Conclusions: Through the extensive simulation study we found that the currently known protein NMR data is quite evenly distributed in terms of protein homology, and therefore homology removal in training dataset construction wouldn't gain a lot in the overall performance of the resultant scoring schemes. Also, we conclude that in general a naive Bayesian learning is better than a trivial distribution assumption. We believe this conclusion holds not just in our care but also for similar applications where the training data size is large. Another conclusion is that in applications where PsiPred prediction results are used as intermediate input, using its intermediate neural network output could be a better choice than using its the final prediction result. | TRID-ID TR06-10

Technical report TR05-06. The availability of complete genomic sequences allows us to infer the evolutionary footprints between species in a global strategy. However, the length of these genomic sequences poses a challenge on computational efficiency and optimality of information representation in phylogenetic analyses. In this paper, a new method called complete composition vector (CCV) is described to infer evolutionary relationships between species using their complete genomic sequences. In this method, the character string frequencies in the complete genomic sequence of each species are represented by a complete composition vector in a high-dimensional space. After being filtered out the random mutation background, cosines of the angles between the representing vectors are converted into pairwise evolutionary distances, based on which the phylogeny tree is constructed using the neighbor-joining algorithm. The method bypasses the complexity of performing multiple sequence alignments and avoids the ambiguity of choosing individual genes, whereas is expected to effectively retain the rich evolutionary information contained in the whole genomic sequence. To verify its strengths, the method was applied to infer the evolutionary footprints of coronaviruses and microbes. On a typical desktop PC, it took only one and half days to construct the phylogeny for 109 species containing 103 microbes and 6 eukaryotes. The phylogenetic trees generated by our method are highly consistent with those annotated by biologists. | TRID-ID TR05-06

Technical report TR05-18. Reconstruction of an evolutionary history for a set of organisms is an important research subject in computational biology. One approach motivated by graph theory constructs a relationship graph based on pairwise evolutionary closeness. The approach builds a tree representation equivalent to this graph such that leaves of the tree, corresponding to the organisms, are within a specified distance of k in the tree if connected in the relationship graph. This problem, the kth phylogenetic root construction, has known linear time algorithms for k = 5. We present a polynomial time algorithm for strictly chordal relationship graphs if k = 5. | TRID-ID TR05-18