2023/07/31 by Arkadiusz Hiler, Hiler, Arkadiusz, Robert Lewoń +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Property tester #Software Testing and Debugging Techniques #coNP-completeness #pseudotester #secure set #security
paper · doi:10.34767/simis.2014.14.02
openalex publication_date 2023/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/01
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.