Testing hypergraph colorability

We study the problem of testing properties of hypergraphs. The goal of property testing is to distinguish between the case whether a given object has a certain property or is “far away” from the property. We prove that the fundamental problem of $\ell$-colorability of k-uniform hypergraphs can be tested in time independent of the size of the hypergraph. We present a testing algorithm that examines only $(k\ell /\epsilon {)}^{\mathrm{O}(k)}$ entries of the adjacency matrix of the input hypergraph, where $\epsilon$ is a distance parameter independent of the size of the hypergraph. The algorithm tests only a constant number of entries in the adjacency matrix provided that $\ell$, k, and $\epsilon$ are constants. This result is a generalization of previous results about testing graph colorability.     

Highly concurrent multi-word synchronization

The design of concurrent data structures is greatly facilitated by the availability of synchronization operations that atomically modify $k$ arbitrary items, such as $k$-read–modify–write ($k\text{<mi mathsize="small" is="true">RMW</mi>}$). Aiming to increase concurrency in order to exploit the parallelism offered by today’s multi-core and multi-processing architectures, we propose a highly concurrent software implementation of $k\text{<mi mathsize="small" is="true">RMW</mi>}$, with only constant space overhead. Our algorithm ensures that two operations delay each other only if they are within distance $O\left(k\right)$ in the conflict graph, induced by the operations’ data items.The algorithm uses double compare-and-swap (dcas). When dcas is not supported by the architecture, the algorithm of Attiya and Dagan (2001) [3] can be used to replace dcas with (unary) cas, with only a slight increase in the interference among operations.     

Uniform unweighted set cover: The power of non-oblivious local search

We are given $n$ base elements and a finite collection of subsets of them. The size of any subset varies between $p$ to $k$ ($p<k$). In addition, we assume that the input contains all possible subsets of size $p$. Our objective is to find a subcollection of minimum-cardinality which covers all the elements. This problem is known to be NP-hard. We provide two approximation algorithms for it, one for the generic case, and an improved one for the special case of $(p,k)=(2,4)$.The algorithm for the generic case is a greedy one, based on packing phases: at each phase we pick a collection of disjoint subsets covering $i$ new elements, starting from $i=k$ down to $i=p+1$. At a final step we cover the remaining base elements by the subsets of size $p$. We derive the exact performance guarantee of this algorithm for all values of $k$ and $p$, which is less than $H_k$, where $H_k$ is the $k$’th harmonic number. However, the algorithm exhibits the known improvement methods over the greedy one for the unweighted $k$-set cover problem (in which subset sizes are only restricted not to exceed $k$), and hence it serves as a benchmark for our improved algorithm.The improved algorithm for the special case of $(p,k)=(2,4)$ is based on non-oblivious local search: it starts with a feasible cover, and then repeatedly tries to replace sets of size 3 and 4 so as to maximize an objective function which prefers big sets over small ones. For this case, our generic algorithm achieves an asymptotic approximation ratio of $1.5+?$, and the local search algorithm achieves a better ratio, which is bounded by $1.458333\dots +?$.     

The complexity of approximately counting stable roommate assignments

We investigate the complexity of approximately counting stable roommate assignments in two models: (i) the k-attribute model, in which the preference lists are determined by dot products of “preference vectors” with “attribute vectors” and (ii) the k-Euclidean model, in which the preference lists are determined by the closeness of the “positions” of the people to their “preferred positions”. Exactly counting the number of assignments is #P-complete, since Irving and Leather demonstrated #P-completeness for the special case of the stable marriage problem (Irving and Leather, 1986 [11]). We show that counting the number of stable roommate assignments in the k-attribute model (#k-attribute SR, $k?4$) and the 3-Euclidean model (#k-Euclidean SR, $k?3$) is interreducible, in an approximation-preserving sense, with counting independent sets (of all sizes) ($\mathrm{\#}\mathit{IS}$) in a graph, or counting the number of satisfying assignments of a Boolean formula ($\mathrm{\#}\mathit{SAT}$). This means that there can be no FPRAS for any of these problems unless NP = RP. As a consequence, we infer that there is no FPRAS for counting stable roommate assignments ($\mathrm{\#}\mathit{SR}$) unless NP = RP. Utilizing previous results by Chebolu, Goldberg and Martin (2010) [3], we give an approximation-preserving reduction from counting the number of independent sets in a bipartite graph ($\mathrm{\#}\mathit{BIS}$) to counting the number of stable roommate assignments both in the 3-attribute model and in the 2-Euclidean model. $\mathrm{\#}\mathit{BIS}$ is complete with respect to approximation-preserving reductions in the logically-defined complexity class $\mathrm{\#}\mathrm{RH}{\mathrm{\Pi }}_1$. Hence, our result shows that an FPRAS for counting stable roommate assignments in the 3-attribute model would give an FPRAS for all $\mathrm{\#}\mathrm{RH}{\mathrm{\Pi }}_1$. We also show that the 1-attribute stable roommate problem always has either one or two stable roommate assignments, so the number of assignments can be determined exactly in polynomial time.     

Faster gossiping on butterfly networks

Gossiping has been considered intensively for butterflies and “simple” butterflies (which have no wrap-around connections). In the “telephone” communication model, for a butterfly of order k, the best previous gossiping algorithms require $2\frac{1}{2}k$ and $3k$ communication rounds, respectively. By new asymptotic methods we break through these bounds. We show that gossiping on a class of “column-based” networks, which also contains the cube-connected cycles, can be reduced to the simpler problem of “row-gossiping”. Row-gossiping in turn is reduced to “coherent row-broadcasting”. This latter problem is sufficiently simple to be solved by a sophisticated computer program for butterflies with up to $15\times 2^{15}$ nodes. Out of the produced solutions a pattern is distilled, which can be used to perform gossiping on butterflies and simple butterflies of order k in $2\frac{1}{4}k+\mathrm{o}(k)$ and $2\frac{1}{2}k+\mathrm{o}(k)$ rounds, respectively, for any k, considerably reducing the gap with the lower bounds. The new upper bounds also hold for gossiping in the weaker “telegraph” model.     

Brooksʼ Theorem for generalized dart graphs

The well-known Brooks? Theorem says that each graph G of maximum degree $k?3$ is k-colorable unless $G=K_{k+1}$. We generalize this theorem by allowing higher degree vertices with prescribed types of neighborhood.     

A dynamic programming solution to a generalized LCS problem

In this paper, we consider a generalized longest common subsequence problem, the string-excluding constrained LCS problem. For the two input sequences X and Y of lengths n and m, and a constraint string P of length r, the problem is to find a common subsequence Z of X and Y excluding P as a substring and the length of Z is maximized. The problem and its solution were first proposed by Chen and Chao (2011) [1], but we found that their algorithm cannot solve the problem correctly. A new dynamic programming solution for the STR-EC-LCS problem is then presented in this paper. The correctness of the new algorithm is proved. The time complexity of the new algorithm is $O(nmr)$.     

The Steiner traveling salesman problem with online advanced edge blockages

The package delivery in an urban road network is formulated as an online Steiner traveling salesman problem, where the driver (i.e. the salesman) receives road (i.e. edge) blockage messages when he is at a certain distance to the respective blocked edges. Such road blockages are referred to as advanced information. With these online advanced road blockages, the driver wishes to deliver all the packages to their respective customers and returns back to the service depot through a shortest route. During the entire delivery process, there will be at most k road blockages, and they are non-recoverable. When the driver knows about road blockages at a distance $\alpha \mathrm{OPT}$, where $\alpha \in [0,1]$ is referred to as the forecasting ratio and OPT denotes the length of the offline shortest route, we first prove that $\max \left\{\right(1-2\alpha )k+1,1\}$ is a lower bound on the competitive ratio. We then present a polynomial time online algorithm with a competitive ratio very close to this lower bound. Computational results show that our algorithm is efficient and produces near optimal solutions. Similar results for a variation, in which the driver does not need to return to the service depot, are also achieved.