1、An exact algorithm for Intervalizing Colored GraphsHans L.BodlaenderJohan M.M.van RooijContents Intervalizing Colored Graphs:problem and relation with path decompositions Simple O*(3n)algorithm For fixed number of colors:variant with isomorphism test Sketch of time analysis(subexponential time)Concl
2、usionsIntervalizing Colored Graphs Given:undirected graph G=(V,E),vertex coloring c:V 1,k Question:is G a subgraph of a properly colored interval graph?Motivation originally from computational biology NP-complete when k=4(or larger)(B,van Antwerpen-de Fluiter,1996)even for caterpillars(Alvarez et al
3、.2001)Polynomial when k=3(B,vA-dF)or k=2(trivial)Result today Easy O*(2n)time algorithm Held-Karp-style dynamic programming algorithm For fixed k,exact algorithm with subexponential time Held-Karp style DP,augmented with isomorphism test For all e0:)2(1log*nnOePath decomposition A path decomposition
4、 is a sequence(X1,X2,Xr)of subsets of vertices(called bags)such that If i j 1:Xi=Xi-1 v for some v(introduce node),or Xi=Xi-1 v for some v(forget node).Simple lemma:there is a properly colored nice path decomposition,if and only if there is a properly colored path decomposition Helps for the DP algo
5、rithmFine pairs Call a pair of vertex sets(Y,Z)fine if Z Y There exists a properly colored nice path decomposition of GY such that the last bag has vertex set Z N(Y Z)YZYSimple O*(3n)algorithm(2)Tabulate in order of increasing value of 2|Y|Z|all fine pairs(Y,Z)2|Y|Z|equals number of bags If we have
6、a fine pair(V,*)then say“yes”If no such pair is computed when algorithm ends,say“no”Recursive formulation(Y,Z)is fine,if one of the following holds:|Y|=|Z|=1 There is a fine pair(Y,Z v)for some v Y such that N(v)Y(Y,Z)results from a forget node,forgetting v There is a fine pair(Y v,Z v)for some v su
7、ch that v has a color different from all vertices in Z v(Y,Z)results from an introduce node,introducing vIntroduce node For each pair(Y,Z),tabulate all ways of extending with one introduce node:Take a pair(Y v,Z v)for all vertices v with v V-Y v has a color different from all vertices in ZZYZ vForge
8、t node For each pair(Y,Z),tabulate all ways of extending with one forget node:Take a pair(Y,Z v)for all vertices v with v has no neighbor in V-YZYZ vImprovement for unbounded number of colors A changed version only tabulates (Y,Z)such that Z=v Y|v has a neighbor in V-Y Leads to O*(2n)algorithm Simpl
9、e correctness proof omittedFixed number of colors Suppose the number of colors k is fixed.Each set Z has at most k vertices,so the O*(3n)algorithm takes O*(nk 2n)time Improvement with isomorphism test:Say(Y,Z)and(Y,Z)are isomorphic if there is a graph isomorphism from GY to GY that preserves colors
10、with f(z)=z for all z Z Note:both have the same Z If(Y,Z)and(Y,Z)are isomorphic,then either both(Y,Z)and(Y,Z)are fine or neither of themChanged algorithm Use the original algorithm,with this change:When we want to tabulate a fine pair(Y,Z),first test if there is not already a tabulated pair(Y,Z)that
11、 is isomorphic Graph isomorphism is in XP,parameterized by treewidth(and hence pathwidth)(B,1990)Algorithm is correct(proof omitted),and takes time O*(#equivalence classes of isomorphism)Counting equivalences sketch:Components Consider vertex set Z(nk possibilities)Define Components:connected compon
12、ents of GV-Z For each fine pair(Y,Z),and component W,either W Y,or W Y=.Equivalence class of(Y,Z)is determined by telling for each component what option is takenLarge components Components of at least log1-d n vertices:At most n/(log n)1-d such component,i.e.,at mostpossibilities(subexponential)nnd1
13、log2Small components Components of at most log1-d n vertices:Define an equivalence relation on small components:W W,if there is a color preserving isomorphism of GW Z to GW Z For each equivalence class on small components,we look at:how many components in the class are subset of Y Here at most:nnumb
14、er of equivalence classes possibilitiesSmall components(2)Counting:at most 23kl kl equivalence classes of components with l vertices For small(l log1-d n)components at most possibilities(again subexponential)nnkkndd1log1log32Wrapup For each e0,there is a d,such that our analysis gives running time at most)2(1log*nnOeConclusions Simple addition of isomorphism test to Held-Karp style algorithm gives subexponential time algorithm“Curious”result Can the analysis or the algorithm be improved to O(2n/log n)?Are there other applications of the technique?
