A shortest cycle for each vertex of a graph

We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in $1,\dots ,M$, it runs in $\stackrel{?}{O}(\sqrt{M}{n}^{(\omega +3)/2})$ time where $\omega <2.376$ is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in $\stackrel{?}{O}(M{n}^{\omega }t)$ time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ? in $\stackrel{?}{O}(n^{(\omega +6)/3})$ time.     

On the applicability of Postʼs lattice

For decision problems $\Pi (B)$ defined over Boolean circuits using gates from a restricted set B only, we have $\Pi (B){?}_m^{{\mathrm{AC}}^0}\Pi (B^{\prime })$ for all finite sets B and $B^{\prime }$ of gates such that all gates from B can be computed by circuits over gates from $B^{\prime }$. In this note, we show that a weaker version of this statement holds for decision problems defined over Boolean formulae, namely that $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{\wedge ,\vee \})$ and $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{0,1\})$ for all finite sets B and $B^{\prime }$ of Boolean functions such that all $f\in B$ can be defined in $B^{\prime }$.     

Proximity and average eccentricity of a graph

Let $G=(V,E)$ be a connected graph on n vertices. The proximity $\pi (G)$ of G is the minimum average distance from a vertex of G to all others. The eccentricity $e(v)$ of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity $\mathit{ecc}(G)$ of the graph G is $\frac{1}{n}{\sum }_{v\in V(G)}e(v)$. Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on $n?3$ vertices, $\mathit{ecc}(G)?\pi (G)?\mathit{ecc}(P_n)?\pi (P_n)$, with equality if and only if $G?P_n$. In this paper, we show that this conjecture is true.     

Approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph $G=(V,E)$ with edge-weights $w:E\to {\mathbb{R}}_{\ge 0}$ and vertex-weights $\eta :V\to {\mathbb{R}}_{+}$ are given. The goal is to find a vertex set $S\subseteq V$ with $|S|\le t$ while minimizing $w(S,V\backslash S)/\eta (S)$, where $w(S,V\backslash S)$ is the total weight of the edges with exactly one endpoint in S and $\eta (S)={\sum }_{v\in S}\eta (v)$. For this problem, we present a $(O(\log t),1+ϵ)$ factor bicriteria approximation algorithm. Our algorithm outperforms the current best algorithm when $t=n^{o(1)}$. We also present better approximation algorithms for Weighted ρ-Unbalanced Cut and Min–Max k-Partitioning problems.