Abstrakt. En uppsättning fylogenetiska träd med överlappande bladuppsättningar är konsekvent om det kan slås samman utan konflikter till ett superträd. I detta papper studerar vi polynom-tid ungefärlighet av två relaterade optimeringsproblem som kallas maximal rotade trioler konsistens problem (MaxRTC) och den minsta rotade trioler inkonsekvens problem (MinRTI) där indata är en uppsättning R rotade trioler, och där målen är att hitta en största kardinalitet delmängd av R som är konsekvent och en minsta kardinalitet delmängd av R vars avlägsnande från R resulterar i en konsekvent uppsättning, respektive. Vi visar först att en enkel modifiering av Wu's Best-Pair-Merge-First heuristic [25] resulterar i en bottom-up-baserad 3- approximation för MaxRTC. Vi visar sedan hur någon approximation algoritm för MinRTI kan användas för att approxima MaxRTC, och därmed få den första polynom-tid approximation algoritm för MaxRTC med approximation förhållande mindre än 3. Därefter bevisar vi att för en uppsättning rotade trioler som genereras under en enhetlig slumpmässig modell, den maximala fraktionen av trioler som kan överensstämma med något träd är ungefär en tredjedel, och sedan ge en deterministisk konstruktion av en triolet uppsättning med en liknande egenskap som senare används för att bevisa att både MaxRTC och MinRTI är NP-hård även om begränsas till minimalt täta fall. Slutligen bevisar vi att MinRTI inte kan approximeras inom ett förhållande av  ska(log n) i polynom tid, om inte P = NP.
För en färsk undersökning av andra optimeringsproblem relaterade till rotade trillingar konsistens (till exempel att beräkna en maximal kardinalitet delmängd R av en inkonsekvent uppsättning R rotade trillingar så att R är konsekvent), se avsnitt 2 i REF.
New Results on Optimizing Rooted Triplets Consistency
{'venue': 'ISAAC', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}