Search

We study the sparsest cut problem when the “capacity-demand” graph is planar, and give a combinatorial polynomial algorithm. In this type of graphs there is an edge for each positive capacity and also an edge for each positive demand. We extend this result to graphs with no K5 minor. We also show how to find a maximum concurrent flow in these two cases. We also prove that the sparsest cut problem is NP-hard if we only impose that the “capacity-demand” graph has no K6 minor. We use ideas that had been developed for the max-cut problem, and show how to exploit the connections among these problems. [ABSTRACT FROM AUTHOR]

The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results:We show that an algorithm by Crowston et al. (Algorithmica 72(3):734-757, 2015) for (SIGNED) MAX-CUT ABOVE EDWARDS−ERDőS BOUND can be implemented so as to run in linear time8k·O(m); this significantly improves the previous analysis with run time 8k·O(n4).We give an asymptotically optimal kernel for (SIGNED) MAX-CUT ABOVE EDWARDS−ERDőS BOUND with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. (Theor Comput Sci 513:53-64, 2013).We improve all known kernels for parameterizations above strongly λ-extendible properties (a generalization of the MAX-CUT results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics, Guwahati, 2013) from O(k3) vertices to O(k) vertices.Therefore, MAX ACYCLIC SUBDIGRAPH parameterized above Poljak-Turzík bound admits a kernel with O(k) vertices and can be solved in 2O(k)·nO(1) time; this answers an open question by Crowston et al. (Proceedings of FSTTCS 2012, Leibniz international proceedings in informatics, Hyderabad, 2012). All presented kernels can be computed in time O(km). [ABSTRACT FROM AUTHOR]

Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice. In a systematic review of Max-Cut and quadratic unconstrained binary optimization (QUBO) heuristics papers,we found only 4% publish source code, only 14% compare heuristics with identical termination criteria, and most experiments are performed with an artificial, homogeneous set of problem instances. To address these limitations, we implement and release as open-source a code-base of 10 Max-Cut and 27 QUBO heuristics. We perform heuristic evaluation using cloud computing on a library of 3,296 instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners. [ABSTRACT FROM AUTHOR]

Abstract: We use a theorem by Ding, Lubetzky, and Peres describing the structure of the giant component of random graphs in the strictly supercritical regime, in order to determine the typical size of MAXCUT of G ∼ G ( n , 1 + ɛ n ) in terms of ɛ. We then apply this result to prove the following conjecture by Frieze and Pegden. For every ɛ > 0, there exists ℓ ɛ such that w.h.p. G ∼ G ( n , 1 + ɛ n ) is not homomorphic to the cycle on 2 ℓ ɛ + 1 vertices. We also consider the coloring properties of biased random tournaments. A p‐random tournament on n vertices is obtained from the transitive tournament by reversing each edge independently with probability p. We show that for p = Θ ( 1 n ) the chromatic number of a p‐random tournament behaves similarly to that of a random graph with the same edge probability. To treat the case p = 1 + ɛ n we use the aforementioned result on MAXCUT and show that in fact w.h.p. one needs to reverse Θ ( ɛ 3 ) n edges to make it 2‐colorable. [ABSTRACT FROM AUTHOR]

Let $$r\ge 3$$ and $$k\ge 2$$ be fixed integers, and let H be an r-uniform hypergraph with n vertices and m edges. In 1997, Bollobás and Scott conjectured that H has a vertex-partition into k sets with at most $$m/k^r+o(m)$$ edges in each set. So far, this conjecture was confirmed when $$r=3$$ or $$m=\Omega (n^{r-1+o(1)})$$ . In this paper, we show that it holds for $$m=\Omega (n^{r-3+\epsilon })$$ for any $$\epsilon >0$$ . [ABSTRACT FROM AUTHOR]

We show that any 3-connected cubic plane graph on n vertices, with all faces of size at most 6, can be made bipartite by deleting no more than ( p + 3 t ) n / 5 edges, where p and t are the numbers of pentagonal and triangular faces, respectively. In particular, any such graph can be made bipartite by deleting at most 12 n / 5 edges. This bound is tight, and we characterise the extremal graphs. We deduce tight lower bounds on the size of a maximum cut and a maximum independent set for this class of graphs. This extends and sharpens the results of Faria, Klein and Stehlík [SIAM J. Discrete Math. 26 (2012) 1458–1469]. [ABSTRACT FROM AUTHOR]

For positive integers [ABSTRACT FROM AUTHOR]

Let G = ( V,E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1− p, let m ( G) be the minimum of qe( V ) + pe( V ) over partitions V = V ∪ V , where e( V ) denotes the number of edges spanned by V . We show that if m ( G) = pqm− δ, then there exists a bipartition V , V of G such that $$e{V_1} \leqslant {p^2}m - \delta + p\sqrt {m/2} + o\left( {\sqrt m } \right)$$ and $$e{V_2} \leqslant {q^2}m - \delta + q\sqrt {m/2} + o\left( {\sqrt m } \right)$$ for δ = o(m). This is sharp for complete graphs up to the error term $$o\left( {\sqrt m } \right)$$ . For an integer k ≥ 2, let f ( G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if f ( G) = (1 − 1/ k)m + α, then G admits a k-partition such that each vertex class spans at most m/k − Ω( m/k ) edges for α = Ω( m/k ). Both of the above improve the results of Bollobás and Scott. [ABSTRACT FROM AUTHOR]

We adapt a result by Masuda et al. [IEEE Transactions on Computers 39 (1990), 124–127] on FIXED LINEAR CROSSING NUMBER to show that SIMPLE MAX-CUT is NP-hard on comparability graphs. [ABSTRACT FROM AUTHOR]

In microarray-based gene expression analysis, thousands of genes are involved to monitor their expression levels under a particular condition. In fact, however, only few of them are highly expressed, which has been proven by Golub et al. How to identify these discriminative genes effectively is a significant challenge to risk assessment, diagnosis, prognostication in growing cancer incidence and mortality. In this paper, we present a global feature selection method based on semidefinite programming model which is relaxed from the quadratic programming model with maximizing feature relevance and minimizing feature redundancy. The main advantage of relaxation is that the matrix in mathematical model only requires symmetric matrix rather than positive (or semi) definite matrix. In semidefinite programming model, each feature has one constraint condition to restrict the objective function of feature selection problem. Herein, another trick in this paper is that we utilize Lagrange multiplier as proxy measurement to identify the discriminative features instead of solving a feasible solution for the original max-cut problem. The proposed method is compared with several popular feature selection methods on seven microarray data sets. The results demonstrate that our method outperforms the others on most data sets, especially for the two hard feature selection data sets, Beast(Wang) and Medulloblastoma. [ABSTRACT FROM AUTHOR]

A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new 'nonmonotone' strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), and the quadratic assignment problem (QAP). [ABSTRACT FROM AUTHOR]

In this paper, an augmented Lagrangian method is proposed for binary quadratic programming (BQP) problems based on a class of continuous functions. The binary constraints are converted into a class of continuous functions. The approach reformulates the BQP problem as an equivalent augmented Lagrangian function, and then seeks its minimizer via an augmented Lagrangian method, in which the subproblem is solved by Barzilai-Borwein type method. Numerical results are reported for max-cut problem. The results indicate that the augmented Lagrangian approach is promising for large scale binary quadratic programming by the quality of the near optimal values and the low computational time. [ABSTRACT FROM AUTHOR]

Max-cut is one of the most classic NP-hard combinatorial optimization problems. The symmetry nature of it leads to special difficulty in extracting meaningful configuration information for learning; none of the state-of-the-art algorithms has employed any learning operators. This paper proposes an original learning method for max-cut, namely post-flip edge-state learning (PF-ESL). Different from previous algorithms, PF-ESL regards edge-states (cut or not cut) rather than vertex-positions as the critical information of a configuration, and extracts their statistics over a population for learning. It is based on following observations. 1) Edges are the only factors considered by the objective function. 2) Edge-states keep invariant when rotating a local configuration to its symmetry position, but vertex-positions do not. These suggest that edge-states contain more meaningful information about a configuration than vertex-positions do. It is impossible to set the state of an edge without influencing some other edges' states due to their dependencies. Therefore, instead of setting edge-states directly, PF-ESL samples the flips on vertices. Flips on vertices are sampled according to their capacities in increasing the similarity on edge-states between the given solution and a population. PF-ESL is employed in an EDA (Estimation of Distribution Algorithm) perturbation operator and a path-relinking operator. Experimental results show that our algorithm is competitive, and show that edge-state learning is value-added for both the two operators. The main contributions of this paper are as follows. Firstly, previous state-of-the-art evolutionary algorithms for max-cut focus on vertex positions in their evolutionary operation, this paper proposes a new and more reasonable perspective suggesting that edge-states are the critical information of divided graphs rather than vertex positions, and introduces a novel method to measure and utilize their similarities based on it. Such a perspective is fundamental to learning based algorithms design for max-cut and other graph partitioning problems, and can shed lights on future researches. Furthermore, since max-cut is one of the most classic and fundamental NP hard problems, many real-world problems involve dividing graph data into different parts to optimize certain functions, this new perspective may inspire related or similar problems. Secondly, besides the original edge-states based perspective, and the post-flip edge-states learning (PFESL) operator based on it, our memetic algorithm also incorporates a novel evolutionary framework which alternates between EDA based Iterated Tabu search (ITS) and path relinking based genetic algorithm. Finally, the proposed algorithm provides competitive results on two mostly used benchmark sets and improves the best-known results of 6 most challenging instances. • An original edge-state perspective for design learning operators for max-cut. • A novel learning operator to learn edge states. • A new evolutionary framework for max-cut. • It provides competitive results on two mostly used benchmark sets. [ABSTRACT FROM AUTHOR]

This paper presents a tabu search based hybrid evolutionary algorithm (TSHEA) for solving the max-cut problem. The proposed algorithm integrates a distance-and-quality based solution combination operator and a tabu search procedure based on neighborhood combination of one-flip and constrained exchange moves. Comparisons with leading reference algorithms from the literature disclose that the proposed algorithm discovers new best solutions for 15 out of 91 instances, while matching the best known solutions on all but 4 instances. Analysis indicates that the neighborhood combination and the solution combination operator play key roles to the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We prove that under the Gaussian measure, half-spaces are uniquely the most noise stable sets. We also prove a quantitative version of uniqueness, showing that a set which is almost optimally noise stable must be close to a half-space. This extends a theorem of Borell, who proved the same result but without uniqueness, and it also answers a question of Ledoux, who asked whether it was possible to prove Borell's theorem using a direct semigroup argument. Our quantitative uniqueness result has various applications in diverse fields. [ABSTRACT FROM AUTHOR]

Trevisan [SIAM J. Comput., 41 (2012), pp. 1769-1786] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger than 1/2 that is not based on semidefinite programming. Trevisan showed that its approximation ratio is of at least 0.531. In this paper we improve this bound up to 0.614247. We also define and extend this result for the more general maximum colored cut problem. [ABSTRACT FROM AUTHOR]

Downsampling of signals living on a general weighted graph is not as trivial as of regular signals where we can simply keep every other samples. In this paper we propose a simple, yet effective downsampling scheme in which the underlying graph is approximated by a maximum spanning tree (MST) that naturally defines a graph multiresolution. This MST-based method significantly outperforms the two previous downsampling schemes, coloring-based and SVD-based, on both random and specific graphs in terms of computations and partition efficiency quantified by the graph cuts. The benefit of using MST-based downsampling for recently developed critical-sampling graph wavelet transforms in compression of graph signals is demonstrated. [ABSTRACT FROM PUBLISHER]

Abstract: We define strong λ-extendibility as a variant of the notion of λ-extendible properties of graphs (Poljak and Turzík, Discrete Mathematics, 1986). We show that the parameterized APT(Π) problem — given a connected graph G on n vertices and m edges and an integer parameter k, does there exist a spanning subgraph H of G such that and H has at least edges — is fixed-parameter tractable (FPT) for all , for all strongly λ-extendible graph properties Π for which the APT(Π) problem is FPT on graphs which are vertices away from being a graph in which each block is a clique. Our results hold for properties of oriented graphs and graphs with edge labels, generalize the recent result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards–Erdős bound, and yield FPT algorithms for several graph problems parameterized above lower bounds. [Copyright &y& Elsevier]

We obtain asymptotically tight algorithmic bounds for Max-Cut and Edge Dominating Set problems on graphs of bounded clique-width. We show that on an n-vertex graph of clique-width t both problems (1) cannot be solved in time f(t)no(t) for any function f of t unless exponential time hypothesis fails, and (2) can be solved in time nO(t). [ABSTRACT FROM AUTHOR]

Recently, a resolution-based transformation has been introduced for the usual Max-SAT encoding of several graph problems such as the Minimum Vertex Covering, Maximum Clique and Combinatorial Auctions which consists in iteratively applying specific inference rules to transform and simplify the original formula. Such transformation was shown suitable to improve the performance of local and systematic search procedures. In this paper, we present several refinements for such transformation. In particular, we introduce a more suitable transformation for the Minimum Vertex Covering problem, specially for its weighted version, and we extend its use for the Maximum Cut problem. Empirical results indicate that systematic Max-SAT solvers improve substantially their performance. [ABSTRACT FROM AUTHOR]

Abstract: Given an undirected graph where each edge of E is weighted with an integer number, the maximum cut problem (Max-Cut) is to partition the vertices of V into two disjoint subsets so as to maximize the total weight of the edges between the two subsets. As one of Karp''s 21 NP-complete problems, Max-Cut has attracted considerable attention over the last decades. In this paper, we present Breakout Local Search (BLS) for Max-Cut. BLS explores the search space by a joint use of local search and adaptive perturbation strategies. The proposed algorithm shows excellent performance on the set of well-known maximum cut benchmark instances in terms of both solution quality and computational time. Out of the 71 benchmark instances, BLS is capable of finding new improved results in 34 cases and attaining the previous best-known result for 35 instances, within computing times ranging from less than 1s to 5.6h for the largest instance with 20,000 vertices. [Copyright &y& Elsevier]

We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained $$\{-1,1\}$$ quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the non-convex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an efficient and globally convergent algorithm, called SpeeDP, for finding critical points of the LRSDP problem. We provide evidence of the effectiveness of SpeeDP by comparing it with other existing codes on an extended set of instances of the Max-Cut problem. We further include SpeeDP within a simply modified version of the Goemans-Williamson algorithm and we show that the corresponding heuristic SpeeDP-MC can generate high-quality cuts for very large, sparse graphs of size up to a million nodes in a few hours. [ABSTRACT FROM AUTHOR]

A fullerene graph is a cubic bridgeless plane graph with all faces of size 5 and 6. We show that every fullerene graph on n vertices can be made bipartite by deleting at most √12n/5 edges and has an independent set with at least n/2-√3n/5 vertices. Both bounds are sharp, and we characterize the extremal graphs. This proves conjectures of Došlić and Vukičević and of Daugherty. We deduce two further conjectures on the independence number of fullerene graphs, as well as a new upper bound on the smallest eigenvalue of a fullerene graph. [ABSTRACT FROM AUTHOR]

Abstract: We study max-cut in classes of graphs defined by forbidding finitely many graphs as subgraphs, or a single graph as an induced subgraph or a minor. For the first two containment relations, we prove dichotomy theorems. For the minor order, we show how to solve max-cut in polynomial time for the class obtained by forbidding a graph with a single crossing (this generalizes a known result for -minor-free graphs) and identify an open problem which is the missing case for a dichotomy theorem. [Copyright &y& Elsevier]

We construct a small set of explicit linear transformations mapping ℝn to ℝt, where t = O(log(γ-1)ε-2), such that the L2 norm of any vector in ℝn is distorted by at most 1 ± ε in at least a fraction of 1-γ of the transformations in the set. Albeit the tradeoff between the size of the set and the success probability is suboptimal compared with probabilistic arguments, we nevertheless are able to apply our construction to a number of problems. In particular, we use it to construct an ε-sample (or pseudorandom generator) for linear threshold functions on 픔n-1 for ε = o(1). We also use it to construct an ε-sample for spherical digons in 픔n-1 for ε = o(1). This construction leads to an efficient oblivious derandomization of the Goemans-Williamson Max-Cut algorithm and similar approximation algorithms (i.e., we construct a small set of hyperplanes such that for any instance we can choose one of them to generate a good solution). Our technique for constructing an ε-sample for linear threshold functions on the sphere is considerably different than previous techniques that rely on k-wise independent sample spaces. [ABSTRACT FROM AUTHOR]

Max-Cut is a famous NP-hard problem in combinatorial optimization. In this article, we propose a Lagrangian smoothing algorithm for Max-Cut, where the continuation subproblems are solved by the truncated Frank-Wolfe algorithm. We establish practical stopping criteria and prove that our algorithm finitely terminates at a KKT point, the distance between which and the neighbour optimal solution is also estimated. Additionally, we obtain a new sufficient optimality condition for Max-Cut. Numerical results indicate that our approach outperforms the existing smoothing algorithm in less time. [ABSTRACT FROM AUTHOR]

Abstract: We describe an improved technique for handling large numbers of cutting planes when using an interior-point method for the solution of linear or semidefinite relaxations in binary quadratic optimization. The approach does not require solving successive relaxations to optimality but chooses cuts at intermediate iterates based on indicators of inequality violation and feasibility of their slacks, which are initialized using a recently proposed warmstart technique without any additional correction steps. Computational tests on instances of max-cut suggest that this new scheme is superior to solving only the final relaxation with all relevant cuts known in advance. [ABSTRACT FROM AUTHOR]

Abstract: The maximum cut (Max-Cut) problem has extensive applications in various real-world fields, such as network design and statistical physics. In this paper, a more practical version, the Max-Cut problem with fuzzy coefficients, is discussed. Specifically, based on credibility theory, the Max-Cut problem with fuzzy coefficients is formulated as an expected value model, a chance-constrained programming model and a dependent-chance programming model respectively according to different decision criteria. When these fuzzy coefficients are represented by special fuzzy variables like triangular fuzzy numbers and trapezoidal fuzzy numbers, the crisp equivalents of the fuzzy Max-Cut problem can be obtained. Finally, a genetic algorithm combined with fuzzy simulation techniques is designed for the general fuzzy Max-Cut problem under these models and numerical experiment confirms the effectiveness of the designed genetic algorithm. [Copyright &y& Elsevier]

We evaluate the possible benefit from improving the workload distribution in a directed acyclic graph (DAG) (e.g. a project network), by determining a lower bound for the project completion time. It is shown that a lower bound can be obtained by equally distributing the workload over the max-cut in the graph which separates the nodes 1 and n. It is also shown that for a complete n-node DAG, practitioners can quickly compute a lower bound for the project completion time. The max-cut can be found by any linear programming algorithm or by reducing the problem to the problem of finding a maximum matching in a bipartite graph. Our results can help planners and project managers to characterize the "ideal case" in which the optimal workload distribution among the arc networks minimizes the project completion time. That can be done for a non-complete DAG as well as for a complete one. A lower bound can then be used to evaluate the maximum potential for reducing the project completion time in real-life cases. [ABSTRACT FROM AUTHOR]

Abstract: We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on partition problems in hypergraphs which are computationally difficult to solve (NP-hard or NP-complete). Therefore it is very important to obtain nontrivial bounds. More precisely, the following parameters are bounded in the paper: bipartition width, averaged minimal cut, isoperimetric number, max-cut, independence number and domination number. [Copyright &y& Elsevier]

The Quantum Approximate Optimization Algorithm (QAOA) was proposed as a way of finding good, approximate solutions to hard combinatorial optimization problems. QAOA uses a hybrid approach. A parametrized quantum state is repeatedly prepared and measured on a quantum computer to estimate its average energy. Then, a classical optimizer, running in a classical computer, uses such information to decide on the new parameters that are then provided to the quantum computer. This process is iterated until some convergence criteria are met. Theoretically, almost all classical minimizers can be used in the hybrid scheme. However, their behaviour can vary greatly in both the quality of the final solution and the time they take to find it. In this work, we study the performance of twelve different classical optimizers when used with QAOA to solve the maximum cut problem in graphs. We conduct a thorough set of tests on a quantum simulator both, with and without noise, and present results that show that some optimizers can be hundreds of times more efficient than others in some cases. [ABSTRACT FROM AUTHOR]

Abstract: The following problem has been presented in [T. Epping, W. Hochstättler, P. Oertel, Complexity results on a paint shop problem, Discrete Applied Mathematics 136 (2004) 217–226] by Epping, Hochstättler and Oertel: cars have to be painted in two colors in a sequence where each car occurs twice; assign the two colors to the two occurrences of each car so as to minimize the number of color changes. More generally, the “paint shop scheduling problem” is defined with an arbitrary multiset of colors given for each car, where this multiset has the same size as the number of occurrences of the car; the mentioned article states two conjectures about the general problem and proves its NP-hardness. In a subsequent paper in [P. Bonsma, Th. Epping, W. Hochstättler, Complexity results for restricted instances of a paint shop problem for words, Discrete Applied Mathematics 154 (2006) 1335–1343], Bonsma, Epping and Hochstättler proved its APX-hardness and noticed the applicability of some classical results in special cases. We first identify the problem concerning two colors as a minimum odd circuit cover problem in particular graphs, exactly situating the problem. A resulting two-way reduction to a special minimum uncut problem leads to polynomial algorithms for subproblems, to observing APX-hardness through MAX CUT in 3-regular graphs, and to a solution with at most 3/4th of all possible remaining color changes (when all obliged color changes have been made). For the general problem concerning an arbitrary number of colors, we realize that the two aforementioned conjectures are corollaries of the celebrated “necklace splitting” theorem of Alon, Goldberg and West. [Copyright &y& Elsevier]