Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
By: Tesshu Hanaka , Yuto Okada , Yota Otachi and more
We study the parameterized complexity of the problems of finding a maximum common (induced) subgraph of two given graphs. Since these problems generalize several NP-complete problems, they are intractable even when parameterized by strongly restricted structural parameters. Our contribution in this paper is to sharply complement the hardness of the problems by showing fixed-parameter tractable cases: both induced and non-induced problems parameterized by max-leaf number and by neighborhood diversity, and the induced problem parameterized by twin cover number. These results almost completely determine the complexity of the problems with respect to well-studied structural parameters. Also, the result on the twin cover number presents a rather rare example where the induced and non-induced cases have different complexity.
Similar Papers
Triangle-Covered Graphs: Algorithms, Complexity, and Structure
Data Structures and Algorithms
Makes sure every part of a network has a connection.
Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\ell)$-Sparse Subgraphs
Data Structures and Algorithms
Finds best connections in complex networks faster.
Counting large patterns in degenerate graphs
Data Structures and Algorithms
Finds patterns in graphs faster, even for big patterns.