Search

Let G be a graph with m edges, minimum degree $\delta $ and containing no cycle of length 4. Answering a question of Bollobás and Scott, Fan et al. ['Bisections of graphs without short cycles', Combinatorics, Probability and Computing 27 (1) (2018), 44–59] showed that if (i) G is $2$ -connected, or (ii) $\delta \ge 3$ , or (iii) $\delta \ge 2$ and the girth of G is at least 5, then G admits a bisection such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$ , where $e(V_i)$ denotes the number of edges of G with both ends in $V_i$. Let $s\ge 2$ be an integer. In this note, we prove that if $\delta \ge 2s-1$ and G contains no $K_{2,s}$ as a subgraph, then G admits a bisection such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$. [ABSTRACT FROM AUTHOR]

The rapid development of quantum computing has opened up entirely new possibilities for the field of machine learning. However, for the implementation of many existing quantum classification algorithms, a large number of qubits and quantum circuits with high complexity are still required. To effectively solve this problem, the Quantum Approximate Optimization Algorithm (QAOA) arises as a promising solution due to its comparative advantages. In particular, it can be realized in the case of shallow quantum circuits and a finite small number of qubits. Along these lines, in this work, a Max-Cut linear binary classifier based on QAOA (QAOA-MaxCut-LBC) was proposed. First, the data set was constructed into an undirected weighted graph, and the binary classification task was transformed into a Max-Cut problem. Then, a Variational Quantum Circuit (VQC) was built by using QAOA, and the expected value of the target Hamiltonian was transformed into a loss function. Finally, the circuit parameters were iteratively updated to make the loss function converge. The computational basis state with the maximum probability was taken as the classification result after the measurement. In the experimental study, our algorithm was validated on various datasets and compared with classical linear classifiers. Our scheme can be flexibly adjusted for the number of qubits, possessing the potential to scale to multi-classification tasks. The source code is accessible at the URL: . [ABSTRACT FROM AUTHOR]

Summary Oscillator‐based Ising machines (OIMs) particularly those realized in complementary metal oxide semiconductor (CMOS) have gained popularity for solving combinatorial optimization problems (COPs) in recent years due to its scalability, low‐power consumption, and room temperature operation. The implemented OIMs have thus far focused on solving optimization problems with a single global minima. However, real‐life optimization problems often have multiple solutions. In this paper, we propose a generalized approach to solve COPs with single (without contention), as well as multiple (with contention) solutions using frequency tunable CMOS ring oscillator (ROSC)‐based Ising machine. A capacitive frequency tunable CMOS ring‐oscillator coupled with an internal subharmonic injection locking (SHIL) generator realized using 14‐nm FinFET models works as Ising spin in the proposed approach. We demonstrate how frequency tuning can help in attaining good quality results and also determine all possible solutions of COP with contention. We also propose a generalized algorithm for monitoring the states of the oscillator network to indicate tuning necessity and extract solutions from the oscillator's output irrespective of the type of COP. [ABSTRACT FROM AUTHOR]

Combinatorial optimization (CO) has a broad range of applications in various fields, including operations research, computer science, and artificial intelligence. However, many of these problems are classified as nondeterministic polynomial‐time (NP)‐complete or NP‐hard problems, which are known for their computational complexity and cannot be solved in polynomial time on traditional digital computers. To address this challenge, continuous‐time Ising machine solvers have been developed, utilizing different physical principles to map CO problems to ground state finding. However, most Ising machine prototypes operate at speeds comparable to digital hardware and rely on binarizing node states, resulting in increased system complexity and further limiting operating speed. To tackle these issues, a novel device‐algorithm co‐design method is proposed for fast sub‐optimal solution finding with low hardware complexity. On the device side, a piezoelectric lithium niobate (LiNbO3) microelectromechanical system (MEMS) oscillator network‐based Ising machine without second‐harmonic injection locking (SHIL) is devised to solve Max‐cut and graph coloring problems. The LiNbO3 oscillator operates at speeds greater than 9 GHz, making it one of the fastest oscillatory Ising machines. System‐wise, an innovative grouping method is used that achieves a performance guarantee of 0.878 for Max‐cut and 0.658 for graph coloring problems, which is comparable to Ising machines that utilize binarization. [ABSTRACT FROM AUTHOR]

Abstract Combinatorial optimization (CO) has a broad range of applications in various fields, including operations research, computer science, and artificial intelligence. However, many of these problems are classified as nondeterministic polynomial‐time (NP)‐complete or NP‐hard problems, which are known for their computational complexity and cannot be solved in polynomial time on traditional digital computers. To address this challenge, continuous‐time Ising machine solvers have been developed, utilizing different physical principles to map CO problems to ground state finding. However, most Ising machine prototypes operate at speeds comparable to digital hardware and rely on binarizing node states, resulting in increased system complexity and further limiting operating speed. To tackle these issues, a novel device‐algorithm co‐design method is proposed for fast sub‐optimal solution finding with low hardware complexity. On the device side, a piezoelectric lithium niobate (LiNbO3) microelectromechanical system (MEMS) oscillator network‐based Ising machine without second‐harmonic injection locking (SHIL) is devised to solve Max‐cut and graph coloring problems. The LiNbO3 oscillator operates at speeds greater than 9 GHz, making it one of the fastest oscillatory Ising machines. System‐wise, an innovative grouping method is used that achieves a performance guarantee of 0.878 for Max‐cut and 0.658 for graph coloring problems, which is comparable to Ising machines that utilize binarization.

For a graph G , let $f(G)$ denote the maximum number of edges in a bipartite subgraph of G. Given a positive integer m and a fixed graph H , let $f(m,H)$ denote the minimum possible cardinality of $f(G)$ , as G ranges over all graphs on m edges that contain no copy of H. We prove bounds on $f(m,H)$ for some bipartite graphs H and give a bound for a conjecture of Alon et al. ['MaxCut in H -free graphs', Combin. Probab. Comput. 14 (2005), 629–647] concerning $f(m,K_{4,s})$. [ABSTRACT FROM AUTHOR]

A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints from the second order Lasserre hierarchy. We explore a variety of approaches for adding a subset of the positive semidefinite constraints of the second order sparse relaxation obtained by using the maximum cliques of the graph's chordal extension. We apply this idea to sparse graphs of different sizes and densities, and provide evidence of its strengths and limitations when compared to the state-of-the-art Max-Cut solver BiqCrunch and the alternative sparse relaxation CS-TSSOS. [ABSTRACT FROM AUTHOR]

AbstractGraph partitioning problem, which is one of the most important topics in graph theory, usually asks for a partition of the vertex set of a graph into pairwise disjoint subsets with various requirements. It comes from the well-known Max-Cut Problem: Given a graph G, find the maximum bipartite subgraph of G. In practice, one often needs to find a partition of a given graph to optimize several quantities simultaneously. Such problems are called judicious partition problems by Bollobás and Scott. In this survey, we present some new results and problems on graph partitioning.

In this paper, we develop a semidefinite relaxation-based branch-and-bound algorithm that exploits the chordal sparsity patterns of the max-cut problem. We first study how the chordal sparsity pattern affects the hardness of a max-cut problem. To do this, we derive a polyhedral relaxation based on the clique decomposition of the chordal sparsity patterns and prove some sufficient conditions for the tightness of this polyhedral relaxation. The theoretical results show that the max-cut problem is easy to solve when the sparsity pattern embedded in the problem has a small treewidth and the number of vertices in the intersection of maximal cliques is small. Based on the theoretical results, we propose a new branching rule called hierarchy branching rule, which utilizes the tree decomposition of the sparsity patterns. We also analyze how the proposed branching rule affects the chordal sparsity patterns embedded in the problem, and explain why it can be effective. The numerical experiments show that the proposed algorithm is superior to those known algorithms using classical branching rules and the state-of-the-art solver BiqCrunch on most instances with sparsity patterns arisen in practical applications. [ABSTRACT FROM AUTHOR]

We consider the Max-Cut problem. Let G=(V,E) be a graph with adjacency matrix (aij)ni,j=1. Burer, Monteiro, and Zhang proposed to find, for n angles {θ1,θ2,...,θn}⊂[0,2π], minima of the energy f(θ1,...,θn)=∑ni,j=1aijcos(θi-θj). Configurations achieving a global minimum leads to a partition of size at least 0.878⋅MAX-CUT(G). This approach is known to be computationally viable and leads to very good results in practice. We prove, for each ε>0, that replacing cos(θi-θj) with an explicit gε(θi-θj) global minima lead to a partition of size at least (1-ε)⋅MAX-CUT(G). This suggests some interesting algorithms that perform well. It also shows that the problem of finding approximate global minima of energy functionals of this type is NP-hard, in general. [ABSTRACT FROM AUTHOR]

We study the following question: How few edges can we delete from any H $H$‐free graph on n $n$ vertices to make the resulting graph k $k$‐colorable? It turns out that various classical problems in extremal graph theory are special cases of this question. For H $H$ any fixed odd cycle, we determine the answer up to a constant factor when n $n$ is sufficiently large. We also prove an upper bound when H $H$ is a fixed clique that we conjecture is tight up to a constant factor, and prove upper bounds for more general families of graphs. We apply our results to get a new bound on the maximum cut of graphs with a forbidden odd cycle in terms of the number of edges. [ABSTRACT FROM AUTHOR]

The maximum cut problem is a typical problem in the quantum approximate optimization algorithm (QAOA), and Ansatz circuit is an important part of the algorithm. In order to reduce the construction cost of various graph structures in Q AOA and improve its stability, this paper analyzed the optimizability of the circuit, combined the point edge storage characteristics of Dijkstra algorithm, proposed a Dijkstra-like optimization algorithm for the circuit, and applied it to the QAOA maximum cut problem. The paper used the Qiskit quantum framework to simulate the correctness of the optimization algorithm and used the real environment of IBM Quantum Composer to perform comparative experiments to verify the stability of the optimization. After comparing with the initial algorithm, the proposed algorithm reduced the CNOT gate by about 40% and significantly improves its stability. The results show that the Dijkstra-like optimization algorithm can optimize the QAOA maximum cut problem of multiple graph structures. [ABSTRACT FROM AUTHOR]

Many NP-hard combinatorial optimization (CO) problems can be cast as a quadratic unconstrained binary optimization model, which maps naturally to an Ising model. The final spin configuration in the Ising model can adiabatically arrive at a solution to a Hamiltonian, given a known set of interactions between spins. We enhance two photonic Ising machines (PIMs) and compare their performance against classical (Gurobi) and quantum (D-Wave) solvers. The temporal multiplexed coherent Ising machine (TMCIM) uses the bistable response of an electro-optic modulator to mimic the spin up and down states. We compare TMCIM performance on Max-cut problems. A spatial photonic Ising machine (SPIM) convolves the wavefront of a coherent laser beam with the pixel distribution of a spatial light modulator to adiabatically achieve a minimum energy configuration, and solve a number partitioning problem (NPP). Our computational results on Max-cut indicate that classical solvers are still a better choice, while our NPP results show that SPIM is better as the problem size increases. In both cases, connectivity in Ising hardware is crucial for performance. Our results also highlight the importance of better understanding which CO problems are most likely to benefit from which type of PIM. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'. [ABSTRACT FROM AUTHOR]

With the slowdown of Moore's law, many emerging electronic devices and computing architectures have been proposed to sustain the performance advancement of computing. Among them, the Ising machine is a non-von-Neumann solver that has received wide attention in recent years. It is capable of solving intractable combinatorial optimization (CO) problems, which are difficult to be solve using conventional digital computers. In fact, many CO problems can be mapped to finding the corresponding ground states of Ising model. At present, Ising machine prototypes based on different physical principles, such as emerging memristive oscillators, have been demonstrated, among which the Ising Hamiltonian solver based on the coupled oscillator network simultaneously holds the advantages of room-temperature operation, compact footprint, low power consumption, and fast speed to solution. This paper comprehensively surveys the recent developments in this important field, including the types of oscillators, the implementation principle of the Ising model, and the solver's performance. Finally, methods to further improve the performance have also been suggested. [ABSTRACT FROM AUTHOR]

The quadratic unconstrained binary optimization (QUBO) problem is categorized as an NP-hard combinatorial optimization problem. The variable neighborhood search (VNS) algorithm is one of the leading algorithms used to solve QUBO problems. As neighborhood structure change is the central concept in the VNS algorithm, the design of the neighborhood structure is crucial. This paper presents a modified VNS algorithm called "B-VNS", which can be used to solve QUBO problems. A binomial trial was used to construct the neighborhood structure, and this was used with the aim of reducing computation time. The B-VNS and VNS algorithms were tested on standard QUBO problems from Glover and Beasley, on standard max-cut problems from Helmberg–Rendl, and on those proposed by Burer, Monteiro, and Zhang. Finally, Mann–Whitney tests were conducted using α = 0.05 , to statistically compare the performance of the two algorithms. It was shown that the B-VNS and VNS algorithms are able to provide good solutions, but the B-VNS algorithm runs substantially faster. Furthermore, the B-VNS algorithm performed the best in all of the max-cut problems, regardless of problem size, and it performed the best in QUBO problems, with sizes less than 500. The results suggest that the use of binomial distribution, to construct the neighborhood structure, has the potential for further development. [ABSTRACT FROM AUTHOR]

Motivated by conjectures of Karloff, and Van Dam and Sotirov on the smallest eigenvalues of Johnson and Hamming graphs, Brouwer, Cioabă, Ihringer and McGinnis obtained some new results involving the eigenvalues of various graphs coming from association schemes and posed some conjectures related to the eigenvalues of Grassmann graphs, Bilinear forms graphs and Hermitian forms graphs. In this paper, we prove some of their conjectures. [ABSTRACT FROM AUTHOR]

Local search is a fundamental tool in the development of heuristic algorithms. A neighborhood operator takes a current solution and returns a set of similar solutions, denoted as neighbors. In best improvement local search, the best of the neighboring solutions replaces the current solution in each iteration. On the other hand, in first improvement local search, the neighborhood is only explored until any improving solution is found, which then replaces the current solution. In this work we propose a new strategy for local search that attempts to avoid low-quality local optima by selecting in each iteration the improving neighbor that has the fewest possible attributes in common with local optima. To this end, it uses inequalities previously used as optimality cuts in the context of integer linear programming. The novel method, referred to as delayed improvement local search, is implemented and evaluated using the travelling salesman problem with the 2-opt neighborhood and the max-cut problem with the 1-flip neighborhood as test cases. Computational results show that the new strategy, while slower, obtains better local optima compared to the traditional local search strategies. The comparison is favourable to the new strategy in experiments with fixed computation time or with a fixed target. [ABSTRACT FROM AUTHOR]

Artificial bee colony (ABC) algorithm is a widely utilized swarm intelligence (SI) algorithm for addressing continuous optimization problems. However, most binary variants of ABC (BABC) algorithms may suffer from issues such as invalid searches and high complexity when applied to binary problems. To address these challenges, we first establish a set of criteria for developing a BABC algorithm. Following these criteria, we propose a novel BABC algorithm, denoted as oBABC, which not only adheres to the defined criteria but also successfully inherits the advantages of original ABC algorithm. To evaluate the performance of oBABC and verify its effectiveness, experiments are conducted on two typical binary problems: uncapacitated facility location problem (UFLP) and maximum cut problem (Max-Cut). The experimental results reveal the following findings: 1) The validity of the criteria and the accuracy of the theoretical analysis are confirmed. oBABC exhibits high search efficiency with an invalid learning rate (ILR) of 0 %, while the ILR s of other BABC algorithms almost exceeds 20 %. 2) In terms of search efficiency and capability, oBABC exhibits a significant improvement in search efficiency and consistently ranks at the top in terms of optimization capability. These results suggest that oBABC may be a highly efficient and effective tool for solving binary problems. [ABSTRACT FROM AUTHOR]

We present OIM (Oscillator Ising Machines), a new way to make Ising machines using networks of coupled self-sustaining nonlinear oscillators. OIM is theoretically rooted in a novel result that establishes that the phase dynamics of coupled oscillator systems, under the influence of subharmonic injection locking, are governed by a Lyapunov function that is closely related to the Ising Hamiltonian of the coupling graph. As a result, the dynamics of such oscillator networks evolve naturally to local minima of the Lyapunov function. Two simple additional steps (i.e., turning subharmonic locking on and off smoothly, and adding noise) enable the network to find excellent solutions of Ising problems. We demonstrate our method on Ising versions of the MAX-CUT and graph colouring problems, showing that it improves on previously published results on several problems in the G benchmark set. Using synthetic problems with known global minima, we also present initial scaling results. Our scheme, which is amenable to realisation using many kinds of oscillators from different physical domains, is particularly well suited for CMOS IC implementation, offering significant practical advantages over previous techniques for making Ising machines. We report working hardware prototypes using CMOS electronic oscillators. [ABSTRACT FROM AUTHOR]

Finding locally optimal solutions for max-cut and max-k-cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP has been studied in the smoothed complexity framework. Etscheid and Röglin (ACM Transactions on Algorithms, 2017) showed that the smoothed complexity of FLIP for maxcut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei (STOC, 2017) showed that the smoothed complexity of FLIP for max-cut in complete graphs is O(ϕ5n15.1), where ϕ is an upper bound on the random edge-weight density and n is the number of vertices in the input graph. While Angel, Bubeck, Peres, andWei's result showed the first polynomial smoothed complexity, they also conjectured that their run-time bound is far from optimal. In this work, we make substantial progress toward improving the run-time bound. We prove that the smoothed complexity of FLIP for max-cut in complete graphs is O(ϕn7.83). Our results are based on a carefully chosen matrix whose rank captures the run-time of the method along with improved rank bounds for this matrix and an improved union bound based on this matrix. In addition, our techniques provide a general framework for analyzing FLIP in the smoothed framework. We illustrate this general framework by showing that the smoothed complexity of FLIP for max-3-cut in complete graphs is polynomial and for max-k-cut in arbitrary graphs is quasi-polynomial. We believe that our techniques should also be of interest toward showing smoothed polynomial complexity of FLIP for max-k-cut in complete graphs for larger constants k. [ABSTRACT FROM AUTHOR]

We consider the Max-Cut problem on an undirected graph G = (V , E) with | V | = n nodes and | E | = m edges. We investigate a linear size MIP formulation, referred to as (MIP-MaxCut), which can easily be derived via a standard linearization technique. However, the efficiency of the Branch-and-Bound procedure applied to this formulation does not seem to have been investigated so far in the literature. Branch-and-bound based approaches for Max-Cut usually use the semi-metric polytope which has either an exponential size formulation consisting of the cycle inequalities or a compact size formulation consisting of O(mn) triangle inequalities (Barahona and Mahjoub in Math Prog 36:157–173, 1986; Nguyen and Minoux in Networks 69(1):142–150, 2017). However, optimizing over the semi-metric polytope can be computationally demanding due to the slow convergence of cutting-plane algorithms and the high degeneracy of formulations based on the triangle inequalities. In this paper, we exhibit new structural properties of (MIP-MaxCut) that link the binary variables with the cycle inequalities. In particular, we show that fixing a binary variable at 0 or 1 in (MIP-MaxCut) can result in imposing the integrity of several original variables and the satisfaction of a possibly exponential number of cycle inequalities in the semi-metric formulation. Numerical results show that for sparse instances of Max-Cut, our approach exploiting this capability outperforms the branch-and-cut algorithms based on semi-metric polytope when implemented on the same framework; and even without any extra sophistication, the approach is capable of solving hard instances of Max-Cut within acceptable CPU times. [ABSTRACT FROM AUTHOR]

With the slowdown of Moore’s law, many emerging electronic devices and computing architectures have been proposed to sustain the performance advancement of computing. Among them, the Ising machine is a non-von-Neumann solver that has received wide attention in recent years. It is capable of solving intractable combinatorial optimization (CO) problems, which are difficult to be solve using conventional digital computers. In fact, many CO problems can be mapped to finding the corresponding ground states of Ising model. At present, Ising machine prototypes based on different physical principles, such as emerging memristive oscillators, have been demonstrated, among which the Ising Hamiltonian solver based on the coupled oscillator network simultaneously holds the advantages of room-temperature operation, compact footprint, low power consumption, and fast speed to solution. This paper comprehensively surveys the recent developments in this important field, including the types of oscillators, the implementation principle of the Ising model, and the solver’s performance. Finally, methods to further improve the performance have also been suggested.

The quadratic unconstrained binary optimization (QUBO) problem is categorized as an NP-hard combinatorial optimization problem. The variable neighborhood search (VNS) algorithm is one of the leading algorithms used to solve QUBO problems. As neighborhood structure change is the central concept in the VNS algorithm, the design of the neighborhood structure is crucial. This paper presents a modified VNS algorithm called “B-VNS”, which can be used to solve QUBO problems. A binomial trial was used to construct the neighborhood structure, and this was used with the aim of reducing computation time. The B-VNS and VNS algorithms were tested on standard QUBO problems from Glover and Beasley, on standard max-cut problems from Helmberg–Rendl, and on those proposed by Burer, Monteiro, and Zhang. Finally, Mann–Whitney tests were conducted using α=0.05, to statistically compare the performance of the two algorithms. It was shown that the B-VNS and VNS algorithms are able to provide good solutions, but the B-VNS algorithm runs substantially faster. Furthermore, the B-VNS algorithm performed the best in all of the max-cut problems, regardless of problem size, and it performed the best in QUBO problems, with sizes less than 500. The results suggest that the use of binomial distribution, to construct the neighborhood structure, has the potential for further development.

We consider an extended version of the classical Max- k -Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The main focus of this paper is an extensive numerical study in which we analyze the impact of the different techniques for various test sets. It turns out that the techniques from the existing literature are not sufficient to solve an adequate fraction of the test sets. However, our novel techniques significantly outperform the existing ones both in terms of running times and the overall number of instances that can be solved. [ABSTRACT FROM AUTHOR]

The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope with these difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into several independent subproblems. This opens the way to use the bundle method from non-smooth optimization to minimize the dual function. Finally computational experiments on the Max-Cut, stable set and coloring problem show the excellent quality of the bounds obtained with this approach. [ABSTRACT FROM AUTHOR]

Every connected graph on n vertices has a cut of size at least n − 1. We call this bound the spanning tree bound. In the Max-Cut Above Spanning Tree (Max-Cut-AST) problem, we are given a connected n-vertex graph G and a non-negative integer k, and the task is to decide whether G has a cut of size at least n − 1 + k. We show that Max-Cut-AST admits an algorithm that runs in time O (8 k n O (1)) , and hence it is fixed parameter tractable with respect to k. Furthermore, we show that Max-Cut-AST has a polynomial kernel of size O (k 5) . [ABSTRACT FROM AUTHOR]

The max-cut problem is a fundamental and much-studied NP -hard combinatorial optimisation problem, with a wide range of applications. Several authors have shown that the max-cut problem can be solved in polynomial time if the underlying graph is free of certain minors. We give a polyhedral counterpart of these results. In particular, we show that, if a family of valid inequalities for the cut polytope satisfies certain conditions, then there is an associated minor-closed family of graphs on which the max-cut problem can be solved efficiently. [ABSTRACT FROM AUTHOR]

MAX-CUT is one of the well-studied NP-hard combinatorial optimization problems. It can be formulated as an Integer Quadratic Programming problem and admits a simple relaxation obtained by replacing the integer “spin” variables xi by unitary vectors v→i. The Goemans–Williamson rounding algorithm assigns the solution vectors of the relaxed quadratic program to a corresponding integer spin depending on the sign of the scalar product v→i·r→ with a random vector r→. Here, we investigate whether better graph cuts can be obtained by instead using a more sophisticated clustering algorithm. We answer this question affirmatively. Different initializations of k-means and k-medoids clustering produce better cuts for the graph instances of the most well known benchmark for MAX-CUT. In particular, we found a strong correlation of cluster quality and cut weights during the evolution of the clustering algorithms. Finally, since in general the maximal cut weight of a graph is not known beforehand, we derived instance-specific lower bounds for the approximation ratio, which give information of how close a solution is to the global optima for a particular instance. For the graphs in our benchmark, the instance specific lower bounds significantly exceed the Goemans–Williamson guarantee.

MAX-CUT is a well-known classical NP-hard problem. This problem asks whether the vertex-set of a given graph G=(V,E) can be partitioned into two disjoint subsets, A and B, such that there exist at least p edges with one endpoint in A and the other endpoint in B. It is well known that if p≤|E|/2, the answer is necessarily positive. A widely-studied variant of particular interest to parameterized complexity, called (k,n-k)-MAX-CUT, restricts the size of the subset A to be exactly k. For the (k,n-k)-MAX-CUT problem, we obtain an O∗(2p)-time algorithm, improving upon the previous best O∗(4p+o(p))-time algorithm, as well as the first polynomial kernel. Our algorithm relies on a delicate combination of methods and notions, including independent sets, depth-search trees, bounded search trees, dynamic programming and treewidth, while our kernel relies on examination of the closed neighborhood of the neighborhood of a certain independent set of the graph G. [ABSTRACT FROM AUTHOR]

Abstract We prove a conjecture by Van Dam & Sotirov on the smallest eigenvalue of (distance- j) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance- j) Johnson graphs. More generally, we study the smallest eigenvalue and the second largest eigenvalue in absolute value of the graphs of the relations of classical P - and Q -polynomial association schemes. [ABSTRACT FROM AUTHOR]