Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Induced minor free graphs: isomorphism and clique-width
Belmonte R., Otachi Y., Schweitzer P.  Algorithmica 80 (1): 29-47, 2018. Type: Article
Date Reviewed: Apr 2 2019

A graph H is said to be an induced minor of another graph G “if a graph isomorphic to H can be [constructed] from G by a sequence of vertex deletions and edge contractions.”

The main theme of the paper is the complexity of graph isomorphism on graphs “characterized by one forbidden induced minor.” In the initial result, for a complete graph H, graph isomorphism for H-induced-minor-free graphs (that is, “no induced minor of G is isomorphic to H”) can be solved in polynomial time. The authors also prove a necessary and sufficient condition for an H-induced-minor-free graph to have bounded clique-width: the order of H is less than or equal to four. If H is an induced subgraph of P4, then “graph isomorphism for H-induced-minor-free graphs can be solved in linear time.”

The core part of the study deals with “graph classes characterized by a forbidden induced minor H that has at most five vertices.” A GI-complete problem is “polynomial-time tractable or polynomial-time equivalent to the general problem.”

The first main theorem of the paper establishes that the graph isomorphism problem for (K3K1)-induced-minor-free graphs is GI-complete. It is also proves that such graphs do not have bounded clique-width. Following this result, the authors also prove that “the graph isomorphism problem can be solved in polynomial time on gem-induced-minor-free graphs,” and for an induced subgraph H of the gem graph, “the H-induced-minor-free graphs have bounded clique-width.”

The third main result states that the graph isomorphism problem for co-(P3∪2K1)-induced-minor-free graphs can be solved in polynomial time. For an induced subgraph H of co-(P3∪2K1), “the H-induced-minor-free graphs have bounded clique-width.” Furthermore, for a non-complete graph H of order at most five, “the graph isomorphism for H-induced-minor-free graphs is polynomial-time solvable if H is an induced subgraph of co-(P3∪2K1) or the gem; otherwise, it is GI-complete.”

In the last part of the paper, the authors show that for a non-complete graph H with at least six vertices, “graph isomorphism for the H-induced-minor-free graphs is GI-complete” and “H-induced-minor-free graphs have unbounded clique-width.”

The content is beautifully presented and the results and their proofs include nice structural analyses of the graphs concerned. The intended audience is the graph theory research community, including research scholars, professors, and postgraduate students. I would recommend the paper, as the content is innovative and interesting. It is very good work as well.

Reviewer:  Sudev Naduvath Review #: CR146507 (1906-0241)
Bookmark and Share
 
Discrete Mathematics (G.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Discrete Mathematics": Date
 Essential discrete mathematics for computer science
Lewis H., Zax R.,  PRINCETON UNIVERSITY PRESS, Princeton, NJ, 2019. 388 pp. Type: Book (978-0-691179-29-2)
Jul 18 2022
Discrete mathematics and graph theory: a concise study companion and guide
Erciyes K.,  Springer International Publishing, New York, NY, 2021. 352 pp. Type: Book (978-3-030611-14-9)
Jul 12 2022
A modified artificial bee colony approach for the 0-1 knapsack problem
Cao J., Yin B., Lu X., Kang Y., Chen X.  Applied Intelligence 48(6): 1582-1595, 2018. Type: Article
Aug 22 2018
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy