Printer Friendly

The complexity of deciding whether a graph admits an orientation with fixed weak diameter.

An oriented graph [??] is said weak (resp. strong) if, for every pair {u, v} of vertices of [??], there are directed paths joining u and v in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have length at most k, we call [??] k-weak (resp. k-strong). We consider several problems asking whether an undirected graph G admits orientations satisfying some connectivity and distance properties. As a main result, we show that deciding whether G admits a k-weak orientation is NP-complete for every k [greater than or equal to] 2. This notably implies the NP-completeness of several problems asking whether G is an extremal graph (in terms of needed colours) for some vertex-colouring problems.

Keywords: oriented graph, weak diameter, strong diameter, complexity

1 Introduction

Let G be a simple undirected graph with vertex set V(G) and edge set E(G). By orienting every edge uv of G, either from u to v or from v to u, one obtains an orientation [??] of G. This oriented graph [??] has the same vertex set as G, i.e. V([??]) = V(G), and, for every edge uv [member of] E(G), we have either [??] [member of] E( [??]) or [??] [member of] E([??]) depending on the orientation assigned to uv.

The distance dist(G, u, v) from u to v in G is the minimal length of a path joining u and v. We refer to the maximum distance between two vertices of G as its diameter, and denote it diam(G). These definitions can be naturally adapted to the context of oriented graphs. A dipath of [??] is a sequence ([v.sub.1], [v.sub.2],... , [v.sub.k]) of distinct vertices such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [??] E([??]) for every i [member of] {1,2,... ,k - 1}. Such a dipath has length k - 1 and is written [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The directed distance dist([??], u, v) from u to v in [??] is the minimal length of a dipath starting from u and ending at v. Note that, contrarily to the undirected case, we may have dist([??], u, v) [not equal to] dist([??], v, u). Therefore, two definitions of the oriented diameter can be adopted. Let

[dist.sub.w]([??], u,v) = min{dist([??], u, v), dist([??], v,u)}

and

[dist.sub.s]([??], u, v) = max{dist([??], u, v), dist([??], v, u)}.

These two measures are called the weak distance and strong distance, respectively, from u to v in [??]. The weak diameter of [??], denoted [diam.sub.w]([??]), is the maximum weak distance from a vertex to another one. The strong diameter of [??], denoted [diam.sub.s] ([??]), is the maximum strong distance from a vertex to another one. The weak diameter can intuitively be seen as an optimistic measure of the directed distances in an oriented graph (basically two vertices u and v are considered close when, say, u can reach v with few moves, and this no matter how many moves needs v to reach u (if possible)). We call [??] k-weak (resp. k-strong) if it has weak (resp. strong) diameter at most k. More generally, we say that [??] is weak (resp. strong) if it is k-weak (resp. k-strong) for some finite value of k. In turn, a weak (resp. strong) orientation of an undirected graph refers to an orientation being a weak (resp. strong) oriented graph.

Many appealing and attractive problems in graph theory are about deducing graph orientations with particular properties. Such problems find natural applications in real-world problems (e.g. traffic problems). In this paper, we mainly focus on the existence of (either weak or strong) orientations of some undirected graph G in which the diameter is preserved, i.e. as close to diam(G) as possible. Though the question of deciding whether G admits a weak or strong orientation can be answered easily by using several classic results of graph theory (see Sections 2.1 and 3), the hardness of deciding the same when a (weak or strong) diameter restriction is required was mostly unknown. Our main contribution is an indication of the complexity of answering this problem. In particular, we show that deciding whether G admits a k-weak orientation is NP-complete for every k [greater than or equal to] 2, and suggest that the same should be true for k-strong orientations, completing a result of Chvatal and Thomassen.

This paper is organized as follows. In Section 2, we first consider the questions above for the weak notions of distance, orientation, and diameter. Then, we consider, in Section 3, the same questions but for the strong notions of distance, orientation, and diameter. Consequences of our results are then discussed in Section 4. In particular, as side results we get that deciding whether an undirected graph is extremal (in terms of needed colours) for some vertex-colouring problems is NP-complete.

2 Weak orientations

This section is devoted to the following related two decision problems.

WEAK ORIENTATION

Instance: A graph G.

Question: Does G admit a weak orientation?

k-WEAK ORIENTATION

Instance: A graph G.

Question: Does G admit a k-weak orientation?

Using two classic tools of graph theory, we prove, in Theorem 3 below, that WEAK ORIENTATION can be answered in linear time. Then, we prove that k-WEAK ORIENTATION is in P for k = 1, and NP-complete otherwise, i.e. whenever k [greater than or equal to] 2 (see Theorem 5). These two results confirm that imposing a (even constant) weak diameter condition is a strong restriction which makes the problem more difficult.

2.1 Complexity of WEAK ORIENTATION

We here show that WEAK ORIENTATION can be solved in linear time, and is hence in P. For this purpose, we need to recall the following two classic results. Recall that a bridge of a graph is an edge whose removal disconnects the graph.

Theorem 1 (Tarjan [11]). The bridges of a graph can be found in linear time.

Theorem 2 (Robbins [8]). A strong orientation of a bridgeless undirected graph can be computed in linear time.

We also need the notion of B-contraction. Given an undirected graph G, its B-contraction is the graph obtained as follows. Let first [e.sub.1], [e.sub.2],... , [e.sub.x] denote the bridges of G, and [B.sub.1], [B.sub.2],..., [B.sub.y] denote the (bridgeless) components of G - {[e.sub.1], [e.sub.2],... , [e.sub.x]}. Then the B-contraction of Gis obtained by associating a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with each component [B.sub.i], and in which two vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are joined by an edge if and only if there is a bridge joining [B.sub.i] and Bj in G. Clearly the B-contraction of any graph is a tree.

We are now ready to introduce the result of this section.

Theorem 3. An undirected graph admits a weak orientation if and only if its B-contraction is a path.

Proof: We start by proving the sufficiency. Assume G is a connected undirected graph whose B-contraction is a path with successive edges [e.sub.1], [e.sub.2],..., [e.sub.x], and denote [B.sub.1], [B.sub.2],..., [B.sub.y] the components of G - {[e.sub.1], [e.sub.2],..., [e.sub.x]}. We obtain a weak orientation [??] of G as follows. First orient the edges [e.sub.1], [e.sub.2],..., [e.sub.x] towards the same direction, i.e. following the natural first-last ordering of the B-contraction. Then orient the edges of every [B.sub.i] to form a strong component. Such an orientation exists according to Theorem 2 since each [B.sub.i] has no bridge. Clearly [??] is weak since every two vertices within a same [B.sub.i] can reach each other and the orientation of the edges [e.sub.1], [e.sub.2],..., [e.sub.x] form a dipath in the B-contraction.

We now prove the necessity by contradiction. Assume the B-contraction of G is not a path, but G admits a weak orientation [??]. Clearly the orientation of [??], restricted to the B-contraction, should be weak. But this is impossible as the B-contraction of G has a node with degree at least 3, and every B-contraction is a tree. A contradiction. []

Since the B-contraction of any graph can be computed in linear time (due to Theorem 1), we can answer in linear time to every instance of WEAK ORIENTATION. Actually, since the bridges of a graph and a strong orientation of every bridgeless undirected graph can be deduced in linear time (recall Theorems 1 and 2), the algorithm described in the sufficiency part of the proof of Theorem 3 can even be implemented to efficiently construct, i.e. in linear time, a weak orientation (if any) of every undirected graph.

Corollary 4. WEAK ORIENTATION is in P.

2.2 Complexity of k-WEAK ORIENTATION

Clearly the answer to an instance of 1 -WEAK ORIENTATION is yes if and only if G is complete. So 1 -WEAK ORIENTATION is in P. The complexity of every remaining problem k-WEAK ORIENTATION (i.e. with k [greater than or equal to] 2) was mentioned and asked in several references of literature (notably in [6, 9, 10]) due to its relationship with other problems of graph theory (see concluding Section 4). We herein settle the complexity of these problems by showing them to be NP-complete in general.

Theorem 5. k-WEAK ORIENTATION is NP-complete for every k [greater than or equal to] 2.

Proof: For any fixed k, one can, given an orientation G of G, check in polynomial time whether [diam.sub.w] ([??]) [less than or equal to] k. This can be done by essentially computing, for every pair of distinct vertices of G, the length of the shortest directed paths joining these two vertices in [??]. Many polynomial-time algorithms, such as e.g. the well-known Floyd-Warshall Algorithm (with unit weights), can be found in literature and applied to handle this. Consequently, k-WEAK ORIENTATION is in NP.

Let k [greater than or equal to] 2 be fixed. We show that k-WEAK ORIENTATION is NP-hard by reduction from the following problem, which is shown to be NP-complete in [5].

2-VERTEX-COLOURING OF 3-UNIFORM HYPERGRAPHS

Instance: A 3-uniform hypergraph H.

Question: Is H 2-colourable, i.e. can we colour each vertex of H either blue or red so that every hyperedge of H has at least one blue vertex and one red vertex?

Throughout this proof, for any hypergraph H with order n and size m we denote its vertices by [x.sub.1], [x.sub.2],... , [x.sub.n] and hyperedges by [E.sub.1], [E.sub.2],..., [E.sub.m]. For every i [member of] {1, 2,..., n}, we further denote by [n.sub.i] [greater than or equal to] 1 the number of distinct hyperedges of H which contain the vertex [x.sub.i]. From a 3-uniform hypergraph H, we produce a graph [G.sub.H] such that H is 2-colourable if and only if [G.sub.H] admits a k-weak orientation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This reduction is achieved in polynomial time compared to the size of H.

We first describe the crux [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of [G.sub.H], i.e. the subgraph of [G.sub.H] from which the equivalence with H will follow. The subgraph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] does not have diameter k, but [G.sub.H] will be augmented later so that it has diameter k, and this without altering the equivalence. The crux [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has the following vertices (see Figure 1). With each vertex [x.sub.i] of H, we associate [n.sub.i] + 2 vertices [u.sub.i], [u'.sub.i], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [j.sub.1], [j.sub.2],... ,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are the distinct indices of the hyperedges of H which contain [x.sub.i]. We now associate additional vertices in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with each hyperedge [E.sub.j] of H, where j [member of] {1,2,... ,m}. This association depends on the parity of k:

* If k is even, then add two vertices [a.sub.j] and [a'.sub.j] to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

* Otherwise, if k is odd, then add two cycles [a.sub.j][b.sub.j][c.sub.j][a.sub.j] and [a'.sub.j][b'.sub.j][c'.sub.j][a'.sub.j] with length 3 to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now link the vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by means of several vertex-disjoint paths. By "joining a pair {u, v} of vertices by a path", we mean that we identify the endvertices of a new path with u and v, respectively. Since this operation is used at most once for joining any pair {u, v} of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we use the notation uPv to denote the resulting path (if any). First, join every pair {[u.sub.i],[u'.sub.i]} by a path with length [k/2] J. Then also join every pair {[u'.sub.j][v.sub.i,j]} by a path with length [k/2]. Now consider each hyperedge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of H, and add the following paths to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]:

* If k is even, join every pair of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by means of a path with length [k/2].

* Otherwise, if k is odd, then join every pair of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by a path with length [k/2].

Note that, by construction, exactly one pair {[v.sub.i,j], s([v.sub.i,j])} (resp. {[v.sub.i,j], s'([v.sub.i,j])}) was joined by a path with length [k/2], where s([v.sub.i,j]) (resp. s'([v.sub.i,j])) is a vertex of the form [a.sub.j], [b.sub.j] or [c.sub.j] (resp. [a'.sub.j], [b.sub.j]' or [c'.sub.j]). The notation s([v.sub.i,j]) and s'([v.sub.i,j]) are used throughout this section. In particular, observe that if k is even, then we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every hyperedge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of H. We analogously have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A pair {u, v} of distinct vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is said representative whenever it matches one of the following forms:

1. {[u.sub.i], [v.sub.i,j]} where i [member of] {1,2,..., n}, j [member of] {1,2,..., m}, and [x.sub.i] [member of] [E.sub.j].

2. {[u'.sub.i], s([v.sub.i,j])} where i [member of] {1,2,..., n}, j [member of] {1, 2,..., m}, and [x.sub.i] [member of] [E.sub.j].

3. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [i.sub.1], [i.sub.2] [member of] {1,2,..., n}, j [member of] {1,2,..., m}, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [member of] [E.sub.j].

An orientation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is good if every two vertices forming a representative pair are linked by a k-dipath in either direction. Note that, in this definition, there is no requirement on the oriented distance between two vertices which are at distance at least k + 1. A representative pair is a pair of vertices which will not be adjacent in the final [G.sub.H], and for which there will be at most two paths with length at most k joining it. All of these paths will belong to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] so that the existence of a k-weak orientation of [G.sub.H] will depend on the existence of a good orientation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We prove below that we have an equivalence between finding a proper 2-vertex-colouring of H and a good orientation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The proof relies on the following claims.

Claim 1. Suppose the vertex [x.sub.i] belongs to the hyperedges [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of H. Then, in any good orientation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], either

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipath for every j [member of] {[j.sub.1], [j.sub.2],... ,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]}, or

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipath for every j [member of] {[j.sub.1], [j.sub.2],... ,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]}.

Proof: Note that because [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the only path with length at most k joining [u.sub.i] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] must be a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Assume [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is now a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] must also be a dipath for every j [member of] {[j.sub.1], [j.sub.2],... ,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]} since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the only path with length at most k joining [u.sub.i] and [v.sub.i,j] in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Similarly, since, for every j [member of] {[j.sub.1], [j.sub.2],... ,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]}, the only path with length at most k joining [u'.sub.i] and s([v.sub.i,j]) in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [u'.sub.i]P[v.sub.i,j]Ps([v.sub.i,j]), and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has to be a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belongs to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every j [member of] {[j.sub.1], [j.sub.2],... ,[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]} assuming that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belongs to the orientation. The claim follows analogously from the assumption that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. []

Claim 2. Suppose k is even, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an hyper edge of H. Then, in any good orientation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipathfor every i [member of] {[i.sub.1], [i.sub.2], [i.sub.3]}. Furthermore, these three dipaths cannot be all directed from or towards the s([v.sub.i,j])'s.

Proof: Recall that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] when k is even. Note further that there are only two paths with length at most k joining any two of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. These include [a.sub.j] and [a'.sub.j], respectively. If the statement of the claim is not fulfilled, then there is no k-dipath of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] joining any two of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] including [a.sub.j]. So there must be three k-dipaths joining these vertices including [a'.sub.j], but this is impossible. []

Claim 3. Suppose k is odd, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an hyperedge of H. Then, in any good orientation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], either [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a dipathfor every i [member of] {[i.sub.1], [i.sub.2], [i.sub.3]}. Besides these three dipaths cannot be all directed from or towards the s([v.sub.i,j])'s.

Proof: Similarly as for previous Claim 2, if the statement of the claim is not fulfilled by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then there is no dipath with length at most k joining any two of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] including the s([v.sub.i,j])'s. Then there cannot be three k-dipaths, including the s'([v.sub.i,j])'s, joining every pair of these vertices, and this no matter how the paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are oriented, and how the edges of the cycles [a.sub.j][b.sub.j][c.sub.j][a.sub.j] and [a'.sub.j][b.sub.j]'[c'.sub.j][a'.sub.j] are oriented. []

Regarding previous Claims 2 and 3, remark that if two of the dipaths obtained by orienting the paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have the same direction, i.e. from or towards the s([v.sub.i,j])'s, while the third one is oriented in the opposite direction, then we can obtain three k-dipaths joining any two of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Suppose e.g. that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are dipaths of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So far, note that there are two k-dipaths starting from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively, and ending at [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (when k is odd, these are obtained by adding [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to E([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII])). The last k-dipath starting from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and ending at [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be obtained e.g. by orienting the edges of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in such a way that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are dipaths, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an arc when k is odd.

According to Claims 1, 2 and 3, we have an equivalence between finding a proper 2-vertex-colouring of H and a good orientation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Indeed, assume that having the dipath [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (resp. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) in an orientation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] simulates that vertex [x.sub.i] of H is coloured blue (resp. red), and that having the dipath [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] simulates the fact that the vertex xi is counted as a blue (resp. red) vertex in [E.sub.j]. Claim 1 reflects the fact that if [x.sub.i] is coloured, say, blue by a proper 2-vertex-colouring of H, then xi counts as a blue vertex in every hyperedge which contains it. Claims 2 and 3 depict the fact that all vertices from a single hyperedge of H cannot have the same colour. Thus, by the discussion following the proof of Claim 3, it can be concluded that from a proper 2-vertex-colouring of H we can deduce a good orientation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and vice-versa.

We now augment GH with additional vertices so that there is a path with length at most k joining every two non-adjacent vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that do not form a representative pair. This is done in such a way that there is an orientation of the edges of E ([G.sub.H] ) - E ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) so that every two vertices of [G.sub.H] that do not form a representative pair are joined by a dipath with length at most k. In this way, the existence of a k-weak orientation of [G.sub.H] will only rely on the existence of a good orientation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 2 OMITTED]

The augmentation consists in associating a gadget [G.sub.v] with each vertex v of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and then connecting all the resulting gadgets in such a way there is a path with length at most k between any two vertices from different gadgets [G.sub.u] and [G.sub.v]. In the case where {u, v} is not a representative pair, we add a shortcut between [G.sub.u] and [G.sub.v], i.e. an alternative shorter path for joining two vertices of [G.sub.u] and [G.sub.v]. This is done in such a way that every vertex u' of [G.sub.u] is at distance at most k from any vertex v' of [G.sub.v], unless u' = u, v' = v and {u, v} is a representative pair. However, in the situation where {u, v} is not representative, there is a path with length k joining u and v that uses the shortcut between [G.sub.u] and [G.sub.v].

Set x = [k/2]. For every i [member of] {1, 2,... ,x}, add two new vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [G.sub.v]. These two vertices form the ith level of [G.sub.v], and are said tobe i-vertices. Next, for every i [member of] {1,2,... ,x- 1}, add all possible edges between the i- and (i + 1)-vertices of [G.sub.v] so that two consecutive levels of [G.sub.v] form a clique on 4 vertices. Finally, add an edge between v and every 1-vertex of [G.sub.v].

We finish the construction of [G.sub.H] by adding some connection between the gadgets. We distinguish two cases depending on the parity of k:

* If k is even, then turn the subgraph induced by all x-vertices of [G.sub.H] into a clique. Next, for every pair {u, v} of vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is not representative, add a shortcut vertex [e.sub.u,v] to the clique constructed just before. Finally, add every edge between [e.sub.u,v] and the vertices from the (x - 1)th levels of [G.sub.u] and [G.sub.v] if k [greater than or equal to] 4, or the edges u[e.sub.u,v] and [e.sub.u,v]v when k = 2.

* Otherwise, if k is odd, then add a new vertex z to [G.sub.H], and add all possible edges between z and x-vertices. For every pair {u, v} of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] that is not representative, also add the shortcut edges [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [G.sub.H].

This construction is illustrated in Figure 2 for k = 6 and k = 7. Note that no new path with length at most k joining two vertices composing a representative pair of GH arose from the modifications. Therefore, the equivalence between finding a proper 2-vertex-colouring of H and a good orientation of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is preserved. The last thing to do, is showing that there is an orientation of the edges we have just added so that every pair of vertices of [G.sub.H] which is not representative is joined by a k-dipath in either direction.

Define an arbitrary ordering [sigma] = ([v.sub.1], [v.sub.2],..., [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) over all vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and consider the following partial orientation of [G.sub.H] (see Figure 2). First, for every vertex v of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be arcs. Then, for every level i [member of] {1,2,..., x} of [G.sub.v], let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an arc. Next, for every i [member of] {1,2,..., x - 1}, add the arcs [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to the partial orientation. The partial orientation is completed depending on the parity of k:

* If k is even, then, for every shortcut vertex e of [G.sub.H], let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be arcs. Next, for every i < j, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be arcs of the partial orientation. Additionally, if {[v.sub.i], [v.sub.j] } is not a representative pair, then let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be arcs if k [greater than or equal to] 4, or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be arcs when k = 2.

* If k is odd, then let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be arcs. Finally, if {[v.sub.i], [v.sub.j]} is not representative, then let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be arcs.

Note that, under the partial orientation given above, any vertex u' from a gadget [G.sub.u] can directly "access" the upper or lower level of [G.sub.u]. Besides, there is a dipath with length at most k joining u' and any vertex v' from another gadget [G.sub.v], unless u' = u, v' = v, and {u, v} is a representative pair. Such a path typically goes up across [G.sub.u], then exits [G.sub.u] to enter [G.sub.v] (either directly from the xth levels or via z), and finally goes down across [G.sub.v]. Because the gadgets have x = [k/2] levels, the length of such a path does not exceed k. Finally observe that if {u, v} is representative, then there is no path with length at most k joining u and v going across the gadgets. On the contrary, if {u, v} is not a representative pair, then there is a path with length exactly k joining u and v. This path necessarily includes the shortcut between [G.sub.u] and [G.sub.v], i.e. the vertex [e.sub.u,v] if k is even or an edge linking the xth levels of [G.sub.u] and [G.sub.v] otherwise.

Hence, [G.sub.H] admits a k-weak orientation if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] admits a good orientation. Besides, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] admits a good orientation if and only if H is 2-colourable. By transitivity, we get that [G.sub.H] admits a k-weak orientation if and only if H is 2-colourable, and thus that k-WEAK ORIENTATION is NP-complete. []

3 Strong orientations

We herein consider the following strong analogues of WEAK ORIENTATION and k-WEAK ORIENTATION.

STRONG ORIENTATION

Instance: A graph G.

Question: Does G admit a strong orientation?

k -STRONG ORIENTATION

Instance: A graph G.

Question: Does G admit a k -strong orientation?

Using Theorems 1 and 2, we can answer to every instance G of STRONG ORIENTATION in linear time via the following algorithm. Clearly, if G has bridges, then it admits no strong orientation. Otherwise, a strong orientation can be obtained according to Theorem 2. All these steps can be achieved in linear time, so the whole algorithm indeed runs in linear time.

Theorem 6. STRONG ORIENTATION is in P.

Clearly, no instance of 1-STRONG ORIENTATION is positive since we consider oriented graphs only (no symmetric arc is allowed). So 1-STRONG ORIENTATION is trivially in P. Besides, it was proved by Chvatal and Thomassen that 2-STRONG ORIENTATION is NP-complete in general (see [1]). For the other values of k [greater than or equal to] 3, we strongly believe that the NP-completeness of the remaining problems could be proved by slightly modifying the reduction scheme given in the proof of Theorem 5. Namely, consider e.g. the following modifications. First, the crux graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] would be obtained in the same way. Then, when constructing the big clique subgraph (which would be intended to have the same purpose, namely to have a lot of pairs of vertices being joined by a lot of paths with length at most k), one would have to make sure that the following additional paths exist:

* at least two new paths with length k joining the vertices from every non-representative pair;

* one new path with length k joining the vertices from every representative pair.

Then note that if these modifications are performed, then, in order to get a strong orientation of [G.sub.H], for every representative pair {u, v}, we would need to have the path of length k joining u and v in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] being oriented, say, from u to v, and the additional path (of the clique subgraph) oriented from v to u. The hard part would be to make sure that the clique subgraph can be always oriented correctly (as in the second part of the proof of Theorem 5), but this should be doable due to its large number of paths with length at most k (basically the clique subgraph could be less dense in the original construction, but its large size facilitates the proof process).

4 Discussion

In this paper, we have considered the complexity of orienting an undirected graph in such a way that the distances between its vertices are preserved. As a main result, we have proved the same result as Chvatal and Thomassen for weak orientations, hence proving that the weak and strong versions of all these problems are theoretically as hard as each other in essence.

It is worth mentioning that Theorem 5 has consequences on some special vertex-colouring problems. These consequences are related to the following context. Usually, a proper vertex-colouring of an undirected graph G is an assignment of colours to its vertices such that no two adjacent vertices receive the same colour. It is well-known that extremal graphs for the notion of proper vertex-colouring (i.e. the graphs which need the most colours to be coloured, relatively to their order) are complete graphs. But for augmented kinds of graphs and vertex-colourings, the notion of extremal graph is not as obvious. It turns out that the NP-completeness of every problem k-WEAK ORIENTATION (in particular for k = 2) implies that, in some contexts, an easy characterization of these extremal graphs in terms of underlying undirected graph cannot exist (unless P=NP).

4.1 Oriented vertex-colouring of oriented graphs

Let [??] be an oriented graph. An oriented vertex-colouring of [??] is a vertex-colouring c satisfying the following two properties:

* for every two adjacent vertices u and v, we have c(u) [not equal to] c(v),

* for every two arcs [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], if c(x) = c(v) then c(y) [not equal to] c(u).

We call [??] an oriented clique if it does not admit an oriented vertex-colouring using strictly less than |V([??])| colours. It is known that [??] is an oriented clique if and only if every two vertices of [??] are at weak distance at most 2, i.e. [??] is 2-weak, see e.g. [3, 4]. From the undirected graphs point of view, the case k = 2 of Theorem 5 hence implies the following.

Corollary 7. It is NP-complete to decide whether an undirected graph G is the underlying graph of an oriented clique.

4.2 Proper vertex-colouring of 2 -edge-coloured graphs

A 2-edge-coloured graph G = (V,[E.sub.r],[E.sub.b]) (sometimes also called a signified graph) is basically an undirected graph whose each edge is either red (i.e. in [E.sub.r]) or blue (i.e. in [E.sub.b]), refer e.g. to [7, 9] for more details. A proper vertex-colouring of G is then a vertex-colouring c such that:

* for every two adjacent vertices u and v, we have c(u) [not equal to] c(v),

* for every red edge xy and blue edge uv, if c(x) = c(u) then c(y) [not equal to] c(v).

Similarly as in the previous section, in case G cannot be properly vertex-coloured with strictly less than |V(G)| colours, we call G a 2-edge-coloured clique. According to the definition, G is a 2-edge-coloured clique if and only if every two of its vertices are either adjacent, or joined by a path of length 2 whose one edge is red and the other one is blue (see notably [9] for more details). Actually the reduction given in the proof of Theorem 5 can be modified to prove the following, which is equivalent to a result that appeared in [2].

Corollary 8. It is NP-complete to decide whether an undirected graph G is the underlying graph of a 2-edge-coloured clique.

The modifications are mainly the following. Instead of orienting the edges of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (and [G.sub.H]), we now basically want to colour each of them either red or blue. The reduced crux graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] remains the same. A colouring of the edges of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is good if, for every representative pair {u, v} of vertices, the unique path with length 2 joining u to v has one red edge and one blue edge. Then it can be easily checked that the cornerstone property of overlapping unique short paths remains applicable in this context. Namely, in a good 2-edge-colouring, colouring the edges of a unique path with length 2 in the crux "forces" the colouring of other unique paths overlapping it. The rest of the reduction, i.e. the construction of GH from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is similar.

Acknowledgements

The authors would like to thank Prof. Eric Sopena for bringing the problem investigated in this paper to their attention, and for his valuable comments on the first drafts of this paper. Thanks are also due to the referees for their constructive comments and suggestions. The first author was supported by ERC Advanced Grant GRACOL, project no. 320812.

References

[1] V. Chvatal and C. Thomassen. Distances in orientations of graphs. Journal of Combinatorial Theory, Series B, 24(1):61-75, 1978.

[2] A. Kemnitz and I. Schiermeyer. Graphs with rainbow connection number two. Discussiones Mathematicae Graph Theory, 31(2):313-320, 2011.

[3] W.F. Klostermeyer and G. MacGillivray. Analogues of cliques for oriented coloring. Discussiones Mathematicae Graph Theory, 24:373-387, 2004.

[4] A.V. Kostochka, T. Luczak, G. Simonyi and E. Sopena. On the minimum number of edges giving maximum oriented chromatic number. In Dimacs/Dimatia conference "Contemporary Trends in Discrete Mathematics", Stirin, Czech Republic, May 1997. Dimacs Series in Discrete Mathematics & Theorerical Computer Science, 49:179-182, 1999.

[5] L. Lovasz. Coverings and coloring of hypergraphs. In Proceedings of the 4th South-Eastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, page 3-12, 1973.

[6] A. Nandy, S. Sen and E. Sopena. Outerplanar and planar oriented cliques. To appear in Journal of Graph Theory.

[7] R. Naserasr, E. Rollova and E. Sopena. Homomorphisms of signed graphs. Journal of Graph Theory, 79(3):178-212, 2015.

[8] H.E. Robbins. A theorem on graphs, with an application to a problem in traffic control. American Mathematical Monthly, 46:281-283, 1939.

[9] S. Sen. A contribution to the theory of graph homomorphisms and colorings. Ph.D. thesis, University of Bordeaux, 2014.

[10] E. Sopena. Complete oriented colourings and the oriented achromatic number. Discrete Applied Mathematics, 173:102-112, 2014.

[11] R.E. Tarjan. A note on finding the bridges of a graph. Information Processing Letters, 2:160-161, 1974.

Julien Bensmail (1) Romaric Duvignau (2) Sergey Kirgizov (3)

(1) Technical University of Denmark, Denmark

(2) Universite de Bordeaux, LaBRI, UMR 5800, CNRS, France

(3) Universite de Bourgogne Franche-Comte, LE2I, UMR 6306, CNRS, France

received 18th Sep. 2014, accepted 15th Jan. 2016.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Bensmail, Julien; Duvignau, Romaric; Kirgizov, Sergey
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:6757
Previous Article:Avoiding patterns in irreducible permutations.
Next Article:Edge-partitioning graphs into regular and locally irregular components.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters