An upper bound for the maximum cut mean value

DOI10.1007/BFB0024489MaRDI QIDQ4373671zbMATH OpenFDO

Authors Paola Campadelli, Roberto Posenato, Alberto Bertoni

Publication date 11 June 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0024489

zbMATH Keywords

expectationsmaximum cutMAXIMUM CUTNP-hardrandom graphrandom matrixupper bound

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

Exact solution of any NP-hard problem requires performance of tests whose number is exponentially dependent on the problem size. Therefore, solving NP-hard problems by inspection, i.e. performing the requested number of tests, is possible only for limited size instances of the problem. Nevertheless, numerous solutions exist if the structure of a given instance of the NP-hard problem is ``dense. Then, random selection of substructures and test them for a solution enables us to solve the problem expecting the number of requested tests that is estimated by a polynomial on size of the instance. The paper supplies the proof that expectations \(f(x,n)\) and \(r(x,n)\) for sufficiently large \(x\): \[ \lim_{n\to \infty} f(x,n) \leq {1\over 2} +\sqrt {{\ln 2\over 2x}}, \quad \lim_{n\to\infty} r(x,n) \leq {1\over 2} +{1\over \sqrt x} +{1\over 2} {\ln 2 \over x}, \] where \(f(x,n)\) denotes the expectation of a subset of vertices, \(r(x,n)\) denotes the corresponding expectation for random \(2x\)-regular graphs, \(n\) is the number of graph vertices, and \(x\) is the number of graph edges, are the solution of the MAXIMUM CUT problem for a random graph. Similar results were investigated earlier for the MAXIMUM CLIQUE problem. The basic idea of the given proofs is the estimation of the number of given type submatrices included in the adjacency matrix of fixed size that represents a random graph. In order to make the extension of these results on a wide class of NP-hard problems concerning different structures it is worthwile to mention that numerous historically investigated NP-hard problems can be seen as instances of intractable matrix problems, see \textit{A. Kapralski} [Sequential and parallel processing in depth search machines (1994; Zbl 0840.68031)]. Solving any such NP-hard problem means finding a specific submatrix. Then, in order to complete the concerned proofs, we have to estimate the number of specific submatrices or sets of such submatrices included in a random matrix that represents a given structure. For the entire collection see [Zbl 0877.00011].

Recommendations

• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• The solution of some random NP-hard problems in polynomial expected time
• scientific article; zbMATH DE number 2079360
• A probabilistic result for the max-cut problem on random graphs

Cited in

(6)

• On the maximal cut in a random hypergraph
• Sparse graphs: metrics and random models
• MAX k‐CUT and approximating the chromatic number of random graphs
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• Preface
• A probabilistic result for the max-cut problem on random graphs

This page was built for publication: An upper bound for the maximum cut mean value

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4373671)