Algorithms for testing security in graphs

• Autorzy: Hiler A. , Lewoń R. , Małafiejski M.

Warianty tytułu

PL

Algorytmy testujące bezpieczeństwo zbioru wierzchołków grafu

• Języki publikacji: EN

Abstrakty

EN

In this paper we propose new algorithmic methods giving with a high probability the correct answer to the decision problem of security in graphs. For a given graph G and a subset S of a vertex set of G we have to decide whether S is secure, i.e. every subset X of S fulfils the condition:|N[X] ∩ S| ≥ |N[X] \ S|, where N[X]is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based on the heuristic using simulated annealing and tested it on graphs with induced small subgraphs G[S] being trees or graphs with a bounded degree (by 3 or 4). Our approach is a generalization of the concept of property testers known from the subject literature, but we applied our concepts to the coNP-complete problem.

PL

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.

Słowa kluczowe

EN

property tester; pseudotester; secure set; security; coNP-completeness

PL

testowanie własności; pseudotester; zbiór bezpieczny; bezpieczeństwo; coNP-zupełność

• Wydawca: Instytut Informatyki Uniwersytet Kazimierza Wielkiego
• Czasopismo: Studia i Materiały Informatyki Stosowanej
• Rocznik: 2014
• Tom: nr 14
• Strony: 18--26
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Hiler A.

• Gdańsk University of Technology Department of Algorithms and System Modeling Gabriela Narutowicza 11/12, 80-233 Gdańsk

autor

Lewoń R.

• Gdańsk University of Technology Department of Algorithms and System Modeling Gabriela Narutowicza 11/12, 80-233 Gdańsk

autor

Małafiejski M.

• Gdańsk University of Technology Department of Algorithms and System Modeling Gabriela Narutowicza 11/12, 80-233 Gdańsk

Bibliografia

• 1. Blukis T. „Secure sets in graphs” (in Polish), MSc Thesis at Gdańsk University of Technology, 2012.
• 2. 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).
• 3. Brigham R., Dutton R., Hadetniemi S., „Security in graphs”, Discrete Applied Mathematics 2007, vol. 155, pp. 1708-1714.
• 4. Dutton R., „Secure set algorithms and complexity”, Congressus Numerantium 2006, vol. 180, pp. 115-121.
• 5. Dutton R., Lee R., Brigham R., „Bounds on a graph’s security number”, Discrete Applied Mathematics 2008, vol. 156, pp. 695-704.
• 6. Dutton R., Enciso R., „Parameterized complexity of secure sets”, Congressus Numerantium 2008, vol. 189, pp 161-168.
• 7. Gieniusz T., Lewoń R., Małafiejski M., „Graph security testing”, Journal of Applied Computer Science 2014, vol. 22, no. 2 (in press).
• 8. GitHub repository, http://github.com/ivyl/graph-security.
• 9. Goldreich O., Ron D., „A Sublinear Bipartitness Tester for Bounded Degree Graphs”, Combinatorica 1999, vol. 19, pp. 335-373.
• 10. Goldreich O., Goldwasser S., Ron D., „Property testing and its connection to learning and approximation”, Journal of the ACM 1998, vol. 45, pp. 653-750.
• 11. McKay B., nauty Software Program, Version 2.5, http://cs.anu.edu.au/˜bdm/nauty/, 2013.
• 12. Raskhodnikova S., „Property Testing: Theory and Applications”, PhD Thesis at Massachusetts Institute of Technology, 2003.
• 13. Rubinfeld R., Sudan M., „Robust characterizations of polynomials with applications to program testing”, SIAM Journal on Computing 1996, vol. 25, no. 2, pp. 252-271.