Graph reconstruction problem shown to be computationally complex
Graph determination problem from knowledge of its subgraphs
Computational ComplexityData Structures and Algorithms
Summary
This paper looks at a puzzle about graphs, which are networks of points connected by lines. It asks if there's a bigger connected graph that contains a specific number of smaller colored subgraphs and uses every edge shown in those subgraphs. The authors found that figuring this out is hard in a formal computational sense, especially when dealing with certain small graphs called paths. They also provide a way to solve some simpler cases more quickly using a step-by-step method. This helps understand the limits of what can be computed about graphs from partial information.
What this means in practice
- •For network system designers: Understand limitations on reconstructing network structures from partial subnetworks for accurate modeling and analysis.
- •For software engineers in security: Assess complexity boundaries for reconstructing communication graphs, useful in intrusion detection and monitoring scenarios.
A theory result. No direct application yet.
Authors
Coralie Zens, Dominique Barth, Dimitri Watel, Marc-Antoine Weisser
Abstract
In the context of graph reconstruction studies, this paper addresses the problem defined as follows: given a sample of vertex-coloured graphs, each associated with a number, does there exist a connected graph containing exactly the given number of induced subgraphs isomorphic to each graph in the sample, such that every edge of the solution graph is included in at least one of these subgraphs. This paper first shows that this problem is $Σ$______-complete. The associated optimisation problem is to determine the minimum number of vertices in a solution graph, if one exists. For instances consisting of two paths, we prove NP-completeness in general and give a polynomial-time dynamic programming algorithm when one path is monochromatic.