Set de vârf de feedback - Feedback vertex set

În disciplina matematică a teoriei graficelor , un set de vârf de feedback (FVS) al unui grafic este un set de vârfuri a căror îndepărtare lasă un grafic fără cicluri („îndepărtare” înseamnă ștergerea vârfului și a tuturor muchiilor adiacente acestuia). În mod echivalent, fiecare FVS conține cel puțin un vârf al oricărui ciclu din grafic. Numărul setului de vertex de feedback al unui grafic este mărimea celui mai mic set de vârfuri de feedback. Feedback - ul minim la vârf set problemă este NP-completă problemă; a fost printre primele probleme care s-au dovedit a fi NP-complete . Are aplicații largi în sistemele de operare , sistemele de baze de date și proiectarea cipurilor VLSI .

Definiție

Problema deciziei FVS este următoarea:

INSTANȚĂ: un grafic (neorientat sau direcționat) și un număr întreg pozitiv .${\ displaystyle G = (V, E)}$${\ displaystyle k}$

ÎNTREBARE: Există un subset cu astfel încât, atunci când toate vârfurile și marginile lor adiacente să fie șterse , restul este fără cicluri ?${\ displaystyle X \ subseteq V}$${\ displaystyle | X | \ leq k}$${\ displaystyle X}$${\ displaystyle G}$

Graficul care rămâne după îndepărtarea de la o indus pădure (resp. Un indus direcționat grafic aciclic în cazul graficelor îndreptate ). Astfel, găsirea unui FVS minim într-un grafic este echivalent cu găsirea unei păduri maxime induse (resp. Graficul aciclic îndreptat maxim indus în cazul graficelor direcționate ). ${\ displaystyle G [V \ setminus X]}$${\ displaystyle X}$${\ displaystyle G}$

NP-duritate

Karp (1972) a arătat că problema FVS minimă pentru graficele direcționate este NP-completă . Problema rămâne NP-completă pe graficele direcționate cu maxim în grad și în afara gradului doi și pe graficele plane direcționate cu maxim în grad și în afara gradului trei.

Reducerea Karp implică, de asemenea, completitudinea NP a problemei FVS pe grafice nedirecționate , unde problema rămâne NP-hard pe grafice de grad maxim patru. Problema FVS poate fi rezolvată în timp polinomial pe grafice de grad maxim cel mult trei.

Algoritmi exacți

Problema corespunzătoare de optimizare NP a găsirii dimensiunii unui set de vârfuri de feedback minim poate fi rezolvată în timpul O (1.7347 ⁿ ), unde n este numărul de vârfuri din grafic. Acest algoritm calculează de fapt o pădure maximă indusă și, atunci când se obține o astfel de pădure, complementul său este un set de vârf de feedback minim. Numărul de seturi de vertex de feedback minim într-un grafic este mărginit de O (1,8638 ⁿ ). Problema setului de vârfuri de feedback direcționat poate fi încă rezolvată în timpul O * (1.9977 ⁿ ), unde n este numărul de vârfuri din graficul direcționat dat. Versiunile parametrizate ale problemelor direcționate și nedirecționate sunt tratabile cu parametri fixi .

În graficele nedirecționate de grad maxim trei, problema setului de vârfuri de feedback poate fi rezolvată în timp polinomial , transformându-l într-o instanță a problemei parității matroide pentru matroizi liniari .

Apropiere

Problema nedirecționată este APX-completă . Acest lucru rezultă din următoarele fapte.

• Integritatea APX a problemei acoperirii vertexului ;
• Existența unei aproximări care păstrează reducerea L de la problema acoperirii vârfului la aceasta;
• Algoritmi de aproximare a factorilor constanți existenți.

Cel mai cunoscut algoritm de aproximare pe grafice nedirecționate este cu un factor de doi.

Dacă versiunea direcționată este timp polinomial aproximabil în raport constant și, prin urmare, APX-complete este o întrebare deschisă.

Limite

Conform teoremei Erdős – Pósa , dimensiunea unui set de vertex de feedback minim se încadrează într-un factor logaritmic al numărului maxim de cicluri vertex-disjunct în graficul dat.

Concepte conexe

• În loc de vârfuri, se poate lua în considerare un set de margini de feedback - un set de margini într-un grafic nedirecționat, a cărui eliminare face graficul aciclic. Mărimea celei mai mici margini de feedback setate într-un grafic se numește rangul de circuit al graficului. Spre deosebire de numărul FVS, rangul circuitului poate fi calculat cu ușurință: este , unde C este setul de componente conectate ale graficului. Problema găsirii unui set de margini de feedback mai mic este echivalentă cu găsirea unei păduri întinse , care se poate face în timp polinomial .${\ displaystyle | E | - | V | + | C |}$

• Conceptul analog într-un grafic direcționat este setul de arc de feedback (FAS) - un set de arcuri direcționate a căror îndepărtare face graficul aciclic. Găsirea unui FAS cel mai mic este o problemă NP-hard.

Aplicații

• În sistemele de operare , seturile de vârfuri de feedback joacă un rol important în studiul recuperării impasului . În graficul de așteptare al unui sistem de operare, fiecare ciclu direcționat corespunde unei situații de impas. Pentru a rezolva toate blocajele, unele procese blocate trebuie întrerupte. Un vârf de feedback minim setat în acest grafic corespunde unui număr minim de procese pe care trebuie să le întrerupeți.

• Problema setului de vârf de feedback are aplicații în proiectarea cipurilor VLSI .
• O altă aplicație este în teoria complexității. Unele probleme de calcul pe grafice sunt NP-hard în general, dar pot fi rezolvate în timp polinomial pentru grafice cu număr FVS mărginit. Câteva exemple sunt izomorfismul graficului și problema reconfigurării căii.

Note

Referințe

Articole de cercetare

Manuale și articole de sondaj

• Festa, P .; Pardalos, PM; Resende, MGC (2000), „Feedback set problems”, în Du, D.-Z .; Pardalos, PM (eds.), Handbook of Combinatorial Optimization, Supliment vol. A (PDF) , Kluwer Academic Publishers, pp. 209–259
• Garey, Michael R .; Johnson, David S. (1979), Computers and Intractability: A Guide to Theory of NP-Completeness , WH Freeman, A1.1: GT7, p. 191 , ISBN 978-0-7167-1045-5
• Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Conceptele sistemului de operare (ediția a VIII-a), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5