Algorithms for testing security in graphs
DOI:
https://doi.org/10.34767/SIMIS.2014.14.02Słowa kluczowe:
Property tester, pseudotester, secure set, security, coNP-completenessAbstrakt
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.
Bibliografia
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
