Quantum processing units (QPUs) executing annealing algorithms have shown promise in optimization and simulation applications. Hybrid algorithms are a natural bridge to larger applications. We present a simple greedy method for solving larger-than-QPU lattice-structured Ising optimization problems. The method, implemented in the open source D-Wave Hybrid framework, uses a QPU coprocessor operating with generic parameters. Performance is evaluated for standard spin-glass problems on two lattice types with up to 11,616 spin variables, double the size that is directly programmable on any available QPU. The proposed method is shown to converge to low-energy solutions faster than an open source simulated annealing method that is either directly employed or substituted as a coprocessor in the hybrid method. Using newer Advantage QPUs in place of D-Wave 2000Q QPUs is shown to enhance convergence of the hybrid method to low energies and to achieve a lower final energy.

SAT filters are a novel and compact data structure that can be used to quickly query a word for membership in a fixed set. They have the potential to store more information in a fixed storage limit than a Bloom filter. Constructing a SAT filter requires sampling diverse solutions to randomly constructed constraint satisfaction instances, but there is flexibility in the choice of constraint satisfaction problem. Presented here is a case study of SAT filter construction with a focus on constraint satisfaction problems based on MAX-CUT clauses (Not-all-equal 3-SAT, 2-in-4-SAT, etc.) and frustrated cycles in the Ising model. Solutions are sampled using a D-Wave quantum annealer, and results are measured against classical approaches. The SAT variants studied are of interest in the context of SAT filters, independent of the solvers used.

Reed's $\omega$, $\Delta$, $\chi$ conjecture proposes that every graph satisfies $\chi\leq \lceil\frac 12(\Delta+1+\omega)\rceil$; it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colorings that achieve our bounds: $O(n^2)$ for line graphs and $O(n^3m^2)$ for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a coloring that achieves the bound of Reed's original conjecture.

King, Lu, and Peng recently proved that for $\Delta\geq 4$, any $K_\Delta$-free graph with maximum degree $\Delta$ has fractional chromatic number at most $\Delta-\tfrac{2}{67}$ unless it is isomorphic to $C_5\boxtimes K_2$ or $C_8^2$. Using a different approach we give improved bounds for $\Delta\geq 6$ and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's $\omega$, $\Delta$, $\chi$ conjecture.

Let $\Delta(G)$ be the maximum degree of a graph G. Brooks' theorem states that the only connected graphs with chromatic number $\chi(G)=\Delta(G)+1$ are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs G such that the fractional chromatic number $\chi_f(G)$ is at least $\Delta(G)$. These graphs are complete graphs, odd cycles, $C^2_8$, $C_5\boxtimes K_2$, and graphs whose clique number $\omega(G)$ equals the maximum degree $\Delta(G)$. Among the two sporadic graphs, the graph $C^2_8$ is the square graph of cycle $C_8$, while the other graph $C_5\boxtimes K_2$ is the strong product of $C_5$ and $K_2$. In fact, we prove a stronger result: If a connected graph G with $\Delta(G)\geq 4$ is not one of the graphs listed above, then we have $\chi_f(G)\leq \Delta(G)- \frac{2}{67}$.

MOTIVATION: Understanding principles of cellular organization and function can be enhanced if we detect known and predict still undiscovered protein complexes within the cell's protein-protein interaction (PPI) network. Such predictions may be used as an inexpensive tool to direct biological experiments. The increasing amount of available PPI data necessitates an accurate and scalable approach to protein complex identification. RESULTS: We have developed the Restricted Neighborhood Search Clustering Algorithm (RNSC) to efficiently partition networks into clusters using a cost function. We applied this cost-based clustering algorithm to PPI networks of Saccharomyces cerevisiae, Drosophila melanogaster and Caenorhabditis elegans to identify and predict protein complexes. We have determined functional and graph-theoretic properties of true protein complexes from the MIPS database. Based on these properties, we defined filters to distinguish between identified network clusters and true protein complexes. CONCLUSIONS: Our application of the cost-based clustering algorithm provides an accurate and scalable method of detecting and predicting protein complexes within a PPI network.