e-dokumen.com

4Christian Komusiewicz, Johannes Uhlmannsearch tree strategy. In Section 5, we present one easy and two more intricate datareduction rules specific to MFCT. Based on these rules, in Section 6 we can showthat MFCT admits a problem kernel with O(k3 ) vertices. Finally, in Section 7 wepresent an O(3.68k )-size search tree for MFCT.2 PreliminariesThroughout this work, we use the following notation and definitions. For anundirected graph G (V, E ), we use V (G) and E (G) to denote its vertex andedge set, respectively. The open neighborhood NG (v ) of a vertex v V is theset of vertices that are adjacent to v in G (V, E ). Furthermore, let NG [v ] : NG (v ) {v} denote theset of vertices V 0 V ,S closed neighborhood of v . For a Swe define NG (V 0 ) : v V 0 NG (v ) \ V 0 and NG [V 0 ] : v V 0 NG [v ]. The degreeof a vertex v , denoted by degG (v ), is the cardinality of NG (v ). For a set of vertices V 0 V , the induced subgraph G[V 0 ] is the graph over the vertex set V 0 withedge set {{v, w} E v, w V 0 }. For V 0 V we use G V 0 as abbreviationfor G[V \ V 0 ], and for a vertex v V let G v denote G {v}. For two sets Xand Y with X Y , let EX,Y denote the set {{x, y} x X y Y }. As anabbreviation for E{x},Y we write Ex,Y .For two sets E and F , define E F : (E \ F ) (F \ E ) (the symmetric difference ). Further, for a bipartite graph G (Vc , Vt , E ) and a set F EVc ,Vt define G F : (Vc , Vt , E F ). With this notation, the definition of Minimum-FlipConsensus Tree (MFCT) reads as follows.Given a bipartite graph G (Vc , Vt , E ) and an integer k 0, does thereexist S EVc ,Vt with S k such that G S is M -free?Herein, S is called a solution. We call a solution optimal if it has minimum cardinality among all solutions. The elements of S are called edge modifications. We saythat an edge modification e involves a vertex v if v e. Furthermore, a vertex v iscalled affected if S contains an edge modification involving v . Sometimes we referto a vertex v Vc as c-vertex, and to a vertex v Vt as t-vertex.A graph property Π is called hereditary if it is closed under vertex deletion.That is, if a graph G fulfills a hereditary graph property Π , then all inducedsubgraphs of G also fulfill Π . All graph properties that can be described by a(not necessarily finite) set of forbidden induced subgraphs (such as M -freeness forexample) are hereditary.For our data reduction we use a structure called critical independent set.Definition 1 Given an undirected graph G (V, E ), a set I V is called a criticalindependent set if NG (v ) NG (w) for any two vertices v, w I and I is maximalwith respect to this property.Note that NG (v ) NG (w) directly implies that I is an independent set. All criticalindependent sets of a graph can be found in linear time [26]. Given a graph G (V, E ) and the collection I {I1 , I2 , . . . , Iq }, q n, of its critical independent sets,the critical independent set graph of G is the undirected graph (I, E ) with {Ii , Ij } Eif and only if u Ii , v Ij : {u, v} E . That is, the vertices of the criticalindependent set graph represent the critical independent sets and two vertices areadjacent if and only if the corresponding critical independent sets together form

A Cubic-Vertex Kernel for Flip Consensus Tree5a biclique. The critical independent set graph is defined in analogy to the criticalclique graph which plays a decisive role in a kernelization of Cluster Editing [22].A bipartite graph G (X, Y, E ) is called a chain graph if the neighborhoods ofthe vertices in X form a chain [36]. That is, there is an ordering of the vertices in X ,say x1 , x2 , . . . , x X , such that NG (x1 ) NG (x2 ) . . . NG (x X ). It is easy to seethat the neighborhoods of Y also form a chain if G is a chain graph. Moreover,a bipartite graph is a chain graph if and only if it is 2K2 -free [36] (a 2K2 is thegraph that consists of two independent edges). Since every M -graph contains aninduced 2K2 , the set of chain graphs is contained in the class of M -free graphs.One of our data reduction rules is based on identifying and reducing the size ofsubgraphs of the input graphs that are chain graphs and additionally have a specialneighborhood structure.We use the following notation concerning rooted trees. A vertex of a tree iscalled node. For a rooted tree T let L(T ) denote the leaves of T (that is, the nodesof degree one). The nodes in V (T ) \ L(T ) are denoted as inner nodes. The root of Tis denoted by r(T ). Moreover, for a node v V (T ), the maximal subtree rootedat v is denoted by Tv . We refer to a child of a node v as leaf child of v if it is a leaf;otherwise, it is called non-leaf child of v . We speak of the leaves (inner nodes) of aforest to refer to the union of the leaves (inner nodes) of the trees of the forest.Induced M -graphs and M -freeness. Recall that a bipartite graph G (Vc , Vt , E ) iscalled M -free if it does not contain an induced M -graph. An induced M -graphis denoted by a 5-tuple (tl , cl , tm , cr , tr ), where cl , cr Vc and tl , tm , tr Vt . Twoc-vertices cl and cr are in conflict if there exists an induced M -graph containingboth cl and cr . Clearly, for an induced M -graph (tl , cl , tm , cr , tr ) we have tl NG (cl ) \ NG (cr ), tm NG (cl ) NG (cr ) and tr NG (cr ) \ NG (cl ). Thus, twovertices cl , cr Vc are in conflict if and only if(NG (cl ) \ NG (cr ) 6 ) (NG (cl ) NG (cr ) 6 ) (NG (cr ) \ NG (cl ) 6 ).If cl , cr Vc are in conflict, we write cl cr . In summary, for a bipartite graph G (Vc , Vt , E ), the following statements are equivalent:– G is M -free,– no two c-vertices are in conflict, and– for each pair of c-vertices cl and cr , it holds that N (cl ) N (cr ) or N (cl ) N (cr ) or N (cr ) N (cl ).M -free graphs and rooted phylogenetic trees are closely related. Given a connected and M -free graph G (Vc , Vt , E ), one can construct a rooted tree T withnode set Vt Vc and with L(T ) Vt such that ti Vt is a descendant of cj Vc ifand only if ti NG (cj ), see [9, 25, 33] for details. An example is given in Figure 2.Parameterized algorithmics. Parameterized algorithmics [13, 17, 31] aims at a mul-tivariate complexity analysis of problems. This is done by studying relevant problem parameters and their influence on the computational complexity. The decisive question is whether a given parameterized problem is fixed-parameter tractable(FPT) with respect to the parameter k. In other words, we ask for the existenceof a solving algorithm with running time f (k) · poly(n) for some computable function f . A core tool in the development of parameterized algorithms that has been

6Christian Komusiewicz, Johannes Uhlmannc1c3c2t1c1t2c3t3c4t4c2t5t1c4t2t3t4t5Fig. 2 An M -free graph G and the corresponding tree. In a connected M -free graph thereexists a “universal” c-vertex, that is, a vertex adjacent to all t-vertices. In this example, c1is a universal vertex. This universal vertex is the root of the corresponding tree. Thus, onecan build a tree by applying the above argument recursively for the connected components ofG c1 .recognized as one of the most important contribution of parameterized algorithmics to practical computing [6, 14, 24, 27, 31] is polynomial-time preprocessingby data reduction rules, often yielding a problem kernel. Herein, the goal is, givenany problem instance G with parameter k, to transform it in polynomial time intoa new instance G0 with parameter k0 such that the size of G0 is bounded fromabove by some function only depending on k, k0 k, and (G, k) is a yes-instanceif and only if (G0 , k0 ) is a yes-instance. We call a data reduction rule correct if thenew instance after an application of this rule is a yes-instance if and only if theoriginal instance is a yes-instance. An instance is called reduced with respect to aset of data reduction rules if each of the data reduction rules has been exhaustivelyapplied.3 A Universal Rule for Critical Independent SetsIn this section, we describe a polynomial-time data reduction rule that appliesto parameterized graph modification problems for a family of hereditary graphproperties. It is based on the modular decomposition of a graph and has beenapplied to Bicluster Editing [34]. We use this reduction rule for obtaining akernel for MFCT, but we believe that it can be useful for other graph modificationproblems as well. To this end, we show that this reduction rule can be applied toa wide range of Π-Edge Modification problems, including MFCT.The basic idea of the data reduction is to show that, for some graph properties,vertices that belong to the same critical independent set are subject to the “same”edge modifications. Therefore, large critical independent sets can be reduced. First,we give a description of these graph properties.Let Π be a hereditary graph property. We call Π critical independent set preserving (cisp ) whenever for all forbidden induced subgraphs F of Π , there are no twovertices u, v V (F ) that belong to the same critical independent set in F (thatis, all critical independent sets of F have size one). These forbidden subgraphsinclude for example all paths of length at least four and cycles of length 6 4. Notethat formally M -freeness is not a graph property because it is not invariant undergraph isomorphism: An M -graph has its first vertex in Vt . Therefore, exchanging Vtand Vc may transform an M -free graph into a graph that contains an M -graph asinduced subgraph and vice versa. Nevertheless, all vertices in an induced M -graphhave different neighborhoods. Therefore, the following lemmas and reduction rulealso apply directly to MFCT.

A Cubic-Vertex Kernel for Flip Consensus Tree7First, we show that cisp graph properties are closed under a certain vertexaddition operation.Lemma 1 Let G (V, E ) be a graph fulfilling a cisp graph property Π. Let G0 be thegraph that results by adding to G a new vertex x 6 V and making it adjacent to NG (v )for an arbitrary vertex v V . Then, G0 also fulfills Π.Proof Let G0 be the graph that is obtained by adding x to G and inserting all edgesbetween x and NG (v ) for some v V . We prove the lemma by showing that G0does not contain a forbidden induced subgraph.First, since G has the graph property Π , there is no forbidden induced subgraph G0 [S ] such that x S and v 6 S . Otherwise, the vertex set {v} (S \ {x})would induce a forbidden subgraph in G, contradicting the assumption that G hasproperty Π . Second, since v and x are part of a critical independent set and Π iscisp, there is no forbidden induced subgraph that contains both v and x. Therefore, G0 has property Π . utUsing Lemma 1, we can show that for graph modification problems for cispgraph properties there is an optimal solution that “treats” the vertices of anycritical independent set equally. This type of solution is formally defined as follows.Definition 2 A solution S for an instance (G, k) of Π-Edge Modification is calledregular if every critical independent set of G is contained in a critical independentset of G S .In other words, if S is regular then two vertices that have an identical open neighborhood in the input graph G also have an identical open neighborhood in G S .Lemma 2 Let Π be a cisp graph property and let G (V, E ) denote an undirectedgraph. Moreover, let S denote a solution for Π-Edge Modification on G and let Xdenote the set of vertices affected by S. Then, there exists a solution S such that– S S ,– S is regular,– X X, where X denotes the set of vertices affected by S .Proof Assume that there exists a critical independent set I of G that is not contained in a critical independent set in G S . We show that, by a local modification,one can find a graph G0 (V, E 0 ) fulfilling Π such that1. the number of edge modifications to transform G into G0 is at most the numberof edge modifications to transform G into G S , that is, E E 0 S ,2. I is contained in a critical independent set in G0 ,3. for each critical independent set I of G the number of critical independentsets of G0 intersecting with I is at most the number of critical independentsets of G S intersecting with I , and4. the set of affected vertices in G0 is a subset of X .By Condition 3, this local modification step can be applied iteratively until thesolution is regular. Moreover, by Condition 4 the set of affected vertices in theresulting graph is a subset of X .

8Christian Komusiewicz, Johannes UhlmannFirst, we formally specify the modification. Then, we show that the above conditions are fulfilled. Let I1 , I2 , . . . , I denote the critical independent sets in G Swith Ii I 6 , 1 i . Observe that 1. For a vertex w I let Sw denote the set of edge modifications from S involving w and vertices in V \ I , thatis, Sw : {{w, x} S x V \ I}. Let v I such that Sv is minimal and assumewithout loss of generality that v I1 . Build a graph G0 as follows from G S . First,remove all vertices in I \ {v} from G S . Then, add the vertices in I \ {v} step-bystep making each vertex adjacent to the vertices in the current open neighborhoodof v . Let S 0 : E E 0 and note that G0 G S 0 .By Lemma 1, G0 fulfills Π . To prove Condition 1, we show that S 0 S .Note that in the construction above we “change” only edges incident with thevertices in I and, hence, G0 [V \ I ] is identical to G S [V \ I ]. Moreover, since eachvertex w I \ I1 gets the same closed neighborhood as v (more specifically, thevertices in NG S (v ) \ I ), we have to spend at most Sv edge modifications forevery w I \ {v} (instead of at least Sw ). Since Sv Sw by the choice of v , itfollows that S 0 S .Condition 2 follows directly from the fact that by construction all vertices in Ihave the same open neighborhood in G0 (namely, NG S (v ) \ I ).Next, we show that Condition 3 is fulfilled. To this end, note that deletinga vertex does not increase the number of critical independent sets of a graph.Moreover, observe that two nonadjacent vertices with an identical neighborhoodhave an identical neighborhood after adding a vertex and making it adjacent tothe neighbors of an existing vertex. Hence, for each critical independent set I of G the number of critical independent sets of G intersecting with I is at mostthe number of critical independent sets of G0 intersecting with I .Clearly, by construction a vertex w not affected by S is not affected by S 0implying Condition 4. utNote that since the modification operations in the proof of Lemma 2 can be performed in polynomial time, we can compute a regular solution from a given (arbitrary) solution in polynomial time.Protti et al. [34] devised the following data reduction rule for Bicluster Editing. With Lemma 2 at hand, we can show that this rule is correct for all cisp graphproperties.Rule 1 Let I V be a critical independent set. If I k 1, then delete I (k 1)arbitrary vertices from I.Lemma 3 Rule 1 is correct and can be exhaustively applied in O( V E ) time.Proof By Lemma 2, we know that if we modify an edge incident with a vertex ina critical independent set I , then we must perform the same edge modification toany other vertex in I . That is, as long as I k, a solution of size at most k doesnot modify any edge incident with a vertex in I . Protti et al. [34] have shown thatRule 1 can be exhaustively applied in O( V E ) time. utWe can apply Rule 1 for MFCT since the graph property of being M -freeis critical independent set preserving: all vertices in an induced M -graph havedifferent neighborhoods. This general data reduction rule also applies to the Completion and Deletion version of a Π-Edge Modification problem for a cisp

A Cubic-Vertex Kernel for Flip Consensus Tree9graph property Π . Examples for graph modification problems to which this rulecan be applied are Chain Deletion and Co-trivially Perfect Deletion.1Bessy et al. [2] independently obtained a similar result. They considered graphproperties that are closed under “true twin addition”. More specifically, a graphproperty Π is closed under true twin addition if for any graph G fulfilling Π addinga vertex and making it adjacent to each vertex in N [v ] for some vertex v V (G),yields a graph that also fulfills Π . This true twin addition operation is similar tothe vertex addition operation applied in Lemma 1. The difference is that in thecase of “true twin addition” the new vertex is made adjacent to all vertices in theclosed neighborhood of an existing vertex, whereas in Lemma 1 the new vertexis made adjacent to all vertices in the open neighborhood of an existing vertex.Bessy et al. [2] showed that for graph properties closed under true twin additionthere is a solution for the corresponding edge modification problem such that twoadjacent vertices with an identical closed neighborhood in the input graph alsohave an identical closed neighborhood in the modified graph2 . Hence, a reductionrule similar to Rule 1 applies for graph properties closed under true twin addition.For a discussion on graph properties generalizing cisp graph properties and graphproperties closed under true twin addition and further corresponding generalizeddata reductions rules we refer to [35, Chapter 3.4].Note that for Bicluster Editing this data reduction rule (together with thetrivial rule to remove all connected components that are already biclusters) yieldsa problem kernel with O(k2 ) vertices [34]. For most cisp graph properties, however,these two rules are not sufficient to obtain a kernel. This is also the case for MFCT.Hence, in Section 5, we present further more intricate rules specific to MFCT.4 A Decomposition PropertyIn this and the following sections, we focus on the MFCT problem. Here, weshow that, given a set C of c-vertices such that no vertex in C is in conflict withany c-vertex outside of C , the conflicts involving the vertices in C can be resolvedindependently from the conflicts not involving vertices in C . This fact is used toprove the correctness of one of our data reduction rules in Section 5 and to identifya polynomial-time solvable special case of MFCT in Section 7 that is the basis foran improved search tree algorithm.For an input graph G (Vc , Vt , E ), we consider the conflict graph G (Vc , F )with vertex set Vc and edge set F : {{c0 , c00 } c0 , c00 Vc c0 c00 }. Roughlyspeaking, we show that for each connected component of the conflict graph, theconflicts can be resolved independently. To show this property, we need the following lemma. Throughout this section, we identify a connected component by itsvertex set.Lemma 4 Let C1 and C2 be two connected components of G with NG (C1 ) NG (C2 ) 6 . Then, either1Kernelization results for these problems have been obtained by Guo [21].Note that two vertices with the same open neighborhood have the same closed neighborhood in the complement graph and vice versa. In this sense, our results can be seen asequivalent to the result of Bessy et al. [2] when considering the graph property defined by thecomplements of the forbidden induced subgraphs in the complement graph.2

10Christian Komusiewicz, Johannes Uhlmann– for each a C1 it holds that NG (C2 ) NG (a) or NG (a) NG (C2 ) , or– for each b C2 it holds that NG (C1 ) NG (b) or NG (b) NG (C1 ) .Proof Since NG (C1 ) NG (C2 ) 6 , there is a vertex x C1 and a vertex y C2 with NG (x) NG (y ) 6 . Furthermore, because x and y are in two differentconnected components of G , they are not in conflict, and, thus NG (x) NG (y )or NG (y ) NG (x). Assume without loss of generality that NG (y ) NG (x). Tosimplify the notation in the remainder of the proof, we use N (v ) : NG (v ) todenote the open neighborhood of a vertex v in G.First, we show N (C2 ) N (x). Assume towards a contradiction that N (C2 ) \N (x ) 6 . Let A : {y 0 C2 N (y 0 ) N (x)}. Note that y A and, hence, A 6 . Furthermore, let B : C2 \ A and observe that B 6 by the assumptionthat N (C2 ) \ N (x) 6 . Since C2 is a connected component of G there is avertex y 0 A and a vertex y 00 B being in conflict with each other. That is,N (y 0 ) \ N (y 00 ) 6 and N (y 0 ) N (y 00 ) 6 and N (y 00 ) \ N (y 0 ) 6 .Since N (y 0 ) N (x) the above directly implies N (x) N (y 00 ) 6 and N (x)\N (y 00 ) 6 . Furthermore, y 00 B implies N (y 00 ) \ N (x) 6 . As a consequence, x is in conflictwith y 00 , contradicting the fact that x and y 00 are contained in distinct connectedcomponents of G .Next, we prove that for each a C1 it holds that N (C2 ) N (a) or N (a) N (C2 ) . To this end, consider the following partition of C1 :C1 , : {a C1 N (a) N (C2 ) or N (a) N (C2 ) },C1 : {a C1 N (a) N (C2 )},C1r : C1 \ (C1 , C1 ).Note that x C1 , , and, thus, C1 , 6 . To prove the above claim, we showthat C1 C1r . Assume towards a contradiction that C1 C1r 6 . We distinguishtwo cases based on whether C1r or not.Case 1: C1r . From assumption C1 C1r 6 it follows that C1 6 .Furthermore, note that no vertex in C1 is in conflict with a vertex in C1 , . SinceC1 , 6 and C1 6

of a vertex v, denoted by deg G( v), is the cardinality of N ( ). For a set of ver-tices V0 , the induced subgraph G[0] is the graph over the vertex set V0with edge set ff v;wg2E j 2 V0g. For 0 we use G 0as abbreviation for G[ Vn 0], and for a vertex v2 let denote Gf vg. For two sets X and Ywith X\ ;, let E