{'fraction_non_alphanumeric': 0.061868490595367635, 'fraction_numerical': 0.008238768848126845, 'mean_word_length': 3.846327683615819, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algorithms For Longest Chains In Pseudo- Transitive Graphs

A directed acyclic graph G = (V, E) is pseudo-transitive with respect to a given subset of edges E1, if for any edge ab in E1 and any edge bc in E, we have ac in E. We give algorithms for computing longest chains and demonstrate geometric applications that unify and improves some important past results. (For specific applications see the introduction.)


Introduction and Summary
The notation of an "ordering" naturally arises in many problems of combinatorial and computational geometry [8] and the underlying structures usually exhibit some sorts of "weak transitivity" properties. However, in many cases the crucial properties of these problem can not be categorized by the classical theory of partially ordered sets [5,9]. Motivated by geometric problems we introduce here the concept of "pseudo-transitivity" in the directed acyclic graphs. We derive algorithms for computing the longest chains under certain pseudotransitivity assumptions, and demonstrate their applications in computing the maximum independent sets in the intersection graph of geometric objects.
The remaining of this section contains crucial definitions and the descriptions of the results. Throughout this paper, G=(V, E) is a directed acyclic graph with |V|=n and |E|=m. A chain in G is a directed path C: ! , ! , ..., ! , k ≥ 1 so that for any 1 ≤ i < j ≤ k, aiaj ∈ E. It is important to note that there is a one-to-one correspondence between the chains in G and the cliques in the undirected graph obtained from G by ignoring the direction of the edges, since G is acyclic. An anti-chain in G is an independent set of vertices in G. Let ω(G) and α(G) denote the largest number of vertices in any chains and in any antichains of G, respectively. A set C of chains (antichain) covers V, if every vertex in V is located on exactly one chain (antichain) in C. Let χ(G) and β(G), denote respectively, the minimum number of antichains and the minimum number of chains that cover V. Observe that χ(G) and β(G) are the chromatic number and the clique cover number, respectively, of the undirected graph underlying G.
If E is partial order on V, that is if ab ∈ E and bc ∈ E implies that ac ∈ E, then G is called a transitive graph or a Poset. Dilworth's theorem [5] asserts that for any Poset G = (V, E), χ(G) = ω(G) and α(G) = β(G). Moreover, in this case low order polynomial time algorithms have been known for the problems of computing χ(G), ω(G), α(G) and β(G), which in general are NP −hard [7].
Let G = (V, E) and E1 ⊆ E with the property that for any a, b, c∈V, ab ∈E1 and bc∈E implies that ac∈E. Then we say G is pseudo-transitive with respect to E1, and write G = (V, E1, E). When the context is clear we say G=(V, E1, E) is pseudo-transitive. Note that by selecting E1=∅, any directed acyclic graph G becomes pseudo-transitive. However in this extreme case pseudo-transitivity becomes a useless property. Note further that if E1 = E, for a pseudo transitive graph G = (V, E1, E), then G = (V, E) is a transitive graph, that is, G is a Poset. To get a feeling about the geometric aspects of pseudo-transitivity consider the following example. Let P be a finite collection of bounded closed subsets of R k . Let P, Q ∈ P. We say that Q and P are disjoint, if P∩Q=∅, otherwise we say P and Q intersect. The intersection graph of P is an undirected graph with the vertex set P whose edges are intersecting (un-ordered) pairs of elements of P. Let h be a k-dimensional hyperplane in R k . We will construct a pseudo-transitive graph G( P,h) whose underling undirected graph is isomorphic to the complement of the intersection graph of P. With no loss of generality assume that the h is perpendicular to the x axis, if this is not the case, we can rotate the coordinate system so that this holds. Define the left most vertex of P∈P to be a vertex with the smallest x coordinate. We say that Q is disjoint from P , if P and Q are disjoint and the x coordinate of the leftmost vertex of P is smaller or equal to the x coordinate of a leftmost vertex of Q. Let P, Q ∈ P so that Q is disjoint from P . We say that P is to the left of Q, if there is hyperplane parallel to h that separates P from Q in R k so that P is located to the left of h, and Q is to the right of h, where right and left correspond to the positive and negative directions of the x axis, respectively. Theorem 1.1 There is directed pseudo-transitive graph G( P,h) = (P, E1,E) whose underlying undirected graph is isomorphic to the complement of the intersection graph of P.
Proof. Define E1 to be the set of all edges of form P Q, P, Q ∈ P so that P is to the left of Q. To construct E, consider the following simple algorithm. Let initially E=E1, and consider all disjoint pairs P, Q so that Q is disjoint from P , P Q∈ / E, and the x coordinate of the leftmost vertex of P is smaller that the x coordinate of leftmost vertex of Q. We include any such PQ in E. To finish the construction of E, consider all remaining disjoint pairs P, Q for which the x coordinate of the leftmost vertex of P equals to the x coordinate of leftmost vertex of Q. For any It is easy to verify that G P,h is acyclic, and that PQ∈E1 and QR ∈ E implies that PR ∈ E1. Moreover, PQ ∈ E iff the P and Q are disjoint, and hence G( P,h) is isomorphic to the complement of the intersection graph of P. ! Let G = (V, E1, E) be pseudo-transitive and denote by G1 and G2 the directed subgraphs of G with the vertex sets V, and the edges sets E1 and E2 = E − E1, respectively. Furthermore, let ω(G) and ω(G2) denote number of vertices in the longest chains of G and G2, respectively. In section two we show that for any pseudo-transitive G = (V,E1, E), ω(G) can be computed in O(ω(G2)n ω(G2 )+2 ) time. The algorithm has nice applications in graph drawing [4], and when applied to a collection on unit height axis parallel rectangles, its running time is slightly better than the original Dynamic Programing Algorithm of Agarwal, Kreveld, and, Suri [3]. Pach and Töröcsik [8], and others [10] studied extremal problems for disjoint line segments in the plane. They discovered that the "disjointness properties" for the line segments can be captured by the union of several partial orders that all act on the line segments. The work in [8] inspired us to study the pseudo-transitivity when both E1 and E−E1 are partial relations on V. In Particular we have shown in Theorem 2.3 that in this case ω(G) can be computed in O(nm) time. The result has interesting computational consequences when applied to well known problems relating to partial orders. See for instance, the work of Biro and Trotter on segments orders [2]. Specifically, we can compute a largest set Moreover, the algorithm also can be used for circle graphs [6] and gives an optimal disjoint (independent) set in O(n 3 ) time. Agarwal and Mustafa [1] have derived approximation and exact algorithms for maximum independent sets in much more general versions of planar line segments as well as convex objects. However, their algorithms when applied to the cases, discussed here, give weaker results.

Algorithms
We will view chains as sets of vertices.
To see this note that there is a vertex b ∈ C −{a} so that ab ∈ E1, and note that bc ∈ E for any c ∈C', since {C −{a}} ∪ C' is a chain. It follows that from pseudo-transitivity that ac ∈ E for any c∈C', verifying the claim in (i). For (ii), when C can not be extended to a larger chain, then clearly, ω (C)= |C|. To complete the proof of (ii) note that Once such a chain C is generated, all vertices adjacent to C are also generated and stored in the adjacency list format. Let C be a chain in G ω starting at x ∈ V , then degree of C in G ω is at most deg(x). Thus, once C is constructed it takes O(deg(x)ω(G2 )) to construct all chains C' generated by C and store them. It follows that adjacency list of the transition graph can be constructed in time and storage. This finishes the proof, since topological ordering of any acyclic graph can be done in a linear time of the input length. ! Let G = (V, E1, E) be pseudo-transitive so that both E1 and E − E1 are partial orders on V, then we call G strongly pseudo-transitive. Note that in this case ab∈E1 and bc∈E1 implies that ac∈E1, ab∈E −E1 and bc∈E −E1 implies that ac∈E −E1, and finally ab∈E1 and bc∈E − E1 implies that ac∈E. Our next result is that in a strongly pseudo-transitive graph a maximum weighted chain can be computed in low order polynomial time. For any x∈V, let cx denote the weight or the cost of vertex x. Let G = (V, E1, E) be strongly pseudo-transitive and let C: ! , ! , ...,a k , k ≥ 3 be a chain. We say that C is splitable, if there is a j, 2 ≤ j ≤ k − 1 so that for i = 1, 2, ..., j-1, aiaj ∈ E1. In this case a j is called a splitting element. We say C is degenerate if it is not splitable. (iii)-Let C = a1, a2, ..., ap, p ≥ 3 be a chain in G. If C is splitable, then there is an splitting element aj, 1 < j < p such that the chain C ' =aj, !!! , ..., ap is degenerate.
Proof. To prove (i), let ! ∈C1 and ! ∈C2, i, j= / t. We must show that ! ! ∈E. Clearly, ! ! ∈E1 and ! ! ∈E, then ! ! ∈E, proving the claim. For (ii), clearly, if for i=2, 3,..., p − 1, ! ! ∈E −E1, then C is degenerate. For converse note that for p = 3 the claim holds, and observe that for p ≥ 4, if C is degenerate, then ! , ! , ..., !!! is also degenerate and proceed by induction on p. For (iii) let j be the largest integer so that aj is a splitting element for C, and let C' be !!!, !!!, ..., a k . Assume to the contrary that C' is splitable, and let at, t > j be a splitting element for C', then at is also a splitting element for C contradicting the maximality of j. ! Remarks. Part (i) of the Lemma shows how to construct long chains from smaller ones. Part (ii) explores the structure of the degenerate cases.
We will need the following crucial terms and definitions, w h i c h will be used to design our dynamic programming algorithm. For any xy∈E, x, y ∈V , let ωx,y denote the cost of a maximum cost chain starting at x and terminating at y in G. Moreover, for any xy∈E1, x, y∈V , let !,! ! denote the cost of a maximum cost chain C from x to y so that for any element of z≠y of C, it holds that zy∈E1. Note that the cost of a maximum cost chain in G is the Maximum of all !,! . Let xy∈E, x, y∈V , and let ωx,y denote the maximum cost of a degenerate chain among those degenerate chains starting at x, and finishing at y. Finally, let x, y ∈ X so that xy∈E, and let !,! ! denote the maximum cost of a degenerate chain among those degenerate chains starting at x and y, so that for any element k ≠x, y of the chain, ky ∈ E1.
Theorem 2.2 let G = (V, E) be strongly pseudo-transitive, then, the following hold.
Proof. We prove the claim using Lemma 2.2 and distinguishing between the splitable and degenerate cases. Let C be the desirable chain. In (i) and (ii), the first expression inside of the first inner curly bracket applies when C is splitable , whereas the remaining expression applies when C is degenerate. For (iii) and (iv), the expression inside of the first inner curly bracket applies when C −{x} is separable and the expression inside of the second curly bracket applies when C −{x} is degenerate. In particular, for (iii) if C −{x} is splitable, Part (iii) of Lemma 2.2 applies and identifies, a splitting element t, and subchains C1 and C2 of C, C − {x} = C1 ∪ C2 so that C2 is degenerate. Note that xt∈E−E1, since C is degenerate. Moreover, C1 ∪ {x} must be degenerate, since otherwise C is splitable. Now assume for (iii) that C−{x} is degenerate, and let t be the starting vertex of C−{x} and observe that xt∈E −E1. Details of (iv) are similar to (iii). n The preceding Theorem allows to express the optimal values for "larger" problems in terms of optimal values for "smaller" problems, but one needs to formalize the notation of "small" and "large" Since G is acyclic, elements of V can be topologically ordered so that any x∈V is assigned an integer value π(x) in the range of 1 to n. Proof. Our algorithm is a dynamic programming algorithm, w h i c h uses the recurrence relations in Theorem 2.2. We will use both the adjacency matrix and also the adjacency list for the graph G. We first obtain a topological ordering of elements of V and compute π(x) for any x ∈ V in O(n + m) time. We first obtain a topological ordering of elements of V and compute π(x) for any x ∈ V in O(n + m) time. Initially, we will obtain a sorted list of edges xy ∈ E in the increasing order of π(y) − π(x).
We only compute the entries xy of these matrices for which xy∈ E in the increasing of π(y) − π(x) using the sorted list. Note that for any x ∈V there are deg(x) many y's for which ω's must be computed. Computing the LHS of recurrence relations in Theorem 2.2 can be done in O(deg(x)) time any fixed xy∈E.