In this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the pathwidth @math and the profile @math of the input graph @math . We prove that for an arbitrary graph @math and an integer @math , there exists an interval supergraph @math of @math such that for its clique number it holds @math and the number of its edges is bounded by @math . In other words, the pathwidth and the profile of a graph can be simultaneously minimized within the factors of @math (plus a small constant) and @math , respectively. Note that for a fixed @math , both upper bounds provide constant factor approximations. On the negative side, we show an example that proves that, for some graphs, there is no solution in which both parameters are optimal. In case of finding a chordal supergraph, the two corresponding graph parameters that reflect its clique size and number of edges are the treewidth and fill-in. We obtain that the treewidth and the fill-in problems are also orthogonal' in the sense that for some graphs, a solution that minimizes one of those parameters cannot minimize the other. As a motivating example, we recall graph searching games which illustrates a need of simultaneous minimization of these pairs of graph parameters.
We point out several optimization problems in which pathwidth or treewidth is paired with another parameter or with additional conditions that need to be satisfied. For an example consider a problem of computing a path decomposition with restricted width and length (defined as the number of bags in the path decomposition). It has been first studied in @cite_1 as a problem motivated by an industrial application and called the but finds applications also in scheduling a register allocation @cite_11 or graph searching games @cite_8 .
@cite_8 @cite_1 @cite_11
2763773774 1573106092 2056304107
We consider a bicriterion generalization of the pathwidth problem: given integers k , l and a graph G, does there exist a path decomposition of G of width at most k and length (i.e., number of bags) at most l? We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter tractable with respect to k, the generalized problem is NP-complete for any fixed k ? 4 , and also for any fixed l ? 2 . On the other hand, we give a polynomial-time algorithm that constructs a minimum-length path decomposition of width at most k ? 3 for any disconnected input graph. As a by-product, we obtain an almost complete classification for connected graphs: the problem is NP-complete for any fixed k ? 5 , and polynomial for any k ? 3 . We consider graphs of pathwidth k and focus on minimum-length path decompositions.We give a polynomial-time algorithm for k ? 3 .The problem is NP-hard for k ? 4 .The problem is NP-hard even for connected graphs for k ? 5 .The complexity for connected graphs with k = 4 remains open. This paper reviews structural problem decomposition methods, such as tree and path decompositions. It is argued that these notions can be applied in two distinct ways: Either to show that a problem is efficiently solvable when a width parameter is fixed, or to prove that the unrestricted (or some width-parameter free) version of a problem is tractable by using a width-notion as a mathematical tool for directly solving the problem at hand. Examples are given for both cases. As a new showcase for the latter usage, we report some recent results on the Partner Units Problem, a form of configuration problem arising in an industrial context. We use the notion of a path decomposition to identify and solve a tractable class of instances of this problem with practical relevance. The search for efficient register allocation algorithms dates back to the time of the first FORTRAN compiler for the IBM 704. The model we use in this paper is a single processor with an arbitraril...