Search for: All records

A sparsification of a given graph G is a sparser graph (typically a subgraph) which aims to approximate or preserve some property of G. Examples of sparsifications include but are not limited to spanning trees, Steiner trees, spanners, emulators, and distance preservers. Each vertex has the same priority in all of these problems. However, real-world graphs typically assign different “priorities” or “levels” to different vertices, in which higher-priority vertices require higher-quality connectivity between them. Multi-priority variants of the Steiner tree problem have been studied in prior literature but this generalization is much less studied for other sparsification problems. In this paper, we define a generalized multi-priority problem and present a rounding-up approach that can be used for a variety of graph sparsifications. Our analysis provides a systematic way to compute approximate solutions to multi-priority variants of a wide range of graph sparsification problems given access to a single-priority subroutine. 

The abundance of scientific articles published and indexed in publicly accessible repositories has spurred the research and development of automated information extraction systems. The output of such systems can be used to assemble large networks capturing the understanding of mechanistic pathways and their interactions as represented in the underlying body of research. We describe a system designed to help researchers search, visualize and interact with biological networks derived via information extraction tools. As input, the system takes a dataset of biological and biochemical interactions automatically generated by an information extraction system and provides an interface designed to search, visualize and interact with the data. The usage paradigm consists of identifying a starting point for a search, then using the data’s network structure by incrementally exploring the immediate neighborhood of the elements displayed by the system. 

A decision tree recursively splits a feature space Rd and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine- learning toolkit for decades. A large body of work treats heuristic algorithms to compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space. We show that it can be solved in O(n2d+1d) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f (d) · no(d/ log d) running time, where n is the number of training examples. The problem is solvable in (dR)O(dR) · n1+o(1) time, if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class. 

When interacting with a visualization of a bipartite graph, one of the most common tasks requires identifying the neighbors of a given vertex. In interactive visualizations, selecting a vertex of interest usually highlights the edges to its neighbors while hiding/shading the rest of the graph. If the graph is large, the highlighted subgraph may not fit in the display window. This motivates a natural optimization task: find an arrangement of the vertices along two layers that reduces the size of the window needed to see a selected vertex and all its neighbors. We consider two variants of the problem; for one we present an efficient algorithm, while for the other we show NP-hardness and give a 2-approximation.