We study the problem of computing an -orientation of a graph with at most transitive edges, which was recently proven to be NP-hard already when = 0. We strengthen this result by showing that the problem remains NP-hard even for graphs of bounded diameter, and for graphs of bounded vertex degree. These computational lower bounds naturally raise the question about which structural parameters can lead to tractable parameterizations of the problem. Our main result is a fixed-parameter tractable algorithm parameterized by treewidth.
20
10==s
(b)
recall that an edge is transitive if the digraph contains a path directed from to ; for
example, the bold (red) edges in Fig. 1c are transitive. Besides being of theoretical interest,
such orientations, when they exist, can be used to compute readable and compact drawings
of graphs [
Contribution. We study the parameterized complexity of finding -orientations with few
transitive edges. More formally, given a graph and an integer , the st-Orientation problem
asks for an -orientation of with at most transitive edges. This problem is para-NP-hard
by the natural parameter [
For space reasons, many proofs have been omitted, see [
Output: An -orientation of such that the resulting digraph () contains at most transitive edges.
In what follows, for a graph = (, ), the pair ( , ) denotes a nice tree-decomposition of ,
such that = {}∈[ℓ] is a collection of subsets of vertices of , called bags, and is a tree
whose nodes are in one-to-one correspondence with the elements of . The width of ( , ) is
maxℓ=1 || − 1, while the treewidth of , denoted by tw(), is the minimum width over all
(not necessarily nice) tree-decompositions of . Refer to [
We provide a fixed-parameter tractable algorithm for st-Orientation parameterized by treewidth. In fact, the algorithm we propose can solve a slightly more general problem. Namely, it does not assume that and are part of the input, but it looks for an -orientation in which the source and the sink can be any pair of vertices of the input graph. However, if and are prescribed, a simple check can be added to the algorithm (we will highlight the crucial point in which the check is needed) to ensure this property. Let = (, ) be an undirected graph. A solution of the st-Orientation problem is an orientation of such that () is an -graph with at most transitive edges. Let ( , ) be a nice tree-decomposition of of width . For a bag ∈ , we denote by [] the subgraph of induced by the vertices of , and by the subtree of rooted at . Also, we denote by the subgraph of induced by all the vertices in the bags of . We adopt a dynamic-programming approach performing a bottom-up traversal of . The solution space is encoded into records associated with the bags of , which we describe in the next section.
Encoding solutions. Let be a solution and consider a bag . The record of that encodes is the interface of the solution with respect to . For ease of notation, the restriction of () to is denoted by , and similarly the restriction to [] is []. Record stores the following information.
• is the orientation of []. • is the subset of the edges of [] that are transitive in (). We call such edges admissible transitive edges or simply admissible edges. The edges of not in are called non-admissible. • is the set of ordered pairs of vertices (, ) such that: (i) , ∈ , and (ii) contains the path ⇝ . • ℱ is the set of ordered pairs of vertices (, ) such that: (i) , ∈ , and (ii) connecting to with a directed path makes a non-admissible edge of to become transitive. • ≥ | | is the cost of , i.e., the number of transitive edges in . • maps each vertex ∈ to a Boolean value () that is true if and only if is a source in . Analogously, maps each vertex ∈ to a Boolean value () that is true if and only if is a sink in . • is a flag that indicates whether () contains a source that belongs to but not to . Analogously, is a flag that indicates whether () contains a sink that belongs to but not to .
Observe that diferent solutions and ′ of may be encoded by the same record , we call and ′ equivalent. This defines an equivalent relation on the set of solutions for , and each record represents an equivalence class. The algorithm incrementally constructs the set of records (i.e., the quotient set) for each bag rather than the whole set of solutions. More formally, for each bag ∈ , we associate a set of records ℛ = {1, ..., ℎ}. The next lemma follows. Lemma 1 The cardinality of ℛ is 2(2), and each record has size (2).
Informal description of the algorithm. Let be the current bag visited by the algorithm. We compute the records of based on the records computed for its child or children (if any). If the set of records of a bag is empty, the algorithm halts and returns a negative answer. We distinguish four cases based on the type of the bag . Observe that, to index the records within ℛ, we added a superscript ∈ [ℎ] to each record, and we will do the same for all the record’s elements. To begin with, if is a leaf bag, we have that is the empty set and ℛ consists of only one record, i.e., ℛ = {1 = ⟨∅, ∅, ∅, ∅, 0, ∅, ∅, false, false⟩}. is an introduce bag. Let = ∖ {} be the child of . Initially, ℛ = ∅. Next, the algorithm exhaustively extends each record ∈ ℛ to a set of records of ℛ as follow. Let be the set of all the possible orientations of the edges incident to in [], and similarly let be the set of all the possible subsets of the edges incident to in []. The algorithm considers all possible pairs (, ) such that ∈ and ∈ . For each pair (, ), we proceed as follows.
1. Let = |ℛ| + 1, the algorithm computes a candidate orientation of [] starting from and orienting the edges of according to . 2. Similarly, it computes the candidate set of admissible edges starting from and adding to it the edges in . 3. Next, it sets the candidate cost = + ||. 4. Let the extension ⟨, , ⟩ be valid if: a) ≤ ; b) there is no pair (, ) ∈ so that , ∈ []; c) there is no pair (, ) ∈ so that , ∈ []. Clearly, if an extension is not valid, the corresponding record cannot encode any solution, hence the algorithm discards the extension and continues with the next pair (, ). Otherwise, we =comp. ute the record = ⟨, , , ℱ, , , , , ⟩ of ℛ, where = , 5. To complete the record , it remains to compute , , and ℱ. We omit a formal description. At high level, and can be easily computed by inspecting the vertices in and . For , we simply recompute the paths from scratch. For ℱ, we observe that the addition of might have created new pairs of vertices that should belong to ℱ , hence we identify such pairs and compute ℱ accordingly. is a forget bag. Let = ∪ {} be the child of . The algorithm computes ℛ by exhaustively merging records of ℛ as follow.
1. For each ∈ ℛ , we remove from and all the edges incident to and from and ℱ all the pairs where one of the vertices is . Due to this operation, there may be records that are identical except possibly for their costs, we only keep the one whose cost is no larger than any other record. 2. Let be a record of ℛ that was not discarded by the procedure above. If () ∧ , we discard (because the orientation would contain two sources), else we set = true (because is a source). Similarly, if () ∧ , we discard , else we set = true. At this point, if the record has not been discarded yet and vertices and are prescribed, we can add the following check. If () ∧ , then is a source, hence if ̸= , we discard the record. Analogously, if () ∧ , then is a sink, hence if ̸= , we discard the record. Next, we remove from and the values () and (). 3. All the records that have not been discarded and have been updated according to the above procedure are added to ℛ. is a join bag. This case is omitted for space reasons.
It is possible to prove that graph admits a solution for st-Orientation if and only if the algorithm terminates after visiting the root of .
Theorem 1 Given an input graph = (, ) of treewidth and an integer ≥ 0, there is an algorithm that either finds a solution of st-Orientation or reject the input in time 2(2) · .
We first recall the special case of st-Orientation studied in [
Non-Transitive st-Orientation (NT-st-Orientation) Input: An undirected graph = (, ), and two vertices , ∈ .
Output: An non-transitive -orientation of such that vertices and are the source and sink of (), respectively.
In the hardness proof of NT-st-Orientation in [