Graph determination problem from knowledge of its subgraphs

1. Introduction

• SGSC asks whether a connected graph on at most α vertices realizes each prescribed induced-subgraph count exactly while every edge belongs to at least one prescribed copy.Its optimization version seeks a solution graph of minimum order.Source: §1 · p. 1
• Molecular-structure reconstruction from spectral data motivates modeling local patterns as graphs with prescribed copy multiplicities and edge coverage.The paper presents this as a combinatorial abstraction inspired by structure-from-spectrum problems.Source: §1 · pp. 1–2
• Unlike reconstruction from a vertex-deleted deck, SGSC asks for existence; unlike Legitimate-Deck, it specifies multiplicities of graph isomorphism types rather than an explicit multiset.Translating Legitimate-Deck instances requires accounting for graph isomorphism, so the correspondence is not a direct polynomial-time reduction.Source: §1 · p. 2
• SGSC is ΣP_2-complete even with three colours; two-path instances are NP-hard, while a monochromatic path enables characterization and a polynomial-time minimum-order construction.The paper describes its tractable subclass as two-path instances where one path is monochromatic.Source: §1 · p. 2

2. Preliminaries

• A coloured graph assigns each vertex a colour, and isomorphism preserves both colours and adjacency; inclusion means isomorphism to an induced subgraph.Samples contain connected, pairwise non-isomorphic graphs and may be with or without inclusion.Source: §2 · p. 3
• A fingerprint records the required number of copies of each sample graph; it is unary when every component equals one.The paper allows zero entries in the formal problem definition to forbid a pattern.Source: §2 · pp. 3–4
• The example graphs share signature (2, 3, 1, 0) and discrepancy two from fingerprint (1, 3, 2, 0), yet only H is edge-covered.H′ has a curved edge not covered by the sample.Source: §2 · p. 4, Figure 2 · p. 4
• SGSC asks for a connected graph within the vertex bound that has zero discrepancy from the fingerprint and is edge-covered by the sample.Its associated optimization problem minimizes the order of a graph satisfying these conditions; fingerprint values are assumed polynomially bounded in the input sample size.Source: §2 · p. 4
• ΣP_2 consists of decision problems solvable by an NP machine with access to an NP oracle; completeness additionally requires polynomial-time reductions from every problem in the class.The preliminaries also note unique-solution SAT as a problem in this class.Source: §2 · p. 4

3. The complexity of SGSC

• SGSC is Σ_P^2-complete for instances involving at least three colours.Source: §3 · p. 5
• Reductions from Clique and its complement establish that SGSC is NP-hard and co-NP-hard, respectively.Source: §3 · p. 5
• For membership in Σ_P^2, the proof guesses a graph and uses an NP oracle to check exact induced-copy counts and edge coverage.Source: §3 · pp. 5–6
• The reduction to SGSC uses two coloured graphs, with fingerprint (1, 1), to encode the unique-clique-completion condition.Source: §3 · pp. 8–9
• Two-path instances remain NP-hard, even with a unary fingerprint; membership in NP has not been established.Source: §3 · p. 9
• When one of the two paths is monochromatic, the resulting instances can be solved in polynomial time.Source: §3 · p. 10

4. Polynomial-Time Solvability with One Monochromatic Path

• SGSC is solvable in polynomial time for the specified two-path instances with unary fingerprint and positive vertex bound.The two paths consist of a coloured path L1 and a monochromatic path L2 whose colour occurs in L1.Source: §4 · p. 11

4.1. Instances with inclusion or small vertex bound

• Inclusion cases are decided by scanning L1, while instances without inclusion and with α ≤ max{N1, N2} have no valid solution.If L1 is included in L2, no solution exists; if L2 is included in L1, L1 is a solution exactly when α ≥ N1 and the longest maximal c-subpath is unique and has N2 vertices.Source: §4.1 · p. 12

4.2. Structural Encoding of Solutions

• The structural encoding represents solutions through subsets of maximal c-subpaths of L1, with perfect subsets enforcing connectivity and excluding extra L2 occurrences or unnecessary subpaths.A solution's subpath set comprises maximal c-subpaths containing vertices shared by the L1 and L2 occurrences; the encoding also tracks the number and sizes of selected subpaths.Source: §4.2 · p. 13

4.3. Canonical Construction and Normalisation

• Algorithm A1 constructs a candidate graph from each perfect subset, and at least one optimal solution has this canonical form.The search can therefore minimize a specific function over perfect subsets; A1 constructs each graph in O(N1 · |λ|) time.Source: §4.3 · p. 13

4.3.1 Direct Properties of the Construction

• For a non-empty perfect subset λ, A1 returns a connected graph with N1 + |λ| − 1 + max{0, N2 − f(λ)} vertices.The c-coloured vertices induce one tree containing the selected subpaths and added vertices, while each unselected maximal c-subpath forms its own component.Source: §4.3.1 · p. 15
• When N2 ≥ f(λ), A1's graph contains a unique maximum c-coloured subpath with exactly N2 vertices.This property holds for instances in J and perfect subsets λ.Source: §4.3.1 · p. 17
• For an instance in J with set Λ and perfect subset λ of Λ satisfying N2 < f(λ), the graph H returned by A1 has a unique maximum colour-c subpath containing exactly N2 vertices.Source: §4.3.1 · p. 17

4.3.2 Additional Occurrences and Their Repair

• An extra induced L_1 copy using a constructed v_i requires |λ| = 2, λ’s subpaths to contain H_1’s ends, f(λ) = 3 < N_2, and another length-three subpath.These are the exceptional conditions identified for copies involving a vertex v_i.Source: §4.3.2 · pp. 19–20
• An extra L_1 copy using path a requires H_1’s ends in end subpaths, an attachment at an end of a selected subpath, and an unselected end subpath whose length gap is at most N_2 − f(λ).The selected subpath belongs to λ; the other end subpath does not.Source: §4.3.2 · pp. 20–21
• If A1’s graph has an additional L_1 copy, a perfect subset λ★ yields a smaller solution with |λ★| ≤ |λ| and f(λ) ≤ f(λ★) ≤ N_2.The replacement removes the obstruction while preserving a solution graph.Source: §4.3.2 · pp. 21–22

4.3.3 Normalising an Optimal Solution

• An optimal solution can be retained while obtaining a perfect subpath set, so the canonical construction captures the optimum.The section’s converse structural argument establishes this alongside the repair result.Source: §4.3.3 · p. 22
• Every solution’s subpath set satisfies Conditions a and b, and an optimal solution satisfying Condition c exists.These structural conditions support normalization to a perfect subpath set.Source: §4.3.3 · pp. 22–23
• Every instance in J has an optimal graph whose subpath set is perfect.The normalization argument establishes this property for an optimal solution, which underlies the optimization algorithm.Source: §4.3.3 · p. 25
• For a perfect subset λ minimizing q(λ) = |λ| − 1 + max{0, N2 − f(λ)}, Algorithm A1 returns an optimal graph of order N1 + q(λ).Here f(λ) is the total subpath length plus |λ| − 1.Source: §4.3.3 · p. 25

4.4. Optimising over Perfect Subsets

• The minimum-quantity perfect subset can be found in O(|Λ|^3 N2^2) time by combining a search for subsets of at most two subpaths with dynamic programming for larger subsets.The dynamic program runs in O(|Λ|·K·Σ) time for fixed cardinality K and total length Σ; optimal subsets satisfy Σ < 2N2.Source: §4.4 · pp. 26–27
• The two-path problem with one monochromatic path is solvable in O(N1^3 N2^2) time, for both decision and constructive versions.The algorithm computes an optimal graph, and the original instance is feasible exactly when its order is at most α.Source: §4.4 · p. 28

• SGSC is ΣP_2-complete for instances with three colours, two sampled graphs, and a unitary fingerprint.Source: §5 · p. 28
• For two-path samples with an arbitrary number of colours, SGSC is NP-hard, while instances with one monochromatic path admit a polynomial-time algorithm.Source: §5 · p. 28
• The boundary between polynomial-time and NP-complete instances remains unresolved, including whether nonrepeating monochromatic path blocks suffice for polynomial time.Source: §5 · p. 28
• Extending the polynomial-time approach to monochromatic trees or k-coloured paths, for fixed or unrestricted k, remains a direction for further work.Source: §5 · p. 28
• The variant of minimising a graph containing polynomially many copies of fixed small graphs lies in NP because occurrence testing and counting are polynomial-time.Source: §5 · p. 29
• The paper identifies parameterised study using |F|, the sum of fingerprint counts, and the largest sample-graph order as a further direction.Source: §5 · p. 29