Algorithms for testing security in graphs
DOI:
https://doi.org/10.34767/SIMIS.2014.14.02Keywords:
Testowanie własności, pseudotester, zbiór bezpieczny, bezpieczeństwo, coNP-zupełnośćAbstract
W niniejszym artykule przedstawiamy metodę weryfikowania bezpieczeństwa zbioru w grafie, dającą wysokie prawdopodobieństwo poprawnej weryfikacji. Problemem jest określenie, czy dla danego grafu G oraz podzbioru S zbioru wierzchołków tego grafu zbiór S jest bezpieczny, to znaczy każdy jego podzbiór X spełnia warunek: |N[X] ∩ S| ≥ |N[X] \ S|, gdzie N[X] jest domkniętym sąsiedztwem zbioru X w grafie G. Zaprojektowaliśmy pseudotester o wielomianowej złożoności obliczeniowej dla decyzyjnego problemu
bezpieczeństwa zbioru w grafie wykorzystując m.in. koncepcję symulowanego wyżarzania. Wykonaliśmy testy dla grafów, w których podgraf indukowany przez zbiór S jest drzewem lub grafem ograniczonego stopnia (przez 3 oraz 4). Z uwagi na coNP-zupełność problemu bezpieczeństwa zaproponowane przez nas podejście jest uogólnieniem koncepcji testowania własności znanej z literatury.
References
Blukis T. „Secure sets in graphs” (in Polish), MSc Thesis at Gdańsk University of Technology, 2012.
Blukis T., Lewoń R., Małafiejski M., „Efficient algorithms for graph security testing”, IX International Colloquium on Graphs and Optimization (Sirmione, Italy), 2014 (prepared to submit to special issue of Discrete Applied Mathematics).
Brigham R., Dutton R., Hadetniemi S., „Security in graphs”, Discrete Applied Mathematics 2007, vol. 155, pp. 1708-1714.
Dutton R., „Secure set algorithms and complexity”, Congressus Numerantium 2006, vol. 180, pp. 115-121.
Dutton R., Lee R., Brigham R., „Bounds on a graph’s security number”, Discrete Applied Mathematics 2008, vol. 156, pp. 695-704.
Dutton R., Enciso R., „Parameterized complexity of secure sets”, Congressus Numerantium 2008, vol. 189, pp 161-168.
Gieniusz T., Lewoń R., Małafiejski M., „Graph security testing”, Journal of Applied Computer Science 2014, vol.22, no. 2 (in press).
Goldreich O., Ron D., „A Sublinear Bipartitness Tester for Bounded Degree Graphs”, Combinatorica 1999, vol. 19, pp. 335-373.
Goldreich O., Goldwasser S., Ron D., „Property testing and its connection to learning and approximation”, Journalof the ACM 1998, vol. 45, pp. 653-750.
Raskhodnikova S., „Property Testing: Theory andApplications”, PhD Thesis at Massachusetts Institute ofTechnology, 2003.
Rubinfeld R., Sudan M., „Robust characterizations ofpolynomials with applications to program testing”, SIAM Journal on Computing 1996, vol. 25, no. 2, pp. 252-271
