Search

Given two graphs G and H, we define v-coverH(G) (resp. e-coverH(G)) as the minimum number of vertices (resp. edges) whose removal from G produces a graph without any minor isomorphic to H. Also v-packH(G) (resp. e-packH(G)) is the maximum number of vertex- (resp. edge-) disjoint subgraphs of G that contain a minor isomorphic to H. We denote by θr the graph with two vertices and r parallel edges between them. When H=θr, the parameters v-coverH, e-coverH, v-packH, and e-packH are NP-hard to compute (for sufficiently big values of r). Drawing upon combinatorial results in Chatzidimitriou et al. (Minors in graphs of large θr-girth, 2015, arXiv:1510.03041), we give an algorithmic proof that if v-packθr(G)≤k, then v-coverθr(G)=O(klogk), and similarly for e-packθr and  e-coverθr. In other words, the class of graphs containing θr as a minor has the vertex/edge Erdős-Pósa property, for every positive integer r. Using the algorithmic machinery of our proofs we introduce a unified approach for the design of an O(logOPT)-approximation algorithm for v-packθr, v-coverθr, e-packθr, and e-coverθr that runs in O(n·log(n)·m) steps. Also, we derive several new Erdős-Pósa-type results from the techniques that we introduce. [ABSTRACT FROM AUTHOR]

The tree-cut width of a graph is a graph parameter defined by Wollan (J Combin Theory, Ser B, 110:47-66, 2015) with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input n-vertex graph G and an integer w, our algorithm either confirms that the tree-cut width of G is more than w or returns a tree-cut decomposition of G certifying that its tree-cut width is at most 2 w, in time $$2^{O(w^2\log w)} \cdot n^2$$ . Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known. [ABSTRACT FROM AUTHOR]