A cut is a partition of a graph's nodes into two sets, and we say that an edge crosses the cut if it connects two nodes belonging to different sets. A maximum cut is a cut that maximises the number of crossing edges. We show that for any sufficiently small ε > 0 it is NP-hard to distinguish between graphs for which at least a fraction 1 - ε of all edges crosses the maximum cut and graphs for which at most a fraction 1 - 1.4568 ε of all edges crosses the maximum cut. The previous state of the art had a constant smaller than 1.375 in place of 1.4568. / Ett snitt är en partition av en grafs noder i två mängder, och vi säger att en kant korsar snittet om dess ändpunkter tillhör olika mängder. Ett maximalt snitt är ett snitt som maximerar antalet kanter som korsar snittet. Vi bevisar att det för alla tillräckligt små konstanter ε > 0 är NP-svårt att skilja mellan grafer för vilka minst en andel 1 - ε av alla kanter korsar det maximala snittet och grafer för vilka högst en andel 1 - 1.4568 ε av alla kanter korsar det maximala snittet. Detta är en förbättring jämfört med ett tidigare resultat som hade en konstant mindre än 1.375 istället för 1.4568.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-231587 |
| Date | January 2018 |
| Creators | Wiman, Mårten |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2018:317 |
Page generated in 0.0012 seconds