I minimal planarization problem, med tanke på n-vertex graf, målet är att hitta en uppsättning hörn av minimal kardinalitet vars avlägsnande lämnar en planar graf. Detta är ett grundläggande problem i topologisk grafteori. Vi presenterar en log O(1) n- approximation algoritm för detta problem på allmänna grafer med körtid n O(logg n/ log log n). Vi får också en O(n ε )-uppskattning med körtid n O(1/ε) för godtyckligt liten konstant ε > 0. Innan vårt arbete, ingen icke-trivial algoritm var känd för detta problem på allmänna grafer, och det mest kända resultatet även på grafer av begränsad grad var en n 0(1) - approximation [1]. Som en omedelbar följd, vi får också förbättrad approximation algoritmer för korsning nummer problem på grafer av begränsad grad. Specifikt får vi O(n 1/2+ε ) approximation och n 1/2 log O(1) n- approximation algoritmer i tid n O(1/ε) och n O(log n/ log log log n) respektive. Det tidigare mest kända resultatet var en polynom-tid n 9/10 log O(1) n approximation algoritm [2]. Vår algoritm introducerar flera nya verktyg inklusive en effektiv rutnät-minor konstruktion för apex grafer, och en ny metod för att beräkna irrelevanta hörn. Analoger av dessa verktyg var tidigare endast tillgängliga för exakta algoritmer. Vårt arbete ger effektiva implementeringar av dessa idéer vid fastställande av approximationsalgoritmer, vilket kan vara av oberoende intresse.
När F = {K 5, K 3, 3 }, är detta problem känt som Minimum Planarization och medger polylog(n)- tillnärmning i tid n O(log n/ log log n) REF.
Polylogarithmic Approximation for Minimum Planarization (Almost)
{'venue': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}