Cleaning Interval Graphs

Details Cleaning Interval Graphs Cleaning Interval Graphs

2010-03-05

arxiv.org/abs/1003.1260v1

Computer Science

Data Structures and Algorithms

40 pages, 7 eps figures

Scientific paper

We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-parameter tractability of the problem with non-standard parameterization, where the parameter is the difference |V(G)|-|V(H)|, with G and H being the larger and the smaller input graph, respectively. Intuitively, we can interpret this problem as "cleaning" the graph G, regarded as a pattern containing extra vertices indicating errors, in order to obtain the graph H representing the original pattern. We also prove W[1]-hardness for the standard parameterization where the parameter is |V(H)|.

Affiliated with

Also associated with

No associations

Rating

Cleaning Interval Graphs 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 Cleaning Interval Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cleaning Interval Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-687678