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.
The treewidth counterpart of the length' minimization problem can be defined two-fold. It can be seen as minimizing, besides of the width of a tree decomposition, the number of its bags @cite_2 . On the other hand, minimization of width and the diameter of the underlying tree-structure of the decomposition has been studied in @cite_13 @cite_27 .
@cite_27 @cite_13 @cite_2
1518294493 1836127928 1574061374
Motivated by applications in parallel and dynamic graph algorithms, we investigate the tradeoff between width and diameter of tree decompositions. For all integers n, k and K with 1 ≤ k ≤ K ≤ n− 1, denote by D(n, k, K) the maximum, over all n-vertex graphs G of treewidth k, of the smallest diameter of a tree decomposition of G of width K. We determine D(n, k, K), up to a constant factor, for all values of n, k and K. When K is bounded by a constant (the case of greatest practical relevance), D(n, k, K) is θ(n) for K ≤ 2k-1, θ(√n) for 2k ≤ K ≤ 3k−2, and θ(log n) for K ≥ 3k−1. We provide much more accurate bounds for the case K ≤ 2k−1. In this paper we give a parallel algorithm for recognizing graphs with treewidth ≤ k, for constant k, and building the corresponding tree-decomposition, that uses O(log n) time and O(n3k+4) processors on a CRCW PRAM. Also, we give a parallel algorithm that transforms a given tree-decomposition of a graph G with treewidth k to another tree-decomposition of G with treewidth ≤ 3k+2, such that the tree in this tree-decomposition is binary and has logarithmic depth. The algorithm uses a linear number of processors and O(log n) time. Many NP-complete graph problems are known to be solvable in polynomial time, when restricted to graphs with treewidth ≤ k, k constant. From the results in this paper, it follows that most of these problems are also in NC, when restricted to graphs with treewidth bounded by a constant. Tree-decompositions are the cornerstone of many dynamic programming algorithms for solving graph problems. Since the complexity of such algorithms generally depends exponentially on the width (size of the bags) of the decomposition, much work has been devoted to compute tree-decompositions with small width. However, practical algorithms computing tree-decompositions only exist for graphs with treewidth less than 4. In such graphs, the time-complexity of dynamic programming algorithms is dominated by the size (number of bags) of the tree-decompositions. It is then interesting to minimize the size of the tree-decompositions. In this extended abstract, we consider the problem of computing a tree-decomposition of a graph with width at most k and minimum size. We prove that the problem is NP-complete for any fixed k ≥ 4 and polynomial for k ≤ 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs.