the undirected graph formed by ignoring the orientations of the DAG described above must have pathwidth at most w. It is possible to test whether this is the case, using the known fixed-parameter-tractable algorithms for pathwidth, and if so to find a path-decomposition for the undirected graph, in linear time given the assumption that w is a constant. Once a path decomposition has been found, a topological ordering of width w (if one exists) can be found using dynamic programming, again in linear time. Linguistics describe an application of path-width in natural language processing. In this application, sentences are modeled as graphs, in which the vertices represent words and the edges represent relationships between words; for instance if an adjective modifies a noun in the sentence then the graph would have an edge between those two words. Due to the limited capacity of human short-term memory, Kornai and Tuza argue that this graph must have bounded pathwidth (more specifically, they argue, pathwidth at most six), for otherwise humans would not be able to parse speech correctly. Exponential algorithms Many problems in graph algorithms may be solved efficiently on graphs of low pathwidth, by using dynamic programming on a path-decomposition of the graph. For instance, if a linear ordering of the vertices of an n-vertex graph G is given, with vertex separation number w, then it is possible to find the maximum independent set of G in time On graphs of bounded pathwidth, this approach leads to fixed-parameter tractable algorithms, parametrized by the pathwidth. Such results are not frequently found in the literature because they are subsumed by similar algorithms parametrized by the treewidth; however, pathwidth arises even in treewidth-based dynamic programming algorithms in measuring the space complexity of these algorithms. The same dynamic programming method also can be applied to graphs with unbounded pathwidth, leading to algorithms that solve unparametrized graph problems in exponential time. For instance, combining this dynamic programming approach with the fact that cubic graphs have pathwidth n/6 + o(n) shows that, in a cubic graph, the maximum independent set can be constructed in time O(2n/6 + o(n)), faster than previous known methods. A similar approach leads to improved exponential-time algorithms for the maximum cut and minimum dominating set problems in cubic graphs, and for several other NP-hard optimization problems. See also Boxicity, a different way of measuring the complexity of an arbitrary graph in terms of