Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

Tackling the jump number of interval orders

Although the jump number problem for partially ordered sets in NP-complete in general, there are some special classes of posets for which polynomial time algorithms are known.Here we prove that for the class of interval orders the problem remains NP-complete. Moreover we describe another 3/2-approximation algrithm (two others have been developed already by Felsner and Syslo, respectively) by using a polynomial time subgraph packing algorithm.     

A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders

Let L=u ₁ , u ₂ , ..., u _k be a linear extension of a poset P. Each pair (u _i , u _i+1 ) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases.     

On the maximum cardinality search lower bound for treewidth

The Maximum Cardinality Search (MCS) algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbours becomes visited. A maximum cardinality search ordering (MCS-ordering) of a graph is an ordering of the vertices that can be generated by the MCS algorithm. The visited degree of a vertex v in an MCS-ordering is the number of neighbours of v that are before v in the ordering. The visited degree of an MCS-ordering ψ of G is the maximum visited degree over all vertices v in ψ. The maximum visited degree over all MCS-orderings of graph G is called its maximum visited degree. Lucena [A new lower bound for tree-width using maximum cardinality search, SIAM J. Discrete Math. 16 (2003) 345-353] showed that the treewidth of a graph G is at least its maximum visited degree.We show that the maximum visited degree is of size O(logn) for planar graphs, and give examples of planar graphs G with maximum visited degree k with O(k!) vertices, for all k∈N. Given a graph G, it is NP-complete to determine if its maximum visited degree is at least k, for any fixed k?7. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete.In this paper, we also propose some heuristics for the problem, and report on an experimental analysis of them. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.     

On minimizing the jump number for interval orders

The purpose of this paper is to give an effective characterization of all interval orders which are greedy with respect to the jump number problem.This research (Math/1406/30) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Regressions and monotone chains: A ramsey-type extremal problem for partial orders

Aregression is a functiong from a partially ordered set to itself such thatg(x)≦x for allz. Amonotone k-chain is a chain ofk elementsx ₁<x ₂ <...<x _k such thatg(x ₁)≦g(x ₂)≦...≦g(x _k ). If a partial order has sufficiently many elements compared to the size of its largest antichain, every regression on it will have a monotone (k + 1)-chain. Fixingw, letf(w, k) be the smallest number such that every regression on every partial order with size leastf(w, k) but no antichain larger thanw has a monotone (k + 1)-chain. We show thatf(w, k)=(w+1) ^k . Dedicated to Paul Erdős on his seventieth birthday Research supported in part by the National Science Foundation under ISP-80-11451.     

On finding the jump number of a partial orber by substitution decomposition

Consider the linear extensions of a partial order. A jump occurs in a linear extension if two consecutive elements are unrelated in the partial order. The jump number problem is to find a linear extension of the ordered set which contains the smallest possible number of jumps. We discuss a decomposition approach for this problem from an algorithmic point of view. Based on this some new classes of partial orders are identified, for which the problem is polynomially solvable.     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

Crowns,cutsets, and valuable partial orders

We consider the problem of recognizing those partial orders which admit a valuation: this is a linear-algebraic condition which arises naturally in an algebraic/geometric context. We show that a partial order has at most one valuation (which is integer-valued) and present various structural conditions which are either necessary or sufficient for a partial order to be valuable. The first main result is a reduction theorem which allows us to restrict attention to those partial orders which do not have a bounded cutset. We use this and a theorem of Kelly and Rival to prove the second main result: that every contraction of a bounded partial order is fibre-valuable if and only if the partial order is a dismantlable lattice. This result has a geometric interpretation.This research was supported by the Natural Sciences and Engineering Research Council of Canada under operating grant OGP0105392.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

Asymptotic enumeration ofN-free partial orders

LetN(n) andN ^* (n) denote, respectively, the number of unlabeled and labeledN-free posets withn elements. It is proved thatN(n)=2 ^{n logn+o(n logn)} andN ^*(n)=2^{2n logn+o(n logn)}. This is obtained by considering the class ofN-free interval posets which can be easily counted.     

On the complexity of diagram testing

In 1987, Neetil and Rödl [4] claimed to have proved that the problem of finding whether a given graphG can be oriented as the diagram of a partial order is NP-complete. A flaw was discovered in their proof by Thostrup [11]. Neetil and Rödl [5] have since corrected the proof, but the new version is rather complex. We give a simpler and more elementary proof, using a completely different approach.     

Simultaneous representation of interval and interval-containment orders

We characterize the polysemic interval pairs—pairs of posets that admit simultaneous interval and interval-containment representations—and present algorithms to recoginze them and construct polysemic interval representations.This work, supported in part by NSF grant CCR-9300079, also appears in the author's doctoral thesis [9], written at the Johns Hopkins University under the supervision of Professors Edward R. Scheinerman and Michael T. Goodrich.     

A linear-time algorithm for edge-disjoint paths in planar graphs

In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n ^5/3(loglogn)^1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability.     

Minimizing the jump number for partially ordered sets: A graph-theoretic approach

The purpose of this paper is to present a graph-theoretic approach to the jump number problem for N-free posets which is based on the observation that the Hasse diagram of an N-free poset is a line digraph. Therefore, to every N-free poset P we can assign another digraph which is the root digraph of the Hasse diagram of P. Using this representation we show that the jump number of an N-free poset is equal to the cyclomatic number of its root digraph and can be found (without producing any linear extension) by an algorithm which tests if a given poset is N-free. Moreover, we demonstrate that there exists a correspondence between optimal linear extensions of an N-free poset and spanning branchings of its root digraph. We provide also another proof of the fact that optimal linear extensions of N-free posets are exactly greedy linear extensions. In conclusion, we discuss some possible generalizations of these results to arbitrary posets.     

Equivariant closure operators and trisp closure maps

A trisp closure map ? is a special map on the vertices of a trisp (triangulated space) T with the property that T collapses onto the subtrisp induced by the image of ?. We study the interaction between trisp closure maps and group operations on the trisp, and give conditions such that the quotient map is again a trisp closure map. Special attention is on the case that the trisp is the nerve of an acyclic category, and the relationship between trisp closure maps and closure operators on posets is studied.     

Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

Random orders

Letk andn be positive integers and fix a setS of cardinalityn; letP _k (n) be the (partial) order onS given by the intersection ofk randomly and independently chosen linear orders onS. We begin study of the basic parameters ofP _k (n) (e.g., height, width, number of extremal elements) for fixedk and largen. Our object is to illustrate some techniques for dealing with these random orders and to lay the groundwork for future research, hoping that they will be found to have useful properties not obtainable by known constructions.Supported by NSF grant MCS 84-02054.     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.