Papers for

software engineers in security

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Graph reconstruction problem shown to be computationally complex

Graph determination problem from knowledge of its subgraphs

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.

Mon 12 OctComputational ComplexityData Structures and Algorithms

The gist

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.

Open → 2610.16497v1