Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Hitting forbidden subgraphs in graphs of bounded treewidth
Cygan M., Marx D., Pilipczuk M., Pilipczuk M. Information and Computation256 (C):62-82,2017.Type:Article
Date Reviewed: Jul 23 2018

For a given linear transform A over a given vector space Q starting at point x, the orbit of x under A is an infinite sequence (x, Ax, A2x, ..., Ajx). A natural concern in the context of optimality search is whether (and when) the orbit of x will hit a particular target set V. In this paper, the authors study the complexity of such a problem where V is a subgraph H of a given graph G.

This is a very formal, mathematical paper. The authors explore the H-subgraph hitting problem and its motivation, and then describe the techniques they used to arrive at their results. After several theorems, lemmas, and claims (along with their proofs), the paper presents a general algorithm for H-subgraph hitting and a set of claims regarding the availability of a recursive search procedure of a finite graph.

Using a lemma based on this claim, the authors formulate a dynamic programming algorithm using leaf node, introduce node, forget node, and join node. They conclude that the treewidth parameterization of H-subgraph hitting is highly involved, although the described algorithm can be used in certain cases.

I think the paper with its 18 references is of interest to researchers in this particular area. It is a difficult paper to read.

Reviewer:  Anoop Malaviya Review #: CR146165 (1811-0579)
Bookmark and Share
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Graph Algorithms (G.2.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Nonnumerical Algorithms And Problems": Date
Improving the performance guarantee for approximate graph coloring
Wigderson A. Journal of the ACM 30(4): 729-735, 1983. Type: Article
Feb 1 1985
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
Demel J., Demlová M., Koubek V. Theoretical Computer Science 36(2-3): 203-216, 1985. Type: Article
Jan 1 1986
Complexity of the word problem for commutative semigroups of fixed dimension
Huynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy