Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs

Details Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs

2011-11-04

arxiv.org/abs/1111.1109v1

Computer Science

Data Structures and Algorithms

Scientific paper

We generalize the structure theorem of Robertson and Seymour for graphs excluding a fixed graph $H$ as a minor to graphs excluding $H$ as a topological subgraph. We prove that for a fixed $H$, every graph excluding $H$ as a topological subgraph has a tree decomposition where each part is either "almost embeddable" to a fixed surface or has bounded degree with the exception of a bounded number of vertices. Furthermore, we prove that such a decomposition is computable by an algorithm that is fixed-parameter tractable with parameter $|H|$. We present two algorithmic applications of our structure theorem. To illustrate the mechanics of a "typical" application of the structure theorem, we show that on graphs excluding $H$ as a topological subgraph, Partial Dominating Set (find $k$ vertices whose closed neighborhood has maximum size) can be solved in time $f(H,k)\cdot n^{O(1)}$ time. More significantly, we show that on graphs excluding $H$ as a topological subgraph, Graph Isomorphism can be solved in time $n^{f(H)}$. This result unifies and generalizes two previously known important polynomial-time solvable cases of Graph Isomorphism: bounded-degree graphs and $H$-minor free graphs. The proof of this result needs a generalization of our structure theorem to the context of invariant treelike decomposition.

Affiliated with

Also associated with

No associations

Rating

Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-100948