Parallel Bounded Search for the Maximum Clique Problem

Given an undirected graph,the Maximum Clique Problem(MCP)is to find a largest complete subgraph of the graph.MCP is NP-hard and has found many practical applications.In this paper,we propose a parallel Branch-and-Bound(BnB)algorithm to tackle this NP-hard problem,which carries out multiple bounded searches in parallel.Each search has its upper bound and shares a lower bound with the rest of the searches.The potential benefit of the proposed approach is that an active search terminates as soon as the best lower bound found so far reaches or exceeds its upper bound.We describe the implementation of our highly scalable and efficient parallel MCP algorithm,called PBS,which is based on a state-of-the-art sequential MCP algorithm.The proposed algorithm PBS is evaluated on hard DIMACS and BHOSLIB instances.The results show that PBS achieves a near-linear speedup on most DIMACS instances and a superlinear speedup on most BHOSLIB instances.Finally,we give a detailed analysis that explains the good speedups achieved for the tested instances.

Maximum Cliques of Hypergraphs and Polynomial Optimization

A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Bul′o and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by studying the relation of local（global） minimizers of a homogeneous polynomial function of degree r and the maximal（maximum） cliques of an r-uniform hypergraph. In this paper, we study polynomial optimization problems for non-uniform hypergraphs with four different types of edges and apply it to get an upper bound of Tur′an densities of complete non-uniform hypergraphs.

Maximum Independent Sets and Supervised Learning

The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted,with measurable effects on the quality of the solutions provided on unseen instances.Empirical results are presented to validate the idea..

Connection Between Continuous Optimization and Turán Densities of Non-uniform Hypergraphs

A classical result of Motzkin and Straus established the connection between the Lagrangian of a graph and its maximum cliques.Applying it,they gave a new proof of Turán’s theorem.This aroused the interests in studying the connection between continuous optimization and extremal problems in combinatorics.In 2009,S.Rota Bulòand M.Pelillo extended the result of Motzkin-Straus to r-uniform hypergraphs.Recently,Johnston and Lu initiated the study of the Turán density of a non-uniform hypergraph.Polynomial optimization problems related to several types of non-uniform hypergraphs and its applications on Turán densities have also been studied.In this paper,we obtain a Motzkin-Straus type of results for all non-uniform hypergraphs.Applying it,we give an upper bound of the Turán density of a complete non-uniform hypergraph.