A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.     

Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class.     

Optimal 1-edge fault-tolerant designs for ladders

A graph G∗ is 1-edge fault-tolerant with respect to a graph G, denoted by 1-EFT(G), if every graph obtained by removing any edge from G∗ contains G. A 1-EFT(G) graph is optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. The kth ladder graph, L_k, is defined to be the cartesian product of the P_k and P₂ where P_n is the n-vertex path graph. In this paper, we present several 1-edge fault-tolerant graphs with respect to ladders. Some of these graphs are proven to be optimal.     

The rotation graph of k-ary trees is Hamiltonian

In this paper we show that the graph of k-ary trees, connected by rotations, contains a Hamilton cycle. Our proof is constructive and thus provides a cyclic Gray code for k-ary trees. Furthermore, we identify a basic building block of this graph as the 1-skeleton of the polytopal complex dual to the lower faces of a certain cyclic polytope.     

Average-Case Analysis of Dynamic Graph Algorithms

We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for the following problems: maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex connectivity, and bipartiteness. Given a random graph G with m ₀ edges and n vertices and a sequence of l update operations such that the graph contains m _i edges after operation i , the expected time for performing the updates for any l is in the case of minimum spanning forests, connectivity, 2-edge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. We also give improved bounds for k -edge and k -vertex connectivity. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion. Received June 11, 1995; revised March 8, 1996.     

Optimal per-edge processing times in the semi-streaming model

We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to bits.Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(α(n)), for determining k-vertex and k-edge connectivity O(k²n) and O(n⋅logn) respectively for any constant k and for computing a minimum spanning forest O(logn). All these time bounds we reduce to O(1).Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems.     

Approximating Biconnectivity in Parallel

Consider the following NP-hard problems: Given a graph G , find minimum 2-edge connected and 2-vertex connected subgraphs spanning all vertices of G . Over the past few years, exciting sequential algorithms for approximating such minimum subgraphs have been produced [6],[10]. The approximation factors are improved from 2 to 3/2 for both of the problems. Yet the techniques involved are all based on augmenting depth-first-search trees and no similar progress has been carried to the parallel context. This paper presents NC algorithms to achieve approximation factors of 3/2 + ε for these two problems without computing depth-first-search trees. Received June 21, 1995; revised December 24, 1996, and June 2, 1997.     

Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs

A set of k spanning trees rooted at the same vertex r in a graph G is said to be independent if for each vertex x other than r, the k paths from r to x, one path in each spanning tree, are internally disjoint. Using independent spanning trees (ISTs) one can design fault-tolerant broadcasting schemes and increase message security in a network. Thus, the problem of ISTs on graphs has been received much attention. Recently, Yang et al. proposed a parallel algorithm for generating optimal ISTs on the hypercube. In this paper, we propose a similar algorithm for generating optimal ISTs on Cartesian product of complete graphs. The algorithm can be easily implemented in parallel or distributed systems. Moreover, the proof of its correctness is simpler than that of Yang et al.     

Constructing a minimum height elimination tree of a tree in linear time

Given a graph, finding an optimal vertex ranking and constructing a minimum height elimination tree are two related problems. However, an optimal vertex ranking does not by itself provide enough information to construct an elimination tree of minimum height. On the other hand, an optimal vertex ranking can readily be found directly from an elimination tree of minimum height. On n-vertex trees, the optimal vertex ranking problem already has a linear-time algorithm in the literature. However, there is no linear-time algorithm for the problem of finding a minimum height elimination tree. A naive algorithm for this problem requires O(nlogn) time. In this paper, we propose a linear-time algorithm for constructing a minimum height elimination tree of a tree.     

The spanning connectivity of folded hypercubes

A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ_n is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2.     

Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes

Fault-tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and of security. A set of spanning trees in a graph is said to be edge-disjoint if these trees are rooted at the same node without sharing any common edge. Hsieh and Tu [S.-Y. Hsieh, C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science 410 (2009) 926-932] recently presented an algorithm for constructing n edge-disjoint spanning trees in an n-dimensional locally twisted cube. In this paper, we prove that indeed all spanning trees constructed by their algorithm are independent, i.e., any two spanning trees are rooted at the same node, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint.     

Parameterized complexity of connected even/odd subgraph problems

In 2011, Cai an Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs: for a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about:

•

a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and     

Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds

Edge coloring, total coloring and L(2,1)-labeling are well-studied NP-hard graph problems. Even the versions asking whether a graph has a coloring with few colors or a labeling with few labels remain NP-hard on graphs of small maximum degree. This paper studies enumeration and counting problems on edge colorings, total colorings and L(2,1)-labelings of graphs. One part deals with the enumeration of all edge 3-colorings, all total 4-colorings and all L(2,1)-labelings of span 5 of a given connected cubic graph. Branching algorithms to solve these enumeration problems are established. They imply upper bounds on the maximum number of edge 3-colorings, total 4-colorings and L(2,1)-labelings of span 5 in any n-vertex connected cubic graphs. Corresponding combinatorial lower bounds are also provided. The other part of the paper studies dynamic programming algorithms solving counting problems. On one hand, algorithms to count the number of edge k-colorings and total k-colorings for graphs of bounded pathwidth are given. On the other hand, an algorithm to count the number of L(2,1)-labelings of span 4 for graphs of maximum degree three are given.     

Distributed algorithms for finding and maintaining a k-tree core in a dynamic network

A k-core C_k of a tree T is subtree with exactly k leaves for k?n_l, where n_l the number of leaves in T, and minimizes the sum of the distances of all nodes from C_k. In this paper first we propose a distributed algorithm for constructing a rooted spanning tree of a dynamic graph such that root of the tree is located near the center of the graph. Then we provide a distributed algorithm for finding k-core of that spanning tree. The spanning tree is constructed in two stages. In the first stage, a forest of trees is generated. In the next stage these trees are connected to form a single rooted tree. An interesting aspect of the first stage of proposed spanning algorithm is that it implicitly constructs the (convex) hull of those nodes which are not already included in the spanning forest. The process is repeated till all non root nodes of the graph have chosen a unique parent. We implemented the algorithms for finding spanning tree and its k-core. A core can be quite useful for routing messages in a dynamic network consisting of a set of mobile devices.     

Variable neighborhood search for extremal graphs: IV: Chemical trees with extremal connectivity index

By means of the variable neighborhood search algorithm, a newly designed heuristic approach to combinatorial optimization, we established the structure of the chemical trees possessing extremal (maximal and minimal) values for the Randić connectivity index (χ). These findings were eventually corroborated by rigorous mathematical proofs. As could have been anticipated, the n-vertex tree with maximum χ is the path. The n-vertex chemical tree with minimum χ-value is not unique. The structures of such chemical trees (which should be considered as the graph representations of the most branched alkanes) are fully characterized.     

Manifold-ranking based retrieval using k-regular nearest neighbor graph

Manifold-ranking is a powerful method in semi-supervised learning, and its performance heavily depends on the quality of the constructed graph. In this paper, we propose a novel graph structure named k-regular nearest neighbor (k-RNN) graph as well as its constructing algorithm, and apply the new graph structure in the framework of manifold-ranking based retrieval. We show that the manifold-ranking algorithm based on our proposed graph structure performs better than that of the existing graph structures such as k-nearest neighbor (k-NN) graph and connected graph in image retrieval, 2D data clustering as well as 3D model retrieval. In addition, the automatic sample reweighting and graph updating algorithms are presented for the relevance feedback of our algorithm. Experiments demonstrate that the proposed algorithm outperforms the state-of-the-art algorithms.     

随机可满足实例集上警示传播算法的收敛性

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d＜1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.     

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs

We prove lower bounds on the complexity of maintaining fully dynamic k -edge or k -vertex connectivity in plane graphs and in (k-1) -vertex connected graphs. We show an amortized lower bound of (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model, where b is the word size of the machine and n is the number of vertices in G . We also show an amortized lower bound of (log n /(log log n + log b)) per operation for fully dynamic planarity testing in embedded graphs. These are the first lower bounds for fully dynamic connectivity problems. Received January 1995; revised February 1997.     

Efficient DNA sticker algorithms for NP-complete graph problems

Adleman's successful solution of a seven-vertex instance of the NP-complete Hamiltonian directed path problem by a DNA algorithm initiated the field of biomolecular computing. We provide DNA algorithms based on the sticker model to compute all k-cliques, independent k-sets, Hamiltonian paths, and Steiner trees with respect to a given edge or vertex set. The algorithms determine not merely the existence of a solution but yield all solutions (if any). For an undirected graph with n vertices and m edges, the running time of the algorithms is linear in n+m. For this, the sticker algorithms make use of small combinatorial input libraries instead of commonly used large libraries. The described algorithms are entirely theoretical in nature. They may become very useful in practice, when further advances in biotechnology lead to an efficient implementation of the sticker model.     

Finding and counting cliques and independent sets in r-uniform hypergraphs

We present a matrix multiplication based algorithm for counting the number of (induced) occurrences of a fixed r-uniform hypergraph in a larger hypergraph. In many cases, the running time is better than that of the naïve algorithm. We also present several useful applications of the algorithm, such as determining the dominant color among monochromatic simplices in a red-blue edge-colored hypergraph, approximating the number of independent simplices in a random hypergraph, and counting induced occurrences of a given 3-uniform k-vertex hypergraph in a larger k-clique free hypergraph.