{"id":1677,"date":"2025-10-17T07:58:15","date_gmt":"2025-10-17T07:58:15","guid":{"rendered":"https:\/\/prg.inf.unibe.ch\/?page_id=1677"},"modified":"2025-10-17T07:58:15","modified_gmt":"2025-10-17T07:58:15","slug":"thesis-tangle-based-heuristics-for-subgraph-matching-in-large-networks","status":"publish","type":"page","link":"https:\/\/prg.inf.unibe.ch\/index.php\/education\/thesis-tangle-based-heuristics-for-subgraph-matching-in-large-networks\/","title":{"rendered":"thesis-Tangle-Based Heuristics for Subgraph Matching in Large Networks"},"content":{"rendered":"\n
<\/div>\n\n\n\n
<\/div>
\n
<\/div>\n

Tangle-Based Heuristics for Subgraph Matching in Large Networks<\/h1>\n\n\n\n

Co-Supervised by:<\/strong> Kalvin Dobler<\/p>\n\n\n\n

If you are interested in this topic or have further questions, do not hesitate to contact kalvin.dobler@unibe.ch<\/a>.<\/p>\n\n\n\n

Background \/ Context<\/strong><\/p>\n\n\n\n

Traditional subgraph isomorphism methods (e.g., VF2, Ullmann’s) suffer in large networks due to global combinatorial explosion. Many real-world networks (biological, social, infrastructure) exhibit modularity and local structure, which can be exploited using tangle theory.<\/p>\n\n\n\n

Tangle theory, from graph minor theory (developed by Robertson and Seymour), offers a way to capture “highly connected regions” of a graph without explicitly identifying the structure \u2014 focusing instead on consistent orientations of low-order separations. This provides a way to reason about complex graph connectivity abstractly.<\/p>\n\n\n\n

The idea is to implement a framework for subgraph matching in large and complex networks by leveraging tangle-based decomposition. The core idea is to restrict matching operations to highly connected regions identified via tangles in order to improve both efficiency and interpretability.<\/p>\n\n\n\n

Research Question(s) \/ Goals<\/strong><\/p>\n\n\n\n