Abstrakt. För fasta heltal r, l ≥ 0, kallas en graf G en (r, l)-graf om vertex-uppsättningen V (G) kan delas upp i r oberoende uppsättningar och l-kluster. Detta för oss till följande naturliga parameteriserade frågor: Vertex (r, l)-Partization och Edge (r, l)-Partization. En inmatning till dessa problem består av en graf G och ett positivt heltal k och målet är att avgöra om det finns en uppsättning S  på V (G) (S  på E(G)) så att strykningen av S från G resulterar i en (r, l)-graf. Dessa problem generaliserar väl studerade problem som Odd Cycle Transversal, Edge Odd Cycle Transversal, Split Vertex Deletion och Split Edge Deletion. Vi hoppas inte att få parameteriserade algoritmer för vare sig Vertex (r, l)-Partization eller Edge (r, l)-Partization när någon av r eller l är minst 3 som igenkänningsproblemet i sig är NP-komplett. Detta lämnar fallet med r, l och {1, 2}. Vi fullbordar nästan den parameteriserade komplexiteten dikotomi för dessa problem genom att få följande resultat: 1. Vi visar att Vertex (r, l)-Partization är fast parameterdragbar (FPT) för r, l  till {1, 2}. Sedan utformar vi en O( ε log n)-faktor approximationsalgoritmer för dessa problem. Dessa approximationsalgoritmer används sedan för att designa polynomstora randomiserade Turingkärnor för dessa problem. 2. Utgångspunkten är följande: Kant (r, l)-Partificering är FPT när (r, l) (( 1, 2), (2, 1)}. Den parameteriserade komplexiteten i Edge (2, 2)-Partering förblir dock öppen. För vår approximation algoritmer och därmed för Turing kärnor använder vi en intressant ändlig förbjuden inducerad graf karakterisering, för en klass av grafer som kallas (r, l)-split grafer, korrekt innehåller klassen av (r, l)-grafer. Detta tillvägagångssätt för att erhålla approximationsalgoritmer kan vara av oberoende intresse.
Nyligen, Kolay och Panolan REF övervägde problemet med att ta bort k hörn eller kanter för att få en (r, l)-graf.
Parameterized Algorithms for Deletion to (r,l)-graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}