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.
In the graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence of moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive. In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected. We give evidence that many of the standard mathematical tools used so far in classic graph searching fail under the connectivity requirement. We also settle the question on ''the price of connectivity'', that is, how many searchers more are required for searching a graph when the connectivity demand is imposed. We make estimations of the price of connectivity on general graphs and we provide tight bounds for the case of trees. In particular, for an n-vertex graph the ratio between the connected searching number and the non-connected one is O(logn) while for trees this ratio is always at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for all graphs. Our combinatorial results imply a complete characterization of connected graph searching on trees. It is based on a forbidden-graph characterization of the connected search number. We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers. A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed. Finally, we reveal connections of this parameter to other invariants on trees such as the Horton-Strahler number.   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... Consider a team of mobile software agents deployed to capture a (possibly hostile) intruder in a network. All agents, including the intruder move along the network links; the intruder could be arbitrarily fast, and aware of the positions of all the agents. The problem is to design the agents' strategy for capturing the intruder. The main efficiency parameter is the size of the team. This is an instance of the well known graph-searching problem whose many variants have been extensively studied in the literature. In all existing solutions, and in all the variants of the problem, it is assumed that agents can be removed from their current location and placed in another network site arbitrarily and at any time. As a consequence, the existing optimal strategies cannot be employed in situations for which agents cannot access the network at any point, or cannot "jump" across the network, or cannot reach an arbitrary point of the network via an internal travel through insecure zones. This motivates the contiguous search problem in which agents cannot be removed from the network, and clear links must form a connected sub-network at any time, providing safety of movements. This new problem is NP-complete in general. We study it for tree networks, and we consider its more general version, the weighted case, which arises naturally when considering networks whose nodes and links are of different nature and thus require a different number of agents to be explored. We give a linear-time algorithm that computes, for any tree @math , the minimum number of agents to capture the intruder, and the corresponding search strategy. Beside its optimality in time, our algorithm is naturally distributed: if @math is a processor-network, then the minimal search strategy for @math can be computed by @math in a decentralized manner, using a linear number of messages. We give a constructive proof of the equality between treewidth and connected treewidth. More precisely, we describe an O(nk 3 )-time algorithm that, given any n-node width-k tree-decomposition of a connected graph G, returns a connected tree-decomposition of G of width < k. The equality between treewidth and connected treewidth finds applications in graph searching problems. First, using equality between treewidth and connected treewidth, we prove that the connected search number cs(G) of a connected graph G is at most logn + 1 times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an O(log n√log OPT)-approximation algorithm for connected search, running in time O(t(n) + nk 3 log 3 2 k + m log n) for n-node m-edge connected graphs of treewidth at most k, where t(n) is the time-complexity of the fastest algorithm for approximating the treewidth, up to a factor O(√log OPT).