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.
Some more examples of very closely related two-criteria problems can be found in the graph searching games; see e.g. @cite_24 @cite_26 @cite_23 .
@cite_24 @cite_26 @cite_23
2027562075 2125583143 1511821218
Abstract Various parameters of graphs connected to sparse matrix factorization and other applications can be approximated using an algorithm of . that finds vertex separators of graphs. The approximate values of the parameters, which include minimum front size, treewidth, pathwidth, and minimum elimination tree height, are no more than O (log n ) (minimum front size and treewidth) and O (log 2 n ) (pathwidth and minimum elimination tree height) times the optimal values. In addition, we show that unless P = NP there are no absolute approximation algorithms for any of the parameters. We consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not exist in general. On the other hand, we provide a formula for the cost of clearing complete graphs. From our construction it follows that an ideal search strategy of a complete graph does exist and can be calculated efficiently. For general graphs G we give a polynomial-time O(logn)-approximation algorithm for finding minimum cost search strategies. We also prove that recontamination does not help to obtain minimum cost edge search strategies. In this paper we discuss algorithms that approximate the treewidth and pathwidth of cotriangulated graphs, permutation graphs and of cocomparability graphs. For a cotriangulated graph, of which the treewidth is at most k we show there exists an O(n2) algorithm finding a path-decomposition with width at most 3k+4. If G[π] is a permutation graph with treewidth k, then we show that the pathwidth of G[π] is at most 2k, and we give an algorithm which constructs a path-decomposition with width at most 2k in time O(nk). We assume that the permutation π is given. In this paper we also discuss the problem of finding an approximation for the treewidth and pathwidth of cocomparability graphs. We show that, if the treewidth of a cocomparability graph is at most k, then the pathwidth is at most O(k2), and we give a simple algorithm finding a path-decomposition with this width. The running time of the algorithm is dominated by a coloring algorithm of the graph. Such a coloring can be found in time O(n3).