Guillaume Blin
email: guillaume.blin@univ-mlv.fr

Guillaume Fertin
email: guillaume.fertin@univ-nantes.fr

Hafedh Mohamed-Babou
email: hafedh.mohamed-babou@univ-nantes.fr

Irena Rusu
email: irena.rusu@univ-nantes.fr

Florian Sikora
email: florian.sikora@univ-mlv.fr

Stéphane Vialette
email: stephane.vialette@univ-mlv.fr

Algorithmic Aspects of Heterogeneous Biological Networks Comparison ⋆

. We consider here a related problem called k-DAGCC: given a directed graph D and an undirected graph G on the same set V of vertices, and an integer k, does there exist sets of vertices V1, V2, . . .

is a DAG and (ii) G[Vi] is connected ? Two variants of k-DAGCC are of interest: (a) the Vis must form a partition of V , or (b) the Vis must form a cover of V .

We study the computational complexity of both variants of k-DAGCC and, depending on the constraints imposed on the input, provide several polynomial-time algorithms, hardness and inapproximability results.

Introduction

Recent advances in the field of biological networks comparison, inspired by developments in sequence comparison, have provided a prominent tool for explaining organization and interpreting function and evolution of biological networks [START_REF] Sharan | Modeling cellular machinery through biological network comparison[END_REF]. In their most basic abstraction level, biological networks can be modeled by graphs, where vertices represent cellular compounds, and edges (or arcs) represent their interactions. These graphs may be directed or undirected, depending on the type of networks they represent: for instance, a Protein-Protein Interaction network (PPI) is usually modeled by an undirected graph whose vertices are proteins and edges represent the physical interactions between proteins; however, a metabolic network is modeled by a directed graph (also called reaction graph), where (a) any vertex represents a reaction which needs both a set of input compounds (substrates) and some enzymes (proteins) as catalysts, and produces a set of compounds (products) and (b) there is an arc from reaction r i to reaction r j if r j uses, as substrate, a product of r i .

Each biological network represents a partial view of the molecular activity within the cell. Thus, comparing them provides a better understanding of the behavior of a biologic system. We say that two biological networks are homogeneous if they are of the same type and have the same graph representation, but come from different species. In contrast, networks are said to be heterogeneous if they come from the same species, but are of different types and have different graph representations (e.g., a directed graph and an undirected graph).

The main comparative approaches considered so far focus on homogeneous networks using networks alignment (see, among others, [START_REF] Kelley | Conserved pathways within bacteria and yeast as revealed by global protein network alignment[END_REF][START_REF] Kelley | Pathblast: a tool for alignment of protein interaction networks[END_REF][START_REF] Pinter | Alignment of metabolic pathways[END_REF][START_REF] Sharan | Modeling cellular machinery through biological network comparison[END_REF][START_REF] Flannick | Graemlin: General and robust alignment of multiple large interaction networks[END_REF][START_REF] Deniélou | Multiple alignment of biological networks: A flexible approach[END_REF][START_REF] Tian | Pairwise alignment of interaction networks by fast identification of maximal conserved patterns[END_REF][START_REF] Kuchaiev | Topological network alignment uncovers biological function and phylogeny[END_REF]). Such methods are powerful for detecting conserved modules across several networks of different species. Unlike homogeneous networks, only few research works aim at comparing heterogeneous networks. Most of the existing methods used to compare heterogeneous networks are usually manual, or use case-by-case methods. In [START_REF] Zheng | Computational identification of operons in microbial genomes[END_REF][START_REF] Rison | Homology, pathway distance and chromosomal localisation of the small molecule metabolism enzymes in Escherichia coli[END_REF][START_REF] Lee | A probabilistic functional network of yeast genes[END_REF][START_REF] Pal | Evidence against the selfish operon theory[END_REF][START_REF] Boyer | Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data[END_REF], authors search for a chain of reactions in a metabolic network, by investigating the relationships between genes involved in the reactions and the proximity of genes along the genome. Interactions between proteins that catalyze successive reactions in metabolic networks have been studied in [START_REF] Durek | The integrated analysis of metabolic and protein interaction networks reveals novel molecular organizing principles[END_REF][START_REF] Huthmacher | A computational analysis of protein interactions in metabolic networks reveals novel enzyme pairs potentially involved in metabolic channeling[END_REF]. In [START_REF] Medvedovsky | An algorithm for orienting graphs based on cause-effect pairs and its applications to orienting protein networks[END_REF][START_REF] Gitter | Discovering pathways by orienting edges in protein interaction networks[END_REF][START_REF] Gamzu | Improved orientations of physical networks[END_REF], authors search signaling pathways by confronting a signal transduction network, represented by a directed graph, to a PPI network, represented by an undirected graph. They perform an orientation of the PPI graph as follows: given a list of ordered source-target pairs, the PPI graph is oriented in such a way that, for a maximum number of pairs (s, t), there is a directed path from the source s to the target t. The advantage of this method is that it allows to return to homogeneous networks with the same graph. However, in addition to its computational difficulty, the good behavior of this method is closely related to the choice of the list of the source-target pairs. In [START_REF] Gitter | Discovering pathways by orienting edges in protein interaction networks[END_REF], such a list is manually constructed.

Recently, a unified framework for comparison and analysis of heterogeneous networks was proposed [START_REF] Fertin | A patternguided approach to compare heterogeneous networks[END_REF]. In particular, the central problem considered in [START_REF] Fertin | A patternguided approach to compare heterogeneous networks[END_REF] is the following: given a directed acyclic graph (DAG) D ′ and an undirected graph G ′ built on the same set of vertices, find the longest directed path in D ′ whose vertices induce a connected component in G ′ . In this setting, D ′ and G ′ represent a metabolic network and a PPI network, respectively. However, in general, metabolic networks are not DAGs, and hence contain directed cycles.

Therefore, we consider in thispaper the following problem, called k-DAGCC, that can be seen as a way to pre-process the input graphs in [START_REF] Fertin | A patternguided approach to compare heterogeneous networks[END_REF]: given a directed graph D and an undirected graph G on the same set V of vertices and an integer k, does there exist sets of vertices

V 1 . . . V k ′ , k ′ ≤ k, such that, for each 1 ≤ i ≤ k ′ , (i) D[V i ] is a DAG and (ii) G[V i ]
is connected ? Two variants of k-DAGCC are considered: (a) the partition version, where the V i s must form a partition of V , and (b) the cover version, where the V i s must form a cover of V .

The problem k-DAGCC (under both its variants) is also motivated by the research of pathways in metabolic networks that correspond to functionally related proteins in PPI networks. Indeed, pathways in metabolic networks correspond to DAGs [START_REF] Pinter | Alignment of metabolic pathways[END_REF], while functionally related proteins in PPI networks correspond to connected subgraphs [START_REF] Boyer | Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data[END_REF][START_REF] Deniélou | Multiple alignment of biological networks: A flexible approach[END_REF][START_REF] Narayanan | Comparing protein interaction networks via a graph match-and-split algorithm[END_REF][START_REF] Tian | Pairwise alignment of interaction networks by fast identification of maximal conserved patterns[END_REF][START_REF] Kuchaiev | Topological network alignment uncovers biological function and phylogeny[END_REF]). Thus, it is of interest to be able to extract biologically relevant information from two large networks by decomposing them into smaller modules that each (i) carry a rich biological information and (ii) are easier to interpret.

In this paper, we study the computational complexity of both variants of k-DAGCC and, depending on the constraints imposed on the input, provide several polynomial-time algorithms, along with hardness and inapproximability results. Once the main notations and definitions will be stated (Section 2), we will define formally and study in detail the complexity of the two variants of the k-DAGCC problem, first in its partition version (Section 3), then in its cover version (Section 4).

Preliminaries

This paper is concerned with both directed and undirected graphs. We briefly recall the basic needed material.

A graph G = (V, E) consists of a set of vertices V and a set of edges (unordered pairs of vertices) E. To shorten the exposition, we shall usually abbreviate |V | and |E| to n and m, respectively. The degree of a vertex u ∈ V is the number of edges incident to it. A graph is acyclic if it does not contain any cycle. An independent set is a subset V ′ ⊆ V such that (x, y) / ∈ E for any x, y ∈ V ′ . A graph is connected if there exists a path between any pair of vertices. For any V ′ ⊆ V , we let G[V ′ ] = (V ′ , E ′ ) stand for the subgraph induced by V ′ , i.e. E ′ = {{x, y} ∈ E : x, y ∈ V ′ }. A graph is a tree if it is both connected and acyclic. A star of order n ≥ 3 is a tree with exactly one vertex of degree strictly greater than 1. A graph is complete if it contains all possible edges. A planar graph is a graph that can be embedded onto the plane, in such a way that its edges intersect only at their endpoints. Finally, a graph is said to be outerplanar if it has a planar embedding such that the vertices lie on a circle and the edges lie inside that circle, without crossing each other.

A directed graph D = (V, A) consists of a set of vertices V and a set of arcs (ordered pairs of vertices) A. A directed acyclic graph (DAG) is a directed graph that does not have any directed cycle. For any

V ′ ⊆ V , we let D[V ′ ] = (V ′ , A ′ ) stand for the subgraph induced by V ′ , i.e. A ′ = {(x, y) ∈ A : x, y ∈ V ′ }.
We shall consider graphs and directed graphs defined on the same set of vertices, i.e. we will write D = (V, A) for the directed graph and G = (V, E) for the undirected graph. To avoid ambiguity, we let m D and m G stand for |A| and |E|, respectively. Given two such graphs D = (V, A) and G = (V, E) built on the same set V of vertices, we say that a partition (resp. a cover)

{V 1 , V 2 . . . V k } of V is valid if, for any 1 ≤ i ≤ k, D[V i ] is a DAG and G[V i ] is connected.
The two variants of k-DAGCC we are going to study in this paper are called respectively k-DAGCC-Partition and k-DAGCC-Cover, and are defined as follows.

k-DAGCC-Partition

Instance: A directed graph D = (V, A), an undirected graph G = (V, E), and an integer k. Question: Does there exist a valid partition

P = {V 1 , V 2 , . . . , V k ′ } of V such that k ′ ≤ k ? k-DAGCC-Cover Instance: A directed graph D = (V, A), an undirected graph G = (V, E)
, and an integer k. Question: Does there exist a valid cover

C = {V 1 , V 2 , . . . , V k ′ } of V such that k ′ ≤ k ?
The natural minimization version of the above decision problems are denoted Min-DAGCC-Partition and Min-DAGCC-Cover, respectively.

❅ ❅ ❅ k G Graph Outerplanar Tree Star Path (n -k) = O(1) P [Prop. 2] k = O(1) NPC [Prop. 4] P [Prop. 3] k unbounded Inapprox. within n 1-ǫ [Prop. 6] APX-hard [Prop. 7] NPC [Prop. 5] P [Prop. 1]
Table 1. Complexity results for k-DAGCC-Partition and Min-DAGCC-Partition.

❅ ❅ ❅ k G Graph Outerplanar Tree Star Path k = O(1) NPC [Prop. 9] P [Prop. 8] k unbounded Inapprox. within n 1-ǫ [Prop. 10] P [Prop. 8]
Table 2. Complexity results for k-DAGCC-Cover and Min-DAGCC-Cover.

The results presented in this paper are summarized in Table 1 (for problems k-DAGCC-Partition and Min-DAGCC-Partition) and Table 2 (for problems k-DAGCC-Cover and Min-DAGCC-Cover).

Partition Version of k-DAGCC

In this section, we provide polynomial-time algorithms, hardness and inapproximability results for different variants of Min-DAGCC-Partition and k-DAGCC-Partition (see Table 1). We first provide polynomial-time algorithms for three restricted cases: (a) G is a path, (b) nk is a constant, and (c) G is an outerplanar graph and k is a constant.

Recall that, given a directed graph D = (V, A) and an undirected graph

G = (V, E), testing whether D is a DAG (resp. whether G is connected) can be done in O(n + m D ) time (resp. O(n + m G ) time) by depth-first search. Proposition 1. Min-DAGCC-Partition is polynomial-time solvable when G is a path.
Proof. The proof is by a simple greedy algorithm. Write (v 1 , v 2 , . . . , v n ) for the path G. We consider the vertices of G from v 1 to v n . We start with S = ∅. For vertex v i , if D[S ∪ {v i }] is a DAG, we add v i to S, otherwise we report S as an element of the sought partition and set S = {v i }. When the algorithm stops, we report the current S as the last element of the partition.

It is easily seen that this greedy algorithm produces a valid partition of V . What is left is to prove that the valid partition obtained by the above algorithm is of minimum cardinality. Let P = {V 1 , V 2 , . . . V k } be the partition returned by our algorithm, and suppose, aiming at a contradiction, that there exists a strictly smaller valid partition

P ′ = {V ′ 1 , V ′ 2 , . . . , V ′ ℓ }, thus with ℓ < k. We first observe that, by construction, V 1 cannot be a proper subset of V ′ 1 .
Since any connected subgraph of G is built on consecutively indexed vertices {v p , v p+1 , v p+2 . . . v q }, it follows that there must exist 2 ≤ i < k and 2 ≤ j ≤ ℓ such that (1) V i is a proper subset of V ′ j , and (2) V ′ j contains the first vertex, say x, of V i+1 . This is a contradiction since V i ∪ {x} is not a DAG in D.

⊓ ⊔ Proposition 2. k-DAGCC-Partition is polynomial-time solvable when nk is a constant.

Proof. Let us prove that this variant of k-DAGCC-Partition can be solved in polynomial time by an exhaustive procedure. We consider all k-partitions of V . We start from the unique n-partition of V and iteratively compute all (k -1)partitions of V starting from its k-partitions. Recall that the Stirling number of the second kind S(n, k) represents the number of ways to partition a set of n elements into k nonempty subsets. We have

S(n, k) = S(n, n) n-k-1 i=0 n-i 2 . But S(n, n) = 1, and hence S(n, k) = n-k-1 i=0 n-i 2 = O(n 2(n-k)
). For each of these O(n 2(n-k) ) partitions, we can check in polynomial-time whether it is a valid solution for k-DAGCC-Partition. The proposition follows.

⊓ ⊔ Proposition 3. k-DAGCC-Partition is polynomial-time solvable when G is an outerplanar graph and k is a constant.

Proof. Recall that a graph is outerplanar just when its vertices can be placed on a circle so that its edges become non-crossing chords of the circle. Fix any such an outerplanar circular embedding. Let V 1 , V 2 , . . . , V k be any valid partition of V . Now, associate to any V i , 1 ≤ i ≤ k, the smallest arc of the circle that covers all vertices in V i (according to the outerplanar circular embedding). Since V 1 , V 2 , . . . , V k is a valid partition of V , any vertex is covered by at least one arc of the circle, and no two arcs of the circle share a common endpoint. Moreover, since (v 1 , v 2 , . . . , v n ) is an outerplanar embedding of G and G[V i ] is connected for every 1 ≤ i ≤ k, it follows that no two arcs of the circle properly overlap.

The algorithm is by enumerating all sets of non-overlapping k arcs of the circle with distinct endpoints that cover V . Let v 1 , v 2 , . . . , v n be the vertices of G in the outerplanar circular embedding following, say, the trigonometric orientation. For any 1

≤ i ≤ n, consider all 2(k -1)-subsets of V \ {v i , v i-1 } (by convention, v 0 = v n ). Let {v j1 , v j2 , . . . , v j 2(k-1)
} be such a subset, where the vertices are read along the outerplanar circular embedding starting from v i and following the trigonometric orientation. We now need to construct all possible arcs of the circle with endpoints v i , v j1 , v j2 , . . . , v j 2(k-1) , v i-1 such that no two arcs of the circle are overlapping. Clearly, this reduces to considering all well-formed parenthesis strings of length 2k. Our construction yields sets of k arcs a 1 , a 2 , . . . , a k of the circle such that (1) any two arcs of the circle have distinct endpoints, (2) no two arcs of the circle are overlapping, and (3) each vertex of V is covered by at least one arc of the circle. For any such solution, we construct a partition (V 1 , V 2 , . . . , V k ) as follows: V i contains all vertices covered by arc a i of the circle, except those vertices covered by at least one arc a j of the circle which is strictly covered by a i . This algorithm is O(n

2 n 2(k-1) 2(k-1)
k-1

(n + m)) time, where m = max{m D , m G }. Indeed, we have n possibilities for choosing the reference vertex v i . Starting from each reference vertex v i , we consider

n 2(k-1) 1 k 2(k-1) k-1 sets of k arcs of the circle ( 1 k 2(k-1) k-1
is the number of well-formed parenthesis strings of length 2k). From these sets, one can construct a solution Proof. k-DAGCC-Partition is certainly in NP. To prove hardness, we propose a reduction from the NP-complete Not-All-Equal 3SAT (NAE 3Sat) problem [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF]: Given a collection C q = {c 1 , . . . c q } of q clauses, where each clause consists of a set of three literals over a finite set of n boolean variables V n = {x 1 , . . . x n }, is there a truth assignment of each variable of V n such that at least one of the literals is true and at least one is false in each clause ? For ease of exposition, for any 1 ≤ j ≤ 3, we let c j i stand for the j-th literal of clause c i . Given any instance (C q , V n ) of NAE 3Sat, we build D and G as follows:

V i , 1 ≤ i ≤ k, is O(n) time,
• V = {v j i : 1 ≤ i ≤ q, 1 ≤ j ≤ 3} ∪ {v i : 3 ≤ i ≤ k} • A = {(v j i , v j ′ i ′ ), (v j ′ i ′ , v j i ) : c j i = c j ′ i ′ } ∪ {(v 1 i , v 2 i ), (v 2 i , v 3 i ), (v 3 i , v 1 i ) : 1 ≤ i ≤ q} ∪ {(v i , v), (v, v i ) : 3 ≤ i ≤ k, v ∈ V \ {v i }} • E = {(v, v ′ ) : v, v ′ ∈ V }
Roughly speaking, vertex v j i corresponds to the j-th literal of clause c i , whereas vertices v i , 3 ≤ i ≤ k, are gadgets to adapt the proof for any k ≥ 2. There is a cycle of length two between any pair of vertices representing two complementary literals (e.g. x i and x i ) and between v i , 3 ≤ i ≤ k, and any other vertex of V . Moreover, there is a cycle of length three between the triple of vertices (v 1 i , v 2 i , v 3 i ) corresponding to the three literals of any clause c i . Finally, G is a complete graph on V . An illustration of such a construction -omitting G -is given in Figure 1.

v 1 1 v 2 1 v 3 1 v 1 2 v 2 2 v 3 2 v 1 3 v 2 3 v 3 3 v3 v4 . . . v k Fig. 1. Illustration of the construction of D, given C q = {(x 1 ∨ x 2 ∨ x 3 ), (x 1 ∨ x 2 ∨ x 4 ), (x 1 ∨ x 2 ∨ x 3 )}. For readability, arcs {(v j i , v l ), (v l , v j i ) : 1 ≤ i ≤ q, 1 ≤ j ≤ 3, 4 ≤ l ≤ k} are not drawn.
We claim that there is a solution for our NAE 3Sat instance iff there exists a valid partition (V 1 , V 2 , . . . , V k ) of V .

(⇒) Given a truth assignment A of V n such that each clause contains at least one true and one false literals, we make a partition

P = {V 1 , V 2 . . . V k } of V as follows: V 1 = {v j i : c j i = true in A}, V 2 = {v j i : 1 ≤ i ≤ q, 1 ≤ j ≤ 3} \ V 1 , and, V i = {v i } for 3 ≤ i ≤ k.
By definition, there is one or two true literal(s) in each clause. Thus, among the three vertices corresponding to the literals of c i , at least one and at most two of them are in V 1 (resp. V 2 ). Moreover, considering A, any variable cannot be simultaneously true and false. Therefore, two vertices representing complementary literals cannot both belong to V 1 (resp. V 2 ). Then it follows that each D[V i ], 1 ≤ i ≤ k, is a DAG since all cycles have been destroyed. Since G is complete, we have a valid solution.

(⇐) Let P = {V 1 , V 2 . . . V k } be a valid partition of V . We build a truth assignment A as follows. By construction, there is no loss of generality in assuming V 3 = {v 3 }, . . . , V k = {v k } (each of these vertices has to occur as a singleton in the partition). Let us define a truth setting A such that literal c j i , 1 ≤ i ≤ q and 1 ≤ j ≤ 3, evaluates to true iff v j i ∈ V 1 . This requirement certainly defines a truth setting assignment since opposite literals are part of a cycle of length two. Let us now prove that A is a solution for our NAE 3Sat instance. Indeed, at least one and at most two of the vertices representing the literals of each clause c i belong to V 1 . Thus, any clause c i is indeed satisfied and by at most two of its literals.

⊓ ⊔ Proposition 5. k-DAGCC-Partition is NP-complete even when G is a star.

Proof. We propose a reduction from the NP-complete k ′ -Independent Set (k ′ -IS) problem [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF]: Given a graph G I = (V I , E I ) and a positive integer k ′ , is there an independent set V ′ I ⊆ V I of cardinality at least k ′ ? Given any instance G I of k ′ -IS, we build D and G as follows:

• V = V I ∪ {v r } • A = {(v, v ′ ), (v ′ , v) : (v, v ′ ) ∈ E I } • E = {(v r , v) : v ∈ V I } Moreover, we set k = |V I |-k ′ +1.
Roughly speaking, graph D is obtained from G I by replacing each edge by two arcs in opposite directions, and by adding an isolated vertex v r . The graph G is a star whose center is v r ; thus v r must be part of any connected subgraph of G of order strictly greater than one. Construction of both these graphs is illustrated in Figure 2. We will show that there is an independent set, in

G I = (V I , E I ), of cardinality at least k ′ iff there is a solution for k-DAGCC-Partition with k = |V I |-k ′ +1.
(⇒) Given an independent set of G I of cardinality greater or equal than k ′ , choose any subset V ′ I of k ′ vertices of it (which is itself an independent set). We compute the partition

P = {V 1 , V 2 . . . V k } of V , where k = |V I |-k ′ +1, as follows. Let V 1 = V ′ I ∪{v r }.
Consider any ordering of the vertices in V I \V ′ I , and, for every 2 ≤ i ≤ k, let V i = {v}, where v is the (i -1)-th vertex in this ordering. First, note that any

D[V i ], 2 ≤ i ≤ k is indeed a DAG since it is composed of a single vertex. Moreover, by definition, ∄{v, v ′ } ⊆ V ′ I , such that (v, v ′ ) ∈ E I . Therefore, D[V 1 ] is composed of isolated vertices (and thus, is also a DAG). The induced subgraphs G[V i ], 2 ≤ i ≤ k, are trivially connected; moreover, connectivity of G[V 1 ] is ensured by the fact that v r ∈ V 1 .
(⇐) Given a solution P = {V 1 , V 2 . . . V k }, to k-DAGCC-Partition, we build an independent set

V ′ I ⊆ V I of G I , such that |V ′ I | = |V I | -k + 1, as follows. Let V ′ I = V j \{v r }
where D j is the DAG containing v r . As previously mentioned, in any solution, any connected subgraph of G of order strictly greater than one must contain v r . Since we require that for every 1 ≤ i < j ≤ k, V i ∩ V j = ∅, at most one of the V i s can be of order strictly greater than one, and it contains v r . Thus,

|V ′ I | = |V j | -1 = ((|V I | + 1) -(k -1)) -1, that is |V ′ I | = |V I | -k + 1. Moreover, V ′
I is indeed an independent set since D j is a DAG and thus does not contain cycles.

⊓ ⊔

Finally, let us prove the inapproximability of Min-DAGCC-Partition when G is a graph or a tree. Proposition 6. Min-DAGCC-Partition cannot be approximated within n 1-ǫ , for any ǫ > 0.

Proof. We give an L-reduction from the Minimum Chromatic Number (Min-CN) problem defined as follows: Given a graph G C = (V C , E C ), find a proper vertex coloring of G C using the minimum number of colors, where a vertex coloring is said to be proper iff two neighbors in G C carry different colors.

Given any instance G C of Min-CN, we build D and G as follows:

• V = V C • A = {(v, v ′ ), (v ′ , v) : (v, v ′ ) ∈ E C } • E = {(v, v ′ ) : v, v ′ ∈ V C } \ E C
In other words, we keep the same set of vertices as in G C , the graph D is obtained from G C by replacing each edge with two arcs in opposite directions, while G is the complement of G C . An example of such a construction is given in Figure 3.

Let us prove that this construction is indeed an L-reduction from Min-CN. More precisely, we will prove the following property: there exists a proper coloring for G C using k colors iff there exists a valid cardinality k partition

P = {V 1 , V 2 . . . V k } of V . (⇒) Given a coloring of G C with k colors, let V i , 1 ≤ i ≤ k
, be the set of vertices assigned color i. Let us now show that the partition P = {V i : 1 ≤ i ≤ k} is valid (i.e., for every 1

≤ i ≤ k, D[V i ] is a DAG and G[V i ] is connected). Indeed, by definition of a proper coloring, each V i , 1 ≤ i ≤ k, is an independent set. Thus, any D[V i ], 1 ≤ i ≤ k,
is composed of isolated vertices -and therefore is a DAG. Moreover, the induced subgraphs in G are indeed connected since, by construction, whenever two vertices are not adjacent in G C , they are in G. (⇐) Given a valid k-partition P = {V 1 , V 2 . . . V k } of V , we assign to any vertex v ∈ V i the color i, for any 1 ≤ i ≤ k. This assignment is a proper coloring since, by construction, no D[V i ], 1 ≤ i ≤ k, contains an arc, otherwise it would not be a DAG.

The above reduction linearly preserves the approximation, and moreover the sizes of the solutions in the two problems are equal. Hence, given an approximation algorithm for Min-DAGCC-Partition, one can derive an algorithm for Min-CN with the same approximation ratio. Since Min-CN cannot be approximated within n 1-ǫ for any ǫ > 0 [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF], so does Min-DAGCC-Partition.

⊓ ⊔ Proposition 7. Min-DAGCC-Partition is APX-hard even when G is a tree.

Proof. We give an L-reduction from the APX-hard problem Set Cover-2 [START_REF] Papadimitriou | Optimization, approximation, and complexity classes[END_REF] defined as follows: Given a ground set X = {x 1 , . . . x n } and a collection of sets C = {S 1 , . . . S q } in which each element of X appears at most twice, find a minimum set cover C ′ , i.e. a set C ′ ⊆ C such that X = Si∈C ′ S i and |C ′ | is minimum. In the rest of the proof, for any 1 ≤ i ≤ q, we will denote by s j i the j-th element of S i .

Given any instance (X , C) of Set Cover-2, we build D and G as follows:

• V = {v r } ∪ {v i : S i ∈ C} ∪ {v k i : x k = s j i , S i ∈ C, 1 ≤ j ≤ |S i |} • A = {(v k i , v k j ), (v k j , v k i ) : x k ∈ S i ∩ S j } ∪ {(v r , v k i ), (v k i , v r ) : ∄S j s.t. x k ∈ S i ∩ S j } • E = {(v r , v i ) : S i ∈ C} ∪ {(v i , v k i ) : x k ∈ S i , S i ∈ C}.
Otherwise stated, G is a tree rooted at v r , whose children are the vertices v i , 1 ≤ i ≤ q (where v i , 1 ≤ i ≤ q, represents S i ). Each v i has one child per element of S i (v k i for x k ∈ S i ). In D, the vertices v i , 1 ≤ i ≤ q, are isolated whereas the two vertices (v k i , v k j ) representing an element x k appearing twice in C form a cycle of length two. Each of the remaining vertices forms a cycle of length two with v r . An illustration of such a construction is given in Figure 4. Let us now prove that this construction is indeed an L-reduction; for this, we show that there is a solution C ′ of size k for Set Cover-2 iff there is a valid partition of V in at most k + 1 sets V 1 , V 2 . . . V k+1 .

(⇒) Given a set-cover C ′ ⊆ C of cardinality k, we compute the partition

P = {V 1 , V 2 . . . , V k , V k+1 } of V as follows: for each S i ∈ C ′ , 1 ≤ i ≤ k, let V i = {v i } ∪ {v k i : x k ∈ S i }, and let V k+1 = {v r } ∪ {v j , v k j : x k ∈ S j , S j ∈ C \ C ′ }.
In other words, there is a set V i (inducing the subtree of G rooted at v i ) for each S i belonging to the set cover; whereas V k+1 contains the remaining vertices (including the root v r of G). Consequently, by construction, for any 1 (⇐) Given a valid partition P = {V 1 , V 2 . . . V k } of V , we build a cover

≤ i ≤ k+1, G[V i ] is indeed connected. Moreover, each D[V i ], 1 ≤ i ≤ k,
C ′ = {S 1 , . . . , S k-1 } as follows. Assume, wlog, v r ∈ V 1 ; then C ′ = {S i : ∃v j i ∈ V 1 }.
In other words, we add in the cover all the sets having an element whose corresponding vertex does not belong to V 1 . First, note that, by construction, there is at most one vertex of {v i : 1 ≤ i ≤ q} in any G[V j ], 2 ≤ j ≤ k, since any path linking two such vertices goes through v r , which is already contained in V 1 . It follows that |C ′ | ≤ k -1. It remains to show that C ′ is indeed a set cover for X . To do so, consider any element x i ∈ X . If x i occurs exactly once in C (wlog, suppose x i ∈ S j ), then the corresponding vertex v i j cannot belong to V 1 since, by construction, it would induce a cycle with v r in D[V 1 ]. Therefore, S j ∈ C ′ . Otherwise, x i occurs exactly twice, and then at most one of the corresponding vertices v i j and v

i j ′ belongs to V 1 , since otherwise it would induce a cycle in D[V 1 ]. Thus, every x i ∈ X appears at least once in C ′ .
The above reduction is an L-reduction from Set Cover-2 to Min-DAGCC-Partition. Hence, since Set Cover-2 is APX-hard, so is Min-DAGCC-Partition, and the proposition is proved.

⊓ ⊔

Cover Version of k-DAGCC

As we did in the previous section, we now show several complexity results concerning the k-DAGCC-Cover and Min-DAGCC-Cover problems (see also Table 2).

Let us first provide a polynomial-time algorithm when G is a path (Proposition 8). We first prove the following lemma.

C = {V 1 , V 2 , . . . V k } of D such that for every 1 ≤ i ≤ k, G[V i ] is connected and D[V i ] is a DAG. Since G is a path, so does any G[V i ]
. Suppose now that a vertex v ∈ V belongs to at least three pairwise distinct sets V p , V q , V r from C. In that case, G being a path, one of these three sets, say (wlog) V p , satisfies V p ⊆ V q ∪ V r , and we can remove V p from C and obtain a strictly smaller cover. Applying this rule until no such case occurs, we end up with a cover C ′ = {V ′ 1 , . . . V ′ k ′ }, k ′ ≤ k, in which every vertex v ∈ V belongs to at most two different sets of C ′ . Therefore, assuming the V ′ i s are ordered according to their leftmost vertex in G, we consider the following partition: As opposed to k-DAGCC-Partition, k-DAGCC-Cover proves to be NPcomplete even when G is a star and k is a constant. Proposition 9. For any k ≥ 3, k-DAGCC-Cover is NP-complete, even when G is a star.

P = {V ′′ i = V ′ i \ V ′ i+1 : 1 ≤ i < k ′ s.t. V ′ i ∈ C ′ } ∪ {V ′ k ′ }. P

Conclusion

In this paper, we have studied the problem of decomposing (i.e., partitioning or covering) a directed graph D into DAGs, such that each DAG induces a connected subgraph in a given undirected graph G built on same vertex set as D. We have provided, depending on the constraints imposed on the input, several polynomial-time algorithms, as well as hardness and inapproximability results.

There are still several open problems worthwhile to study. For example, one may consider the parameterized complexity of k-DAGCC-Partition, where the parameter is the number of partitions, in the specific case where G is a tree (we indeed know that no FPT algorithm of complexity f (k)n O (1) is possible when G is a graph, since the problem is NP-complete for k = 2). One may also consider studying the approximability of Min-DAGCC-Partition.

  and check whether each subset V i , 1 ≤ i ≤ k, induces both a DAG in D and a connected component in G in O(n + m) time. The proposition follows. ⊓ ⊔ We now prove that k-DAGCC-Partition becomes NP-complete when (a) G is a complete graph or (b) G is a star. Proposition 4. For any k ≥ 2, k-DAGCC-Partition is NP-complete even when G is a complete graph.

Fig. 2 .

 2 Fig. 2. Illustration of the construction of D and G, given G I . We highlighted a possible 2-IS {1, 4} and a corresponding valid 4-partition of V .

GFig. 3 .

 3 Fig. 3. Illustration of the construction of D and G, given G C . We highlighted a 3-coloring of D and a corresponding valid 3-partition of V .

Fig. 4 .

 4 Fig. 4. Illustration of the construction of D and G, given C = {{x 1 , x 3 , x 4 }, {x 2 , x 3 }, {x 1 , x 4 }, {x 5 }}.

  is a DAG since it does not contain v r and each element of X occurs at most once in S i . Finally, D[V k+1 ] is also a DAG since, by definition of Set Cover-2, any element appears at most twice in C and at least once in C ′ . Therefore, in C \ C ′ , any element appears at most once, and thus no cycle occurs in D[V k+1 ].

Lemma 1 .

 1 When G is a path, k-DAGCC-Cover admits a YES answer iff k-DAGCC-Partition admits a YES answer.Proof. Any partition being a cover, if k-DAGCC-Partition admits a YES answer, then so does k-DAGCC-Cover. Conversely, consider any positive answer to k-DAGCC-Cover. Hence, there exists a cover

Proposition 8 .

 8 is indeed a partition of V , of cardinality k ′ ≤ k ; besides, (a) since for any 1≤ i < k ′ , D[V ′ i ] is a DAG, so does any D[V ′′ i ] ; (b) D[V ′ k ′ ] is a DAG by hypothesis, and (c) G[V ′′ i ], 1 ≤ i < k ′ , and G[V ′ k ′ ]are all subpaths of G, and therefore connected. Thus k-DAGCC-Partition admits a YES answer, and the lemma is proved.⊓ ⊔ Min-DAGCC-Cover is polynomial-time solvable when G is a path.Proof. By Lemma 1, we know that when G is a path, the (YES/NO) solutions of k-DAGCC-Partition and k-DAGCC-Cover are equivalent. Thus, in the minimization versions of both problems (namely, Min-DAGCC-Partition and Min-DAGCC-Cover), the same minimum value is reached, and in particular if there exists a cardinality k solution to Min-DAGCC-Partition, then there exists a cardinality k solution to Min-DAGCC-Cover. Besides, any partition being a cover, we conclude that any solution to Min-DAGCC-Partition is also a solution to Min-DAGCC-Cover Since Min-DAGCC-Partition is polynomial time solvable (see Proposition 1), so does Min-DAGCC-Cover.⊓ ⊔

⋆ This work was partially supported by GDR-IM and ANR project BIRDS JCJC SIMI 2-2010

Proof. Clearly, k-DAGCC-Cover is in NP. In order to prove that the problem is NP-hard, we provide a reduction from the Minimum Chromatic Number (Min-CN) problem, in its natural decision version: Given a graph G C = (V C , E C ) and an integer k, does there exist a proper vertex coloring of G C using at most k colors ? This problem has been shown to be NP-hard for any k ≥ 3 [START_REF] Garey | Computers and Intractability: A guide to the theory of NP-completeness[END_REF].

Given any instance G C of Min-CN, we build D and G as follows:

In other words, D is obtained from G C by replacing each edge by two arcs in opposite directions, and by adding an arc from any vertex to v r , while G is a star whose center is v r .

We now prove the following property: there exists a proper coloring for G C using k colors iff there exists a valid cardinality

By definition of a proper coloring, each S i is an independent set in G C (thus in D). Hence, since the outdegree of v r is equal to zero, any

This assignment is a proper coloring of G C since, by construction, no V i can contain two neighbors in G C , since otherwise, by construction of D, D[V i ] would not be a DAG.

⊓ ⊔

We finally show that Min-DAGCC-Cover is hard to approximate. Note that this inapproximability even holds when G is a star (instead of general graphs for the problem Min-DAGCC-Partition).

Proposition 10. Min-DAGCC-Cover cannot be approximated within n 1-ǫ , for any ǫ > 0, even when G is a star.

Proof. The reduction provided in proof of Proposition 9 is actually an L-reduction, since the sizes of the solutions in the two problems are equal (we have indeed proved, following our reduction, that "there exists a proper coloring for G C using k colors iff there exists a valid cardinality k cover C = {V 1 , V 2 . . . V k } of V "). Hence, given any approximation algorithm for Min-DAGCC-Cover, one can derive an algorithm for Min-CN, with the same approximation ratio. Since Min-CN cannot be approximated within n 1-ǫ for any ǫ > 0 [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF], so does Min-DAGCC-Cover.