The anonymous subgraph problem

Article

Bettinelli, A., Liberti, L., Raimondi, F. and Savourey, D. 2013. The anonymous subgraph problem. Computers and Operations Research. 40 (4), pp. 973-979. https://doi.org/10.1016/j.cor.2012.11.018
TypeArticle
TitleThe anonymous subgraph problem
AuthorsBettinelli, A., Liberti, L., Raimondi, F. and Savourey, D.
Abstract

In this work we address the Anonymous Subgraph Problem (ASP). The problem asks to decide whether a directed graph contains anonymous subgraphs of a given family. This problem has a number of practical applications and here we describe three of them (Secret Santa Problem, anonymous routing, robust paths) that can be formulated as ASPs. Our main contributions are (i) a formalization of the anonymity property for a generic family of subgraphs, (ii) an algorithm to solve the ASP in time polynomial in the size of the graph under a set of conditions, and (iii) a thorough evaluation of our algorithms using various tests based both on randomly generated graphs and on real-world instances.

KeywordsAnonymity; Anonymous routing; Secret Santa; Graph topology
PublisherElsevier
JournalComputers and Operations Research
ISSN0305-0548
Electronic1873-765X
Publication dates
Online05 Dec 2012
Print01 Apr 2013
Publication process dates
Deposited23 Apr 2015
Output statusPublished
Copyright Statement

This is a RoMEO green journal - author can archive pre-print (ie pre-refereeing)

Digital Object Identifier (DOI)https://doi.org/10.1016/j.cor.2012.11.018
Web of Science identifierWOS:000314483400008
LanguageEnglish
First submitted version
Permalink -

https://repository.mdx.ac.uk/item/850y6

Log in to edit

Download files

  • 134
    total views
  • 33
    total downloads
  • 2
    views this month
  • 0
    downloads this month

Export as

Related outputs

Implementing a digital twin for a robotic platform to support large-scale coding classes
Heeney, M., Androutsopoulos, K. and Raimondi, F. 2024. Implementing a digital twin for a robotic platform to support large-scale coding classes. Santos, A.L. and Pinto-Albuquerque, M. (ed.) 5th International Computer Programming Education Conference. Lisbon, Portugal 27 - 28 Jun 2024 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH. https://doi.org/10.4230/oasics.icpec.2024.15
Differential cost analysis with simultaneous potentials and anti-potentials
Žikelić, Ð., Chang, B., Bolignano, P. and Raimondi, F. 2022. Differential cost analysis with simultaneous potentials and anti-potentials. 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. San Diego, USA 13 - 17 Jun 2022 Association for Computing Machinery (ACM). pp. 442-457 https://doi.org/10.1145/3519939.3523435
Automatic annotation of confidential data in Java code
Bastys, I., Bolignano, P., Raimondi, F. and Schoepe, D. 2022. Automatic annotation of confidential data in Java code. Aïmeur, E., Laurent, M., Yaich, R., Dupont, B. and Garcia-Alfaro, J. (ed.) FPS 2021: The 14th International Symposium on Foundations & Practice of Security. Paris, France 08 - 12 Dec 2021 Springer. pp. 146-161 https://doi.org/10.1007/978-3-031-08147-7_10
Comparing approaches for model-checking strategies under imperfect information and fairness constraints
Busard, S., Pecheur, C., Qu, H. and Raimondi, F. 2019. Comparing approaches for model-checking strategies under imperfect information and fairness constraints. International Journal on Software Tools for Technology Transfer. 21 (4), pp. 449-469. https://doi.org/10.1007/s10009-018-0505-6
Multi-agent based simulations of block-free distributed ledgers
Bottone, M., Raimondi, F. and Primiero, G. 2018. Multi-agent based simulations of block-free distributed ledgers. The 32nd IEEE International Conference on Advanced Information Networking and Applications Workshops (WAINA). Krakow, Poland 16 - 18 May 2018 IEEE. pp. 585-590 https://doi.org/10.1109/WAINA.2018.00149
Analysis and verification of ECA rules in intelligent environments
Cacciagrano, D., Corradini, F., Culmone, R., Gorogiannis, N., Mostarda, L., Raimondi, F. and Vannucchi, C. 2018. Analysis and verification of ECA rules in intelligent environments. Journal of Ambient Intelligence and Smart Environments. 10 (3), pp. 261-273. https://doi.org/10.3233/AIS-180487
MIRTO: an open-source robotic platform for education
Androutsopoulos, K., Aristodemou, L., Boender, J., Bottone, M., Currie, E., El-Aroussi, I., Fields, B., Gheri, L., Gorogiannis, N., Heeney, M., Micheletti, M., Loomes, M., Margolis, M., Petridis, M., Piermarteri, A., Primiero, G., Raimondi, F. and Weldin, N. 2018. MIRTO: an open-source robotic platform for education. 3rd European Conference on Software Engineering Education. Seeon, Germany 14 - 15 Jun 2018 Association for Computing Machinery (ACM). pp. 55-62 https://doi.org/10.1145/3209087.3209106
CoSMed: a confidentiality-verified social media platform
Bauereiß, T., Pesenti Gritti, A., Popescu, A. and Raimondi, F. 2018. CoSMed: a confidentiality-verified social media platform. Journal of Automated Reasoning. 61 (1-4), pp. 113-119. https://doi.org/10.1007/s10817-017-9443-3
Implementing virtual pheromones in BDI robots using MQTT and Jason
Bottone, M., Palumbo, F., Primiero, G., Raimondi, F. and Stocker, R. 2016. Implementing virtual pheromones in BDI robots using MQTT and Jason. 2016 5th IEEE International Conference on Cloud Networking (Cloudnet). Pisa, Italy 03 - 05 Oct 2016 Institute of Electrical and Electronics Engineers (IEEE). pp. 196-199 https://doi.org/10.1109/CloudNet.2016.22
From raw data to agent perceptions for simulation, verification, and monitoring
Bottone, M., Primiero, G., Raimondi, F. and Rungta, N. 2016. From raw data to agent perceptions for simulation, verification, and monitoring. 12th International Conference on Intelligent Environment 2016:- 5th International Workshop on Reliability of Intelligent Environments (WoRIE’16). London, United Kingdom 14 - 16 Sep 2016 IOS Press. pp. 66-75 https://doi.org/10.3233/978-1-61499-690-3-66
Trust and distrust in contradictory information transmission
Primiero, G., Raimondi, F., Bottone, M. and Tagliabue, J. 2017. Trust and distrust in contradictory information transmission. Applied Network Science. 2 (1). https://doi.org/10.1007/s41109-017-0029-0
Examining the interaction between fourth estate and Twitter: an exploratory case study
Barn, B., Barn, R., Raimondi, F. and Mukherjee, U. 2017. Examining the interaction between fourth estate and Twitter: an exploratory case study. HUSO 2017: Third International Conference on Human and Social Analytics. Nice, France 23 - 27 Jul 2017 IARIA. pp. 11-17
Symbolic verification of event–condition–action rules in intelligent environments
Vannucchi, C., Diamanti, M., Mazzante, G., Cacciagrano, D., Culmone, R., Gorogiannis, N., Mostarda, L. and Raimondi, F. 2017. Symbolic verification of event–condition–action rules in intelligent environments. Journal of Reliable Intelligent Environments. 3 (2), pp. 117-130. https://doi.org/10.1007/s40860-017-0036-z
A novel symbolic approach to verifying epistemic properties of programs
Gorogiannis, N., Raimondi, F. and Boureanu, I. 2017. A novel symbolic approach to verifying epistemic properties of programs. Twenty-Sixth International Joint Conference on Artificial Intelligence. Melbourne, Australia 19 - 25 Aug 2017 International Joint Conferences on Artificial Intelligence. pp. 206-212 https://doi.org/10.24963/ijcai.2017/30
CoSMeDis: a distributed social media platform with formally verified confidentiality guarantees
Bauereiß, T., Pesenti Gritti, A., Popescu, A. and Raimondi, F. 2017. CoSMeDis: a distributed social media platform with formally verified confidentiality guarantees. 38th IEEE Symposium on Security and Privacy. San Jose, CA, USA 22 - 26 May 2017 Institute of Electrical and Electronics Engineers (IEEE). pp. 729-748 https://doi.org/10.1109/SP.2017.24
A proof-theoretic trust and reputation model for VANET
Primiero, G., Raimondi, F., Chen, T. and Nagarajan, R. 2017. A proof-theoretic trust and reputation model for VANET. S4CIP’17: 2nd Workshop on Safety & Security aSSurance for Critical Infrastructures Protection. Paris, France 29 Apr 2017 Institute of Electrical and Electronics Engineers (IEEE). pp. 146-152 https://doi.org/10.1109/EuroSPW.2017.64
The packing chromatic number of the infinite square lattice is between 13 and 15
Martin, B., Raimondi, F., Chen, T. and Martin, J. 2017. The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics. 225, pp. 136-142. https://doi.org/10.1016/j.dam.2017.03.013
MCMAS: an open-source model checker for the verification of multi-agent systems
Lomuscio, A., Qu, H. and Raimondi, F. 2017. MCMAS: an open-source model checker for the verification of multi-agent systems. International Journal on Software Tools for Technology Transfer. 19 (1), pp. 9-30. https://doi.org/10.1007/s10009-015-0378-x
Contradictory information flow in networks with trust and distrust
Primiero, G., Bottone, M., Raimondi, F. and Tagliabue, J. 2016. Contradictory information flow in networks with trust and distrust. 5th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016). Milan 01 - 06 Dec 2016 Springer. https://doi.org/10.1007/978-3-319-50901-3_29
Teaching functional patterns through robotic applications
Boender, J., Currie, E., Loomes, M., Primiero, G. and Raimondi, F. 2016. Teaching functional patterns through robotic applications. The 4th International Workshop on Trends in Functional Programming in Education, TFPIE 2015. Sophia-Antipolis, France 02 Jun 2015 Open Publishing Association. pp. 17-29 https://doi.org/10.4204/EPTCS.230.2
CoSMed: a confidentiality-verified social media platform
Bauereiß, T., Pesenti Gritti, A., Popescu, A. and Raimondi, F. 2016. CoSMed: a confidentiality-verified social media platform. Blanchette, J.C. and Merz, S. (ed.) ITP 2016: 7th International Conference on Interactive Theorem Proving. Nancy, France 22 - 25 Aug 2016 Springer. pp. 87-106 https://doi.org/10.1007/978-3-319-43144-4_6
A model for trustworthy orchestration in the internet of things
Bottone, M., Primiero, G., Raimondi, F. and De Florio, V. 2016. A model for trustworthy orchestration in the internet of things. 12th International Conference on Intelligent Environments (IE). London, United Kingdom 14 - 16 Sep 2016 IEEE. pp. 171-174 https://doi.org/10.1109/IE.2016.37
Using multi-agent systems to go beyond temporal patterns verification
Raimondi, F. 2016. Using multi-agent systems to go beyond temporal patterns verification. ACM SIGLOG News. 3 (2), pp. 69-77. https://doi.org/10.1145/2948896.2948905
Taking Arduino to the Internet of things: the ASIP programming model
Barbon, G., Margolis, M., Palumbo, F., Raimondi, F. and Weldin, N. 2016. Taking Arduino to the Internet of things: the ASIP programming model. Computer Communications. 89-90, pp. 128-140. https://doi.org/10.1016/j.comcom.2016.03.016
A computationally grounded, weighted doxastic logic
Chen, T., Primiero, G., Raimondi, F. and Rungta, N. 2016. A computationally grounded, weighted doxastic logic. Studia Logica. 104 (4), pp. 679-703. https://doi.org/10.1007/s11225-015-9621-4
Temporal planning for business process optimisation
Magazzeni, D., Mercorio, F., Barn, B., Clark, T., Raimondi, F. and Kulkarni, V. 2014. Temporal planning for business process optimisation. ICAPS 2014: 8th Scheduling and Planning Application woRKshop (SPARK 2014). Portsmouth, New Hampshire, USA 22 Jun 2014
Aviation safety: modeling and analyzing complex interactions between humans and automated systems
Rungta, N., Brat, G., Clancey, W., Linde, C., Raimondi, F., Seah, C. and Shafto, M. 2013. Aviation safety: modeling and analyzing complex interactions between humans and automated systems. ATACCS 2013. Naples, Italy 28 - 30 May 2013 Association for computing machinery. pp. 27-37 https://doi.org/10.1145/2494493.2494498
A synergistic and extensible framework for multi-agent system verification
Hunter, J., Raimondi, F., Rungta, N. and Stocker, R. 2013. A synergistic and extensible framework for multi-agent system verification. AAMAS 2013 :12th International Conference on Autonomous Agents and Multiagent Systems. Saint Paul, Minnesota, USA. 06 - 10 May 2013 Richland, SC International Foundation for Autonomous Agents and Multiagent Systems. pp. 869-876
Domain types: abstract-domain selection based on variable usage
Apel, S., Beyer, D., Friedberger, K., Raimondi, F. and von Rhein, A. 2013. Domain types: abstract-domain selection based on variable usage. Hardware and Software: Verification and Testing. 8244 (1), pp. 262-278. https://doi.org/10.1007/978-3-319-03077-7_18
Introducing Binary Decision Diagrams in the explicit-state verification of Java code
von Rhein, A., Apel, S. and Raimondi, F. 2011. Introducing Binary Decision Diagrams in the explicit-state verification of Java code. The Java Pathfinder Workshop (co-located with ASE 2011). Oread, Lawrence, Kansas 12 Nov 2011
Towards cyber-physical systems as services: the ASIP protocol
Bordoni, M., Bottone, M., Fields, B., Gorogiannis, N., Margolis, M., Primiero, G. and Raimondi, F. 2015. Towards cyber-physical systems as services: the ASIP protocol. 2015 IEEE/ACM 1st International Workshop on Software Engineering for Smart Cyber-Physical Systems (SEsCPS). Florence, Italy 17 - 17 May 2015 IEEE. pp. 52-55 https://doi.org/10.1109/SEsCPS.2015.18
Minimizing transitive trust threats in software management systems
Boender, J., Primiero, G. and Raimondi, F. 2015. Minimizing transitive trust threats in software management systems. 13th Annual Conference on Privacy, Security and Trust (PST 2015). Izmir, Turkey 21 - 23 Jul 2015 IEEE. pp. 191-198 https://doi.org/10.1109/PST.2015.7232973
Symbolic model-checking for resource-bounded ATL
Alechina, N., Logan, B., Nguyen, H., Raimondi, F. and Mostarda, L. 2015. Symbolic model-checking for resource-bounded ATL. 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015. Istanbul, Turkey 04 - 08 May 2015 International Foundation for Autonomous Agents and Multiagent Systems. pp. 1809-1810
Symbolic model checking for one-resource RB±ATL
Alechina, N., Logan, B., Nguyen, H. and Raimondi, F. 2015. Symbolic model checking for one-resource RB±ATL. Yang, Q. and Wooldridge, M. (ed.) 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). Buenos Aires, Argentina 25 - 31 Jul 2015 Buenos Aires, Argentina AAAI Press / International Joint Conferences on Artificial Intelligence. pp. 1069-1075
Software theory change for resilient near-complete specifications
Primiero, G. and Raimondi, F. 2015. Software theory change for resilient near-complete specifications. 2nd International Workshop on Computational Antifragility and Antifragile Engineering (ANTIFRAGILE 2015). London, UK 02 - 05 Jun 2015 Elsevier. https://doi.org/10.1016/j.procs.2015.05.091
On the role of value sensitive concerns in software engineering practice
Barn, B., Barn, R. and Raimondi, F. 2015. On the role of value sensitive concerns in software engineering practice. 37th International Conference on Software Engineering, ICSE 2015. Florence, Italy 16 - 24 May 2015 IEEE. pp. 497-500 https://doi.org/10.1109/ICSE.2015.182
A racket-based robot to teach first-year computer science
Androutsopoulos, K., Gorogiannis, N., Loomes, M., Margolis, M., Primiero, G., Raimondi, F., Varsani, P., Weldin, N. and Zivanovic, A. 2014. A racket-based robot to teach first-year computer science. 7 th European Lisp Symposium. IRCAM, Paris, France 05 - 06 May 2014 pp. 54-61
Model checking degrees of belief in a system of agents
Primiero, G., Raimondi, F. and Rungta, N. 2014. Model checking degrees of belief in a system of agents. AAMAS 2014: 13th International Conference on Autonomous Agents and Multiagent Systems. Paris, France 05 - 09 May 2014 International Foundation for Autonomous Agents and Multiagent Systems. pp. 133-140
Programming the MIRTO robot with neurons
Huyck, C., Primiero, G. and Raimondi, F. 2014. Programming the MIRTO robot with neurons. 5th Annual International Conference on Biologically Inspired Cognitive Architectures, BICA 2014. Cambridge, MA, USA 07 - 09 Nov 2014 Elsevier. https://doi.org/10.1016/j.procs.2014.11.087
A typed natural deduction calculus to reason about secure trust
Primiero, G. and Raimondi, F. 2014. A typed natural deduction calculus to reason about secure trust. 2014 Twelfth Annual Conference on Privacy, Security and Trust (PST). Toronto, Canada 23 - 24 Jul 2014 Institute of Electrical and Electronics Engineers (IEEE). pp. 379-382 https://doi.org/10.1109/PST.2014.6890963
Decidable model-checking for a resource logic with production of resources
Alechina, N., Logan, B., Nguyen, H. and Raimondi, F. 2014. Decidable model-checking for a resource logic with production of resources. Schaub, T., Friedrich, G. and O'Sullivan, B. (ed.) 21st European Conference on Artificial Intelligence (ECAI-2014). Prague, Czech Republic 18 - 22 Aug 2014 Prague, Czech Republic IOS Press. pp. 9-14 https://doi.org/10.3233/978-1-61499-419-0-9
Improving the model checking of strategies under partial observability and fairness constraints
Busard, S., Pecheur, C., Qu, H. and Raimondi, F. 2014. Improving the model checking of strategies under partial observability and fairness constraints. 16th International Conference on Formal Engineering Methods, ICFEM 2014. Luxembourg 03 - 05 Nov 2014 Springer. pp. 27-42 https://doi.org/10.1007/978-3-319-11737-9_3
Slrtool: a tool to support collaborative systematic literature reviews
Barn, B., Raimondi, F., Athiappan, L. and Clark, T. 2014. Slrtool: a tool to support collaborative systematic literature reviews. 16th International Conference on Enterprise Information Systems. Lisbon, Portugal 27 - 30 Apr 2014 SCITEPRESS - Science and Technology Publications. pp. 440-447 https://doi.org/10.5220/0004972204400447
Context-aware adaptive applications: fault patterns and their automated identification
Sama, M., Elbaum, S., Raimondi, F., Rosenblum, D. and Wang, Z. 2010. Context-aware adaptive applications: fault patterns and their automated identification. IEEE Transactions on Software Engineering. 36 (5), pp. 644-661. https://doi.org/10.1109/TSE.2010.35
Evaluation of collaborative filtering algorithms using a small dataset
Roda, F., Liberti, L. and Raimondi, F. 2011. Evaluation of collaborative filtering algorithms using a small dataset. WEBIST 2011. http://www.webist.org/WEBIST2011/
Reasoning about strategies under partial observability and fairness constraints
Busard, S., Pecheur, C., Qu, H. and Raimondi, F. 2013. Reasoning about strategies under partial observability and fairness constraints. 1st International Workshop on Strategic Reasoning. Rome, Italy 16 - 17 Mar 2013 Open Publishing Association. https://doi.org/10.4204/EPTCS.112.12
Implementing adaptation and reconfiguration strategies in heterogeneous WSN
Di Marco, A., Gallo, F., Gemikonakli, O., Mostarda, L. and Raimondi, F. 2013. Implementing adaptation and reconfiguration strategies in heterogeneous WSN. 27th IEEE International Conference on Advanced Information Networking and Applications (AINA-2013). Barcelona, Spain 25 - 28 Mar 2013 IEEE. pp. 477-483 https://doi.org/10.1109/AINA.2013.102
Application of verification techniques to security: model checking insider attacks
Kammueller, F., Probst, C. and Raimondi, F. 2012. Application of verification techniques to security: model checking insider attacks. 1st International Conference on Software and Emerging Technologies for Education, Culture, Entertainment, and Commerce (SETECEC 2012): New Directions in Multimedia Mobile Computing, Social Networks, Human-Computer Interaction and Communicability. Venice, Italy 28 - 29 Mar 2012 Blue Herons editions.
The secret santa problem.
Liberti, L. and Raimondi, F. 2008. The secret santa problem. Lecture Notes in Computer Science. 5034, pp. 271-279. https://doi.org/10.1007/978-3-540-68880-8_26
Algorithms for efficient symbolic detection of faults in context-aware applications.
Sama, M., Raimondi, F., Rosenblum, D. and Emmerich, W. 2008. Algorithms for efficient symbolic detection of faults in context-aware applications. in: Automated Software Engineering - Workshops, 2008. ASE Workshops 2008. 23rd IEEE/ACM International Conference. Institute of Electrical and Electronics Engineers. pp. 1-8
Service-level agreements for electronic services
Skene, J., Raimondi, F. and Emmerich, W. 2010. Service-level agreements for electronic services. IEEE Transactions on Software Engineering. 36 (2), pp. 288-304. https://doi.org/10.1109/TSE.2009.55
PDVer, a tool to verify PDDL planning domains.
Raimondi, F., Pecheur, C. and Brat, G. 2009. PDVer, a tool to verify PDDL planning domains. ICAPS'09 Workshop on Verification and Validation of Planning and Scheduling Systems. Thessaloniki, Greece 20 Sep 2009
The Anonymous subgraph problem.
Bettinelli, A., Liberti, L., Raimondi, F. and Savourey, D. 2009. The Anonymous subgraph problem. Cologne Twente Workshop 2009: 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Paris 02 - 04 Jun 2009 pp. 269-274
Combinatorial optimization based recommender systems.
Roda, F., Liberti, L. and Raimondi, F. 2009. Combinatorial optimization based recommender systems. Cologne Twente Workshop 2009: 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. Paris 02 - 04 Jun 2009 pp. 175-179
A model to design and verify context-aware adaptive service composition.
Cubo, J., Sama, M., Raimondi, F. and Rosenblum, D. 2009. A model to design and verify context-aware adaptive service composition. 6th IEEE International Conference on Services Computing (SCC 2009). Bangalore 21 - 25 Sep 2009
A formal analysis of requirements-based testing
Pecheur, C., Raimondi, F. and Brat, G. 2009. A formal analysis of requirements-based testing. in: Rothermel, G. and Dillon, L. (ed.) Proceedings of the Eighteenth International Symposium on Software Testing and Analysis Association for Computing Machinery (ACM). pp. 47-56
MCMAS: a model checker for the verification of multi-agent systems
Lomuscio, A., Qu, H. and Raimondi, F. 2009. MCMAS: a model checker for the verification of multi-agent systems. Lecture Notes in Computer Science. 5643, pp. 682-688. https://doi.org/10.1007/978-3-642-02658-4_55
Efficient online monitoring of web-service SLAs
Raimondi, F., Skene, J. and Emmerich, W. 2008. Efficient online monitoring of web-service SLAs. in: Harrold, J. and Murphy, G. (ed.) Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of Software Engineering Association for Computing Machinery (ACM). pp. 170-180