arXiv preprint ·
Graph determination problem from knowledge of its subgraphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
Query Complexity of Densest Sub(hyper)graph Problems
Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
Learning, Compression, and Meta-Complexity
Hitting Minors: Stronger Lower Bounds
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.