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.
Pathwidth or treewidth parameters have been also studied with additional constraints which can be most generally stated as requiring certain connectivity structures to be induced by the bags. These include the parameter of connected pathwidth introduced in @cite_16 in the context of graph searching games and studied further e.g. in @cite_18 @cite_15 . Another examples are connected treewidth @cite_17 , or bounded diameter tree decompositions @cite_22 @cite_6 .
@cite_18 @cite_22 @cite_6 @cite_15 @cite_16 @cite_17
2098322943 2099470983 2027562075 2763773774
We prove that any graph excluding Kr as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O(r Δ) fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning that required to remove O(r2 Δ) fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor, can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter O(r) and strong-diameter partitions with padding parameter O(r2) for Kr-free graphs, O(k) for treewidth-k graphs, and O(log g) for graphs with genus g. It is proven that the connected pathwidth of any graph @math is at most @math , where @math is the pathwidth of @math . The method is constructive, i.e., it yields an efficient algorithm that for a given path decomposition of width @math computes a connected path decomposition of width at most @math . The running time of the algorithm is @math , where @math is the number of “bags” in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality @math , where @math and @math are the connected search number and the search number of @math , respectively. Moreover, the algorithm presented in this work can be used to convert a given search strategy using @math searchers into a (monotone) connected one using @math searc... 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 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.