Abstrakt. Grafer används ofta för att modellera riskhantering i olika system. Särskilt Caskurlu et al. I [6] har man övervägt ett system som i huvudsak utgör ett trepartsdiagram. Målet med denna modell är att minska risken i systemet under en fördefinierad risktröskelnivå. Det kan visas att det huvudsakliga målet i detta riskhanteringssystem kan formuleras som ett partiellt Vertex Cover problem på bipartit grafer. Det är välkänt att vertex cover problem är i P på bipartite grafer; dock, beräknings komplexiteten av den partiella vertex cover problem på bipartite grafer är öppen. I detta dokument visar vi att det partiella vertex cover problemet är NP-hård på bipartit grafer. Sedan visar vi att den budgeterade maximal täckning problem (ett problem i samband med partiella vertex cover problem) medger en - approximation algoritm i klassen av bipartite grafer, som matchar integrality gap av en naturlig LP avkoppling.
I REF visades att PVC-problemet på bipartitgrafer är NP-hård.
On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
{'venue': 'IFIP TCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}