Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Given an unweighted undirected or directed graph with n vertices, m edges and edge connectivity c, we present a new deterministic algorithm for edge splitting. Our algorithm splits-off any specified subset S of vertices satisfying standard conditions (even degree for the undirected case and in-degree ≥ out-degree for the directed case) while maintaining connectivity c for vertices outside S in Õ(m+nc2) time for an undirected graph and Õ(mc) time for a directed graph. This improves the current best deterministic time bounds due to Gabow [8], who splits-off a single vertex in Õ(nc2+m) time for an undirected graph and Õ(mc) time for a directed graph. Further, for appropriate ranges of n, c, |S| it improves the current best randomized bounds due to Benczúr and Karger [2], who split-off a single vertex in an undirected graph in Õ(n2) Monte Carlo time. We give two applications of our edge splitting algorithms. Our first application is a sub-quadratic (in n) algorithm to construct Edmonds' arborescences. A classical result of Edmonds [5] shows that an unweighted directed graph with c edge-disjoint paths from any particular vertex r to every other vertex has exactly c edge-disjoint arborescences rooted at r. For a c edge connected unweighted undirected graph, the same theorem holds on the digraph obtained by replacing each undirected edge by two directed edges, one in each direction. The current fastest construction of these arborescences by Gabow [7] takes Õ(n2c2) time. Our algorithm takes Õ(nc3+m) time for the undirected case and Õ(nc4+mc) time for the directed case. The second application of our splitting algorithm is a new Steiner edge connectivity algorithm for undirected graphs which matches the best known bound of Õ(nc2 + m) time due to Bhalgat et al [3]. Finally, our algorithm can also be viewed as an alternative proof for existential edge splitting theorems due to Lovász [9] and Mader [11].

Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

Amphiphilic poly(meta-phenylene)s: A novel conjugated polysoap; A possible foldamer?

Novel amphiphilic poly(meta-phenylene)s were prepared by an oxidative coupling approach. These polymers were synthesized to shed light on their solution properties with special emphasis on aggregation and folding behavior. The polymers were characterized by NMR spectroscopy and molecular weights were determined by Gel Permeation Chromatography using Universal calibration. Literature studies revealed that the backbone of these PMPs can be helical moreover, the light emitting properties of this conjugated polymer can be used as a handle to study the possible aggregation or self-assembling behavior. In this report we show the synthesis, characterization and preliminary aggregation properties that points out that one of the synthesized PMP behave as a polysoap.

Haloarchaeal gas vesicle nanoparticles displaying Salmonella antigens as a novel approach to vaccine development

A safe, effective, and inexpensive vaccine against typhoid and other Salmonella diseases is urgently needed. In order to address this need, we are developing a novel vaccine platform employing buoyant, self-adjuvanting gas vesicle nanoparticles (GVNPs) from the halophilic archaeon Halobacterium sp. NRC-1, bioengineered to display highly conserved Salmonella enterica antigens. As the initial antigen for testing, we selected SopB, a secreted inosine phosphate effector protein injected by pathogenic S. enterica bacteria during infection into the host cells. Two highly conserved sopB gene segments near the 3'- region, named sopB4 and sopB5, were each fused to the grIpC gene, and resulting SopB-GVNPs were purified by centrifugally accelerated flotation. Display of SopB4 and SopB5 antigenic epitopes on GVNPs was established by Western blotting analysis using antisera raised against short synthetic peptides of SopB. Immunostimulatory activities of the SopB4 and B5 nanoparticles were tested by intraperitoneal administration of SopB-GVNPs to BALB/c mice which had been immunized with S. enterica serovar Typhimurium 14028 ApmrG-H111-D (DV-STM-07), a live attenuated vaccine strain. Proinflammatory cytokines IFN-y, IL-2, and IL-9 were significantly induced in mice boosted with SopB5-GVNPs, consistent with a robust Thl response. After challenge with virulent S. enterica serovar Typhimurium 14028, bacterial burden was found to be diminished in spleen of mice boosted with SopB4-GVNPs and absent or significantly diminished in liver, mesenteric lymph node, and spleen of mice boosted with SopB5GVNPs, indicating that the C-terminal portions of SopB displayed on GVNPs elicit a protective response to Salmonella infection in mice. SopB antigen-GVNPs were also found to be stable at elevated temperatures for extended periods without refrigeration. The results show that bioengineered GVNPs are likely to represent a valuable platform for antigen delivery and development of improved vaccines against Salmonella and other diseases.

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

We show here a 2(Omega(root d.log N)) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d(3) in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Sigma(i) Pi(j) Q(ij), where the Q(ij)'s are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that Sigma(i,j) (Number of monomials of Q(ij)) >= 2(Omega(root d.log N)). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on the recent lower bound results 1], 2], 3], 4], 5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of 6] and the N-Omega(log log (N)) lower bound in the independent work of 7].