Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
Pith reviewed 2026-05-16 05:46 UTC · model grok-4.3
The pith
The maximum common vertex subgraph without isolated vertices is NP-hard but admits an FPT algorithm parameterized by the size h.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We show that the Maximum Common Vertex Subgraph problem without isolated vertices is NP-hard and fixed-parameter tractable parameterized by h. We obtain a full dichotomy of the parameterized complexity with respect to the vertex cover number, maximum degree, treedepth, pathwidth, and treewidth of one or both input graphs, for both individual parameters and their combinations.
What carries the argument
The target size h as the primary parameter for FPT membership, combined with structural parameters of the input graphs to obtain hardness or tractability results via reductions and kernelization techniques.
Load-bearing premise
The two input graphs are undirected and simple, and the common subgraph is a graph whose vertices and edges are subsets of both inputs with the no-isolated-vertex condition.
What would settle it
A concrete pair of graphs where no algorithm running in f(h) * n^c time solves the problem for some function f would falsify the FPT claim when parameterized by h.
read the original abstract
In this paper, we study the Maximum Common Vertex Subgraph problem: Given two input graphs $G_1,G_2$ and a non-negative integer $h$, is there a common subgraph $H$ on at least $h$ vertices such that there is no isolated vertex in $H$. In other words, each connected component of $H$ has at least $2$ vertices. This problem naturally arises in graph theory along with other variants of the well-studied Maximum Common Subgraph problem and also has applications in computational social choice. We show that this problem is NP-hard and provide an FPT algorithm when parameterized by $h$. Next, we conduct a study of the problem on common structural parameters like vertex cover number, maximum degree, treedepth, pathwidth and treewidth of one or both input graphs. We derive a complete dichotomy of parameterized results for our problem with respect to individual parameterizations as well as combinations of parameterizations from the above structural parameters. This provides us with a deep insight into the complexity theoretic and parameterized landscape of this problem.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Maximum Common Vertex Subgraph problem without isolated vertices: given undirected simple graphs G1 and G2 and integer h, decide if there is a common subgraph H on at least h vertices with no isolated vertices (every component of H has size at least 2). It proves NP-hardness in general, gives an FPT algorithm parameterized by h, and derives a complete dichotomy of FPT versus W[1]-hardness results for individual and combined parameterizations by vertex cover number, maximum degree, treedepth, pathwidth, and treewidth of one or both input graphs.
Significance. If the results hold, the manuscript delivers a thorough parameterized complexity landscape for this natural variant of maximum common subgraph, which arises in graph theory and computational social choice. The complete dichotomy is a clear strength, as it precisely identifies tractable cases under standard structural parameters and supplies an FPT algorithm by h together with matching hardness results; this level of classification is useful for algorithm design and for understanding the effect of the no-isolated-vertex restriction.
minor comments (2)
- [Abstract and §1] Abstract and §1: the precise definition of a 'common subgraph' (induced versus non-induced) is left implicit. Explicitly state whether H must preserve all edges between the chosen vertices or only some, as this affects both the problem statement and the reductions.
- [§3] §3 (FPT algorithm): the running time of the algorithm parameterized by h should be stated explicitly (e.g., 2^{O(h)} n^{O(1)} or similar) rather than only asserting FPT membership.
Simulated Author's Rebuttal
We thank the referee for the positive summary, recognition of the complete dichotomy as a strength, and recommendation for minor revision. The report accurately reflects the NP-hardness, FPT algorithm parameterized by h, and the full FPT/W[1]-hardness classification under the listed structural parameters for the no-isolated-vertices variant of Maximum Common Vertex Subgraph.
Circularity Check
No significant circularity detected in derivation chain
full rationale
The paper establishes NP-hardness through explicit reductions from known hard problems, provides an FPT algorithm parameterized by h via standard techniques such as bounded search trees or dynamic programming on the parameter, and derives a complete dichotomy for structural parameters (vertex cover, maximum degree, treedepth, pathwidth, treewidth) via case analysis and kernelization. None of these steps reduce by construction to the target quantities themselves; the results rest on independent graph-theoretic constructions and external complexity assumptions rather than self-definitional mappings, fitted inputs renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained and externally verifiable.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard definitions of NP-hardness, FPT, W[1]-hardness, and structural parameters (vertex cover, treewidth, etc.) from parameterized complexity theory
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.