Search

The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80's, being one of the problems proposed by Johnson in his Ongoing Guide to NP-completeness, and has been settled as NP-complete only recently by Adhikary, Bose, Mukherjee, and Roy. On the other hand, many flawed proofs of polynomiality for MaxCut on the more restrictive class of unit/proper interval graphs (or graphs with interval count 1) have been presented along the years, and the classification of the problem is still unknown. In this paper, we present the first NP-completeness proof for MaxCut when restricted to interval graphs with bounded interval count, namely graphs with interval count 4. [ABSTRACT FROM AUTHOR]

Given a graph G$$ G $$ of degree k$$ k $$ over n$$ n $$ vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth 2L$$ 2L $$, we develop a local message passing algorithm whose complexity is O(nkL)$$ O(nkL) $$, and that achieves near optimal cut values among all L$$ L $$‐local algorithms. Focusing on max‐cut, the algorithm constructs a cut of value nk/4+nP⋆k/4+err(n,k,L)$$ nk/4+n{P}_{\star}\sqrt{k/4}+\mathsf{err}\left(n,k,L\right) $$, where P⋆≈0.763166$$ {P}_{\star}\approx 0.763166 $$ is the value of the Parisi formula from spin glass theory, and err(n,k,L)=on(n)+nok(k)+nkoL(1)$$ \mathsf{err}\left(n,k,L\right)={o}_n(n)+n{o}_k\left(\sqrt{k}\right)+n\sqrt{k}{o}_L(1) $$ (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, that is, graphs whose girth becomes 2L$$ 2L $$ after removing a small fraction of vertices. Earlier work established that, for random k$$ k $$‐regular graphs, the typical max‐cut value is nk/4+nP⋆k/4+on(n)+nok(k)$$ nk/4+n{P}_{\star}\sqrt{k/4}+{o}_n(n)+n{o}_k\left(\sqrt{k}\right) $$. Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max‐cut, and nearly maximum min‐bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near‐Ramanujan property of random regular graphs. [ABSTRACT FROM AUTHOR]

We resolve the longstanding open problem concerning the computational complexity of MaxCut on interval graphs by showing that it is NP-complete. [ABSTRACT FROM AUTHOR]

Let V be a set of n vertices, M a set of m labels, and let R be an m × n matrix ofs independent Bernoulli random variables with probability of success p; columns of R are incidence vectors of label sets assigned to vertices. A random instance G (V , E , R T R) of the weighted random intersection graph model is constructed by drawing an edge with weight equal to the number of common labels (namely [ R T R ] v , u ) between any two vertices u, v for which this weight is strictly larger than 0. In this paper we study the average case analysis of Weighted Max Cut, assuming the input is a weighted random intersection graph, i.e. given G (V , E , R T R) we wish to find a partition of V into two sets so that the total weight of the edges having exactly one endpoint in each set is maximized. In particular, we initially prove that the weight of a maximum cut of G (V , E , R T R) is concentrated around its expected value, and then show that, when the number of labels is much smaller than the number of vertices (in particular, m = n α , α < 1 ), a random partition of the vertices achieves asymptotically optimal cut weight with high probability. Furthermore, in the case n = m and constant average degree (i.e. p = Θ (1) n ), we show that with high probability, a majority type randomized algorithm outputs a cut with weight that is larger than the weight of a random cut by a multiplicative constant strictly larger than 1. Then, we formally prove a connection between the computational problem of finding a (weighted) maximum cut in G (V , E , R T R) and the problem of finding a 2-coloring that achieves minimum discrepancy for a set system Σ with incidence matrix R (i.e. minimum imbalance over all sets in Σ ). We exploit this connection by proposing a (weak) bipartization algorithm for the case m = n , p = Θ (1) n that, when it terminates, its output can be used to find a 2-coloring with minimum discrepancy in a set system with incidence matrix R . In fact, with high probability, the latter 2-coloring corresponds to a bipartition with maximum cut-weight in G (V , E , R T R) . Finally, we prove that our (weak) bipartization algorithm terminates in polynomial time, with high probability, at least when p = c n , c < 1 . [ABSTRACT FROM AUTHOR]

The decision problem MaxC ut is known to be NP‐complete since the seventies, but only recently its restriction to interval graphs has been announced to be hard by Adhikary, Bose, Mukherjee, and Roy. Building on their proof, in this paper we prove that the M axC ut problem is NP‐complete on permutation graphs. This settles a long‐standing open problem that appeared in the 1985 column of the Ongoing Guide to NP‐completeness by David S. Johnson, and is the first NP‐hardness entry for permutation graphs in such column. [ABSTRACT FROM AUTHOR]

Quantum annealing is a specialized type of quantum computation that aims to use quantum fluctuations in order to obtain global minimum solutions of combinatorial optimization problems. Programmable D-Wave quantum annealers are available as cloud computing resources, which allow users low-level access to quantum annealing control features. In this article, we are interested in improving the quality of the solutions returned by a quantum annealer by encoding an initial state into the annealing process. We explore two D-Wave features that allow one to encode such an initial state: the reverse annealing (RA) and the h-gain (HG) features. RA aims to refine a known solution following an anneal path starting with a classical state representing a good solution, going backward to a point where a transverse field is present, and then finishing the annealing process with a forward anneal. The HG feature allows one to put a time-dependent weighting scheme on linear ($h$) biases of the Hamiltonian, and we demonstrate that this feature likewise can be used to bias the annealing to start from an initial state. We also consider a hybrid method consisting of a backward phase resembling RA and a forward phase using the HG initial state encoding. Importantly, we investigate the idea of iteratively applying RA and HG to a problem, with the goal of monotonically improving on an initial state that is not optimal. The HG encoding technique is evaluated on a variety of input problems including the edge-weighted maximum cut problem and the vertex-weighted maximum clique problem, demonstrating that the HG technique is a viable alternative to RA for some problems. We also investigate how the iterative procedures perform for both RA and HG initial state encodings on random whole-chip spin glasses with the native hardware connectivity of the D-Wave Chimera and Pegasus chips.

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]

Today's quantum computers are limited in their capabilities, e.g., the size of executable quantum circuits. The Quantum Approximate Optimization Algorithm (QAOA) addresses these limitations and is, therefore, a promising candidate for achieving a near-term quantum advantage. Warm-starting can further improve QAOA by utilizing classically pre-computed approximations to achieve better solutions at a small circuit depth. However, warm-starting requirements often depend on the quantum algorithm and problem at hand. Warm-started QAOA (WS-QAOA) requires developers to understand how to select approach-specific hyperparameter values that tune the embedding of classically pre-computed approximations. In this paper, we address the problem of hyperparameter selection in WS-QAOA for the maximum cut problem using the classical Goemans–Williamson algorithm for pre-computations. The contributions of this work are as follows: We implement and run a set of experiments to determine how different hyperparameter settings influence the solution quality. In particular, we (i) analyze how the regularization parameter that tunes the bias of the warm-started quantum algorithm towards the pre-computed solution can be selected and optimized, (ii) compare three distinct optimization strategies, and (iii) evaluate five objective functions for the classical optimization, two of which we introduce specifically for our scenario. The experimental results provide insights on efficient selection of the regularization parameter, optimization strategy, and objective function and, thus, support developers in setting up one of the central algorithms of contemporary and near-term quantum computing. [ABSTRACT FROM AUTHOR]

The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex relaxations for obtaining lower bounds on graph edit distance. These relaxations can be tailored to the structural properties of the particular graphs via convex graph invariants. Specific examples that we highlight in this paper include constraints on the graph spectrum as well as (tractable approximations of) the stability number and the maximum-cut values of graphs. We prove under suitable conditions that our relaxations are tight (i.e., exactly compute the graph edit distance) when one of the graphs consists of few eigenvalues. We also validate the utility of our framework on synthetic problems as well as real applications involving molecular structure comparison problems in chemistry. [ABSTRACT FROM AUTHOR]

Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an (α , β , δ) -clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most δ labels, a) every label consists of at most β sets of twin vertices, and b) all the labels together induce a graph with independence number at most α. We show that for every two constants α , δ > 0 the problem is FPT when parameterized by β plus the smallest width of an (α , β , δ) -clique-width decomposition. [ABSTRACT FROM AUTHOR]

In this paper, we discuss various connections between the smallest eigenvalue of the adjacency matrix of a graph and its structure. There are several techniques for obtaining upper bounds on the smallest eigenvalue, and some of them are based on Rayleigh quotients, Cauchy interlacing using induced subgraphs, and Haemers interlacing with vertex partitions and quotient matrices. In this paper, we are interested in obtaining lower bounds for the smallest eigenvalue. Motivated by results on line graphs and generalized line graphs, we show how graph decompositions can be used to obtain such lower bounds.

The exact solution of the NP-hard (nondeterministic polynomial-time hard) maximum cut problem is important in many applications across, for example, physics, chemistry, neuroscience, and circuit layout—which is also due to its equivalence to the unconstrained binary quadratic optimization problem. Leading solution methods are based on linear or semidefinite programming and require the separation of the so-called odd-cycle inequalities. In their groundbreaking research, F. Barahona and A. R. Mahjoub have given an informal description of a polynomial-time algorithm for this problem. As pointed out recently, however, additional effort is necessary to guarantee that the inequalities obtained correspond to facets of the cut polytope. In this paper, we shed more light on a so enhanced separation procedure and investigate experimentally how it performs in comparison with an ideal setting where one could even employ the sparsest, most violated, or geometrically most promising facet-defining odd-cycle inequalities. Summary of Contribution: This paper aims at a better capability to solve binary quadratic optimization or maximum cut problems and their various applications using integer programming techniques. To this end, the paper describes enhancements to a well-known algorithm for the central separation problem arising in this context; it is demonstrated experimentally that these enhancements are worthwhile from a computational point of view. The linear relaxations of the aforementioned problems are typically solved using fewer iterations and cutting planes than with a nonenhanced approach. It is also shown that the enhanced procedure is only slightly inferior to an ideal, enumerative, and, in practice, intractable global cutting-plane selection. [ABSTRACT FROM AUTHOR]

The cut-set ∂ (S) of a graph G = (V , E) is the set of edges that have one endpoint in S ⊂ V and the other endpoint in V \ S , and whenever G[S] is connected, the cut [ S , V \ S ] of G is called a connected cut. A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [ S , V \ S ] of G such that G[S] and G [ V \ S ] are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP . Also, we show that Largest Bond and Maximum Connected Cut are NP-hard even for planar bipartite graphs, whereas Maximum Cut is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that Largest Bond and Maximum Connected Cut are NP-hard on split graphs, and restricted to graphs of clique-width w they can not be solved in time f (w) n o (w) unless the Exponential Time Hypothesis fails, but they can be solved in time f (w) n O (w) . Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number. [ABSTRACT FROM AUTHOR]

For a graph G, let f(G) be the maximum number of edges in a cut of G. For a positive integer m and a set of graphs H , let f (m , H) be the minimum possible cardinality of f(G), as G ranges over all graphs on m edges which contain no graphs in H . Suppose that r ≥ 8 is an even integer and H = { C 5 , C 6 , ... , C r - 1 } . In this paper, we prove that f (m , H) ≥ m / 2 + c m r r + 1 for some real c > 0 , which improves a result of Alon et al. We also give a general lower bound on f (m , H) when H = { K s + K t ¯ } . This extends a result of Zeng and Hou. [ABSTRACT FROM AUTHOR]

The input of the Maximum Colored Cut problem consists of a graph G = (V , E) with an edge-coloring c : E → { 1 , 2 , 3 , ... , p } and a positive integer k , and the question is whether G has a nontrivial edge cut using at least k colors. The Colorful Cut problem has the same input but asks for a nontrivial edge cut using all p colors. Unlike what happens for the classical Maximum Cut problem, we prove that both problems are NP -complete even on complete, planar, or bounded treewidth graphs. Furthermore, we prove that Colorful Cut is NP -complete even when each color class induces a clique of size at most three, but is trivially solvable when each color induces an edge. On the positive side, we prove that Maximum Colored Cut is fixed-parameter tractable when parameterized by either k or p , by constructing a cubic kernel in both cases. [ABSTRACT FROM AUTHOR]

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MaxCut) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and achieves an approximation ratio of at least 1 2 in expectation. When the graph is d -regular and triangle-free, a slightly better approximation ratio can be achieved with a randomized algorithm running in a single round. Here, we investigate the round complexity of deterministic distributed algorithms for MaxCut in regular graphs. We first prove that if G is d -regular, with d even and fixed, no deterministic algorithm running in a constant number of rounds can achieve a constant approximation ratio. We then give a simple one-round deterministic algorithm achieving an approximation ratio of 1 d for d -regular graphs when d is odd. We show that this is best possible in several ways, and in particular no deterministic algorithm with approximation ratio 1 d + ϵ (with ϵ > 0) can run in a constant number of rounds. We also prove results of a similar flavor for the MaxDiCut problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part to the right part of the cut. [ABSTRACT FROM AUTHOR]

• Models the scheduling problem as an optimization problem with congruence constraints. • Proposes a new graph representation of the problem. • Provides optimal inapproximability results for the optimization problem. • Exposes the close bounds that relate this problem with the MAX DICUT problem. • Customizes and applies approximation algorithms for MAX DICUT in real case studies. This paper aims to synchronize timetables in a transit network so as to minimize the total passenger transfer waiting time. Assuming a fixed headway for each line, we first formulate the problem as an optimization problem with congruence constraints. We show that the problem is NP-hard, and investigate several special cases of the problem that are solvable in polynomial time. Furthermore, we show that the local search for the general problem is equivalent to the well-studied maximum directed cut problem. As such, we use an approximation algorithm for the maximum directed cut problem to solve the timetable synchronization problem. We assess the quality of the algorithm on a real-world case study, and show that our algorithm significantly outperforms the state-of-the-art in the literature. Lastly, we relax the fixed headway assumption, and propose an efficient recursive quasi-linear time algorithm to minimize the total transfer waiting time in this general setting. [ABSTRACT FROM AUTHOR]

Mobile Cloud Computing (MCC) aims at leveraging remote resources to boost application performance on mobile devices while conserving resources such as battery, memory, and storage. Offloading computations and outsourcing tasks are, however, associated with numerous challenges known from distributed systems. Typical mobile applications have a monolithic design and are not laid out for a distributed deployment and execution. In this work, we present how to design and partition such applications and how these partitions stay synchronized in a cost-efficient manner at runtime. We introduce our comprehensive and extendable framework MOCCAA (MObile Cloud Computing AdaptAble) that supports developers along this path. Its performance gain is mainly achieved through a new graph partitioning heuristic that is searching for the maximally beneficial cut, through minimized monitoring efforts for resource consumption prediction, through scalable and location-aware resource discovery and management, and through our graph-based delta synchronization of local and remote object states. In particular, the graph partitioning heuristic and the delta synchronization allow us to reduce synchronization costs and improve quality dimensions such as latency and bandwidth consumption. [ABSTRACT FROM AUTHOR]

Given an undirected edge weighted graph, the graph partitioning problem consists in determining a partition of the node set of the graph into subsets of prescribed sizes, so as to maximize the sum of the weights of the edges having both endpoints in the same subset. We introduce a new class of bounds for this problem relying on the full spectral information of the weighted adjacency matrix A. The expression of these bounds involves the eigenvalues and particular geometrical parameters defined using the eigenvectors of A. A connection is established between these parameters and the maximum cut problem. We report computational results showing that the new bounds compare favorably with previous bounds in the literature. [ABSTRACT FROM AUTHOR]

For a graph $G$ , let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$ , 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$. Alon et al. ['Maximum cuts and judicious partitions in graphs without short cycles', J. Combin. Theory Ser. B 88 (2003), 329–346] conjectured that, for any fixed graph $H$ , there exists an $\unicode[STIX]{x1D716}(H)>0$ such that $f(m,H)\geq m/2+\unicode[STIX]{x1D6FA}(m^{3/4+\unicode[STIX]{x1D716}})$. We show that, for any wheel graph $W_{2k}$ of $2k$ spokes, there exists $c(k)>0$ such that $f(m,W_{2k})\geq m/2+c(k)m^{(2k-1)/(3k-1)}\log m$. In particular, we confirm the conjecture asymptotically for $W_{4}$ and give general lower bounds for $W_{2k+1}$. [ABSTRACT FROM AUTHOR]

The paper considers the problem of finding the maximum cut on graphs. A new model of the problem is given in terms of the base of polymatroid. It is shown that the problem solution can be found by the greedy algorithm after the optimal linear ordering of the vertices has been determined. [ABSTRACT FROM AUTHOR]

The maximum independent sets in the Doob graphs D(m, n) are analogs of the distance-2 MDS codes in Hamming graphs and of the latin hypercubes. We prove the characterization of these sets stating that every such set is semilinear or reducible. As related objects, we study vertex sets with maximum cut (edge boundary) in D(m, n) and prove some facts on their structure. We show that the considered two classes (the maximum independent sets and the maximum-cut sets) can be defined as classes of completely regular sets with specified 2-by-2 quotient matrices. It is notable that for a set from the considered classes, the eigenvalues of the quotient matrix are the maximum and the minimum eigenvalues of the graph. For D(m, 0), we show the existence of a third, intermediate, class of completely regular sets with the same property. [ABSTRACT FROM AUTHOR]

Copyright of Cybernetics & Systems Analysis / Kibernetiki i Sistemnyj Analiz is the property of V.M. Glushkov Institute of Cybernetics of NAS of Ukraine and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

A co-bipartite chain graph is a co-bipartite graph in which the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion. It is known that the maximum cardinality cut problem ( $${\textsc {MaxCut}}$$ ) is $${\textsc {NP}}{\text {-hard}}$$ in co-bipartite graphs (Bodlaender and Jansen, Nordic J Comput 7(2000):14-31, 2000). We consider $${\textsc {MaxCut}}$$ in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that $${\textsc {MaxCut}}$$ is polynomial time solvable in this graph class. [ABSTRACT FROM AUTHOR]

A k -radius sequence for a graph G is a sequence of vertices of G (typically with repetitions) such that for every edge u v of G vertices u and v appear at least once within distance k in the sequence. The length of a shortest k -radius sequence for G is denoted by f k ( G ) . We give an asymptotically tight estimation on f k ( G ) for complete bipartite graphs which matches a lower bound, valid for all bipartite graphs. We also show that determining f k ( G ) for an arbitrary graph G is NP-hard for every constant k > 1 . [ABSTRACT FROM AUTHOR]