Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branch-and-reduce paradigm is the de facto standard approach to solve the problem to optimality in practice. In this paradigm, data reduction rules are applied to decrease the problem size. These data reduction rules ensure that given an optimum solution on the new (smaller) input, one can quickly construct an optimum solution on the original input. We introduce new generalized data reduction and transformation rules for the problem. A key feature of our work is that some transformation rules can increase the size of the input. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later throughout the algorithm. In experiments, our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than heuristic solvers DynWVC and HILS on many instances. While the increasing transformations are only efficient enough for preprocessing at this time, we see this as a critical initial step towards a new branch-and-transform paradigm.

It is known that the legal coloring of the nodes of a given graph can be reduced to a clique search problem. This paper generalizes this result for hypergraphs. Namely, we will show how legal coloring of the nodes of a hypergraph can be reduced to clique search in a uniform hypergraph. Replacing ordinary graphs by hypergraphs extends the descriptive power of graph models. In addition searching cliques in uniform hypergraphs may improve the efficiency of computations. As an illustration we will apply the reformulation technique to a hypergraph coloring problem due to Voloshin.

To carry out a clique search in a given graph in a parallel fashion, one divides the problem into a very large number of smaller instances. To sort out as many resulted smaller problems as possible, one can rely on upper estimates of the clique sizes. Legal coloring of the nodes of the graphs is a commonly used tool to establish upper bound of the clique size. We will point out that coloring of the nodes can also be used to divide the clique search problem into smaller ones. We will introduce a non-conventional coloring of the edges of the given graph. We will gather theoretical and computational evidence that the proposed edge coloring provides better estimates for the clique size than the node coloring and can be used to divide the original problem into subproblems.