Search

Given a graph G, we define bcg (G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γ k . A graph class G has the SQGC property if every graph G ∈ G has treewidth O (bcg (G) c) for some 1 ≤ c < 2 . The SQGC property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQGC property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems. [ABSTRACT FROM AUTHOR]

We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept of wall homogeneity as well as the notion of regularity in flat walls. All proposed concepts and results aim at facilitating the use of the irrelevant vertex technique in future algorithmic applications. [ABSTRACT FROM AUTHOR]

Given a finite set of graphs H and a non-negative integer k , we define A k (H) as the set containing every graph G that has k vertices whose removal provides a graph without any of the graphs in H as a minor. It is known that if H contains at least one planar graph then each obstruction in A k (H) has at most k c H vertices, for some c H depending only on the choice of H. In this paper, we investigate the size of the graphs in A k (H) that belong to certain classes of sparse graphs. In particular, we prove that for every graph F , if H contains at least one planar graph and only connected graphs, all graphs in A k (H) that are F -topological minor-free have at most c F , H ⋅ k vertices, where c F , H depends exclusively on the choice of H and F. Our result is a consequence of two more general conditions on graph parameters, namely the Finite Integer Index Property and Protrusion Decomposability, that can serve as a general framework for proving linear bounds for obstructions. [ABSTRACT FROM AUTHOR]

A linkage in a graph G of size k is a subgraph L of G whose connected components are k paths. The pattern of a linkage of size k is the set of k pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function f: N rightarrow N such that if a plane graph G contains a sequence\scrC of at least f(k) nested cycles and a linkage of size at most k whose pattern vertices lay outside the outer cycle of scrC, then G contains a linkage with the same pattern avoiding the inner cycle of\scrC. In this paper we prove the following variant of this result: Assume that all the cycles in\scrC are "orthogonally" traversed by a linkage P and L is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of scrC := [C1,...,Cp, . . ., C2p-1]. We prove that there are two functions g, f: Nrightarrow N, such that if L has size at most k, P has size at least f(k), and | scrC | geq g(k), then there is a linkage with the same pattern as L that is "internally combed" by P, in the sense that L cap Cp subseteq P\cap Cp. This result applies to any graph that is partially embedded on a disk (wherescrC is also embedded). In fact, we prove this result in the most general version where the linkage L is s-scattered: every two vertices of distinct paths are within a distance bigger than s. We deduce several variants of this result in the cases where s = 0 and s > 0. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs. [ABSTRACT FROM AUTHOR]

We consider the weighted monotone and antimonotone satisfiability problems on normalized circuits of depth at most t ≥ 2 , abbreviated Image 1 and Image 2 , respectively, where the parameter under consideration is the weight of the sought satisfying assignment. These problems model the weighted satisfiability of monotone and antimonotone propositional formulas, and serve as the canonical problems in the definition of the parameterized complexity hierarchy. Moreover, several well-studied problems, including important graph problems, can be modeled as Image 1 and Image 2 problems in a straightforward manner. We study the parameterized complexity of Image 2 and Image 1 with respect to the genus of the underlying circuit. We give tight results, and draw a map of the parameterized complexity of these problems with respect to the genus of the circuit. As a byproduct of our results, we obtain tight characterizations of the parameterized complexity of several problems with respect to the genus of the underlying graph. [ABSTRACT FROM AUTHOR]

Several min–max relations in graph theory can be expressed in the framework of the Erdős–Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic. [ABSTRACT FROM AUTHOR]

For a fixed finite collection of graphs F, the F-M-DELETION problem is as follows: given an n-vertex input graph G, find the minimum number of vertices that intersect all minor models in G of the graphs in F. by Courcelle's Theorem, this problem can be solved in time fF(tw) - n°(1), where tw is the treewidth of G for some function ƒ depending on F. In a recent series of articles, we have initiated the program of optimizing asymptotically the function ff. Here we provide an algorithm showing that fF(tw) = 2° (tw.log tw) for every collection F. Prior to this work, the best known function ƒ was double- exponential in tw. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802-1811] for the particular case F = {K5, K3,3} and of Kociumaka and Pilipczuk [Algorithmica, 81 (2019), pp. 3655-3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [Inform. Comput., 256 (2017), pp. 62-82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections F [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135-152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56-77], our algorithm yields the following complexity dichotomy when F = {H} contains a single connected graph H, assuming the Exponential Time Hypothesis: ƒH(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and fH(tw) = 2Θ(tw-log tw) otherwise. [ABSTRACT FROM AUTHOR]

Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G ∖ S belongs to G. We denote by A k (G) the set of all graphs that are k -apices of G. We prove that every graph in the obstruction set of A k (G) , i.e., the minor-minimal set of graphs not belonging to A k (G) , has order at most 2 2 2 2 poly (k) , where poly is a polynomial function whose degree depends on the order of the minor-obstructions of G. This bound drops to 2 2 poly (k) when G excludes some apex graph as a minor. [ABSTRACT FROM AUTHOR]

The celebrated grid exclusion theorem states that for every h-vertex planar graph H, there is a constant [ABSTRACT FROM AUTHOR]

A strict bramble of a graph G is a collection of pairwise-intersecting connected subgraphs of G. The order of a strict bramble B is the minimum size of a set of vertices intersecting all sets of B. The strict bramble number of G, denoted by sbn (G) , is the maximum order of a strict bramble in G. The strict bramble number of G can be seen as a way to extend the notion of acyclicity, departing from the fact that (non-empty) acyclic graphs are exactly the graphs where every strict bramble has order one. We initiate the study of this graph parameter by providing three alternative definitions, each revealing different structural characteristics. The first is a min–max theorem asserting that sbn (G) is equal to the minimum k for which G is a minor of the lexicographic product of a tree and a clique on k vertices (also known as the lexicographic tree product number). The second characterization is in terms of a new variant of a tree decomposition called lenient tree decomposition. We prove that sbn (G) is equal to the minimum k for which there exists a lenient tree decomposition of G of width at most k. The third characterization is in terms of extremal graphs. For this, we define, for each k, the concept of a k-domino-tree and we prove that every edge-maximal graph of strict bramble number at most k is a k-domino-tree. We also identify three graphs that constitute the minor-obstruction set of the class of graphs with strict bramble number at most two. We complete our results by proving that, given some G and k, deciding whether sbn (G) ≤ k is an NP-complete problem. [ABSTRACT FROM AUTHOR]

Abstract: Let be a graph class. The square root of contains all graphs whose squares belong in . We prove that if is non-trivial and minor closed, then all graphs in its square root have carving-width bounded by some constant depending only on . As a consequence, every square root of such a graph class has a linear time recognition algorithm. [Copyright &y& Elsevier]

Abstract: For each non-negative integer , we provide all outerplanar obstructions for the class of graphs whose cycle matroid has pathwidth at most . Our proof combines a decomposition lemma for proving lower bounds on matroid pathwidth and a relation between matroid pathwidth and linear width. Our results imply the existence of a linear algorithm that, given an outerplanar graph, outputs its matroid pathwidth. [Copyright &y& Elsevier]

One of the major results of [N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63 (1995), pp. 65-110], also known as the weak structure theorem, reveals the local structure of graphs excluding some graph as a minor: each such graph G either has small treewidth or contains the subdivision of a planar graph (a wall) that can be arranged in a flat manner inside G, given that some small set of vertices is removed. We prove an optimized version of that theorem where (i) the relation between the treewidth of the graph and the height of the wall is linear (thus best possible) and (ii) the number of vertices to be removed is minimized. [ABSTRACT FROM AUTHOR]

We define helicopter cops and robber games with multiple robbers, extending previous research, which considered only the pursuit of a single robber. Our model is defined for robbers that are visible (their position in the graph is known to the cops) and active (they can move at any point in the game) but is easily adapted to other variants of the single-robber game that have been considered in the literature. We show that the game with many robbers is nonmonotone: that is, fewer cops are needed if the robbers are allowed to reoccupy positions that were previously unavailable to them. As the moves of the cops depend on the position of the visible robbers, strategies for such games should be interactive, but the game becomes, in a sense, less interactive as the initial number of robbers increases. We prove that the main parameter emerging from the game, which we denote mvams(G, r), captures a hierarchy of parameters between proper pathwidth and proper treewidth, and we completely characterize it for trees, extending analogous existing characterizations of the pathwidth of trees. Moreover, we prove an upper bound for mvams(G, r) on general graphs and show that this bound is reached by an infinite class of graphs. On the other hand, if we consider the robbers to be invisible and lazy, the resulting parameters collapse in all cases to either proper pathwidth or proper treewidth, giving a further case where the classical equivalence between visible, active robbers and invisible, lazy robbers does not hold. [ABSTRACT FROM AUTHOR]

Abstract: Graph searching encompasses a wide variety of combinatorial problems related to the problem of capturing a fugitive residing in a graph using the minimum number of searchers. In this annotated bibliography, we give an elementary classification of problems and results related to graph searching and provide a source of bibliographical references on this field. [Copyright &y& Elsevier]

We introduce a new approach to design parameterized algorithms on planar graphs which builds on the seminal results of Robertson and Seymour on graph minors. Graph minors provide a list of powerful theoretical results and tools. However, the widespread opinion in the graph algorithms community about this theory is that it is of mainly theoretical importance. In this paper we show how deep min-max and duality theorems from graph minors can be used to obtain exponential speed-up to many known practical algorithms for different domination problems. Our use of branch-width instead of the usual tree-width allows us to obtain much faster algorithms. By using this approach, we show that the k-dominating set problem on planar graphs can be solved in time O(215.13√k + n³). [ABSTRACT FROM AUTHOR]

Abstract: The cutwidth of a graph G is defined to be the smallest integer k such that the vertices of G can be arranged in a vertex ordering in a way that, for every , there are at most k edges with one endpoint in and the other in . We examine the problem of computing in polynomial time the cutwidth of a partial w-tree with bounded degree. In particular, we show how to construct an algorithm that, in steps, computes the cutwidth of any partial w-tree with vertices of degree bounded by a fixed constant d. Our algorithm is constructive in the sense that it can be adapted to output a corresponding optimal vertex ordering. Also, it is the main subroutine of an algorithm computing the pathwidth of a bounded degree partial w-tree with the same time complexity. [Copyright &y& Elsevier]

Abstract: The cutwidth of a graph G is the smallest integer k such that the vertices of G can be arranged in a linear layout in such a way that, for every , there are at most k edges with one endpoint in and the other in . In this paper we provide, for any constant k, a linear time algorithm that for any input graph G, answers whether G has cutwidth at most k and, in the case of a positive answer, outputs the corresponding linear layout. [Copyright &y& Elsevier]

Submodular functions have appeared to be a key tool for proving the monotonicity of several graph searching games. In this paper, we provide a general game theoretic framework able to unify old and new monotonicity results in a unique min–max theorem. Our theorem provides a game theoretic analogue to a wide number of graph theoretic parameters such as linear-width and cutwidth. [Copyright &y& Elsevier]

It is well known that the treewidth of a graph G corresponds to the node search number where a team of searchers is pursuing a fugitive that is lazy and invisible (or alternatively is agile and visible) and has the ability to move with infinite speed via unguarded paths. Recently, monotone and connected node search strategies have been considered. A search strategy is monotone if it prevents the fugitive from pervading again areas from where he had been expelled and is connected if, at each step, the set of vertices that is or has been occupied by the searchers induces a connected subgraph of G. It has been shown that the corresponding connected and monotone search number of a graph G can be expressed as the connected treewidth , denoted by ctw (G) , that is defined as the minimum width of a rooted tree-decomposition (X , T , r) , where the union of the bags corresponding to the nodes of a path of T containing the root r is connected in G. In this paper, we initiate the algorithmic study of connected treewidth. We design a O (n 2 ⋅ log n) -time dynamic programming algorithm to compute the connected treewidth of biconnected series–parallel graphs. At the price of an extra n factor in the running time, our algorithm generalizes to graphs of treewidth at most two. [ABSTRACT FROM AUTHOR]

We study the class L of link-types that admit a K 4 -minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K 4. We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L (and subclasses of it), with respect to the minimum number of crossings or edges in a projection of L ∈ L. Further, we obtain counting formulas and asymptotic estimates for the connected K 4 -minor-free link-diagrams, minimal K 4 -minor-free link-diagrams, and K 4 -minor-free diagrams of the unknot. [ABSTRACT FROM AUTHOR]

The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search, where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy are to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable; in particular we design a 2O(k2) \cdot n time algorithm that checks whether the connected pathwidth of G is at most k. This resolves an open question by Dereniowski, Osula, and Rz?azewski [Theoret. Comput. Sci., 794 (2019), pp. 85-100]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced by Bodlaender and Kloks [J. Algorithms, 21 (1996), pp. 358-402] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a "global" demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a 2O(k2) \cdot n time algorithm for the monotone and connected version of the edge search number. [ABSTRACT FROM AUTHOR]

Abstract: A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. Self-duality has been examined for several width parameters, such as branchwidth, pathwidth, and treewidth. In this paper, we give a direct proof of the self-duality of branchwidth in graphs embedded in some surface. In this direction, we prove that for any graph embedded in a surface of Euler genus . [Copyright &y& Elsevier]

The node‐search game against a lazy (or, respectively, agile) invisible robber has been introduced as a search‐game analogue of the treewidth parameter (and, respectively, pathwidth). In the connected variants of the above games, we additionally demand that, at each moment of the search, the clean territories are connected. The connected search game against an agile and invisible robber has been extensively examined. The monotone variant (where we demand that the clean territories are progressively increasing) of this game corresponds to the graph parameter of connected pathwidth. It is known that the price of connectivity to search for an agile robber is bounded by 2, that is, the connected pathwidth of a graph is at most twice (plus some constant) its pathwidth. We investigate the study of the connected search game against a lazy robber. A lazy robber moves only when the cops' strategy threatens the vertex that he currently occupies. We introduce two alternative graph‐theoretical formulations of this game, one in terms of connected tree‐decompositions and one in terms of (connected) layouts, leading to the graph parameter of connected treewidth. We observe that the connected treewidth parameter is closed under contractions and prove that for every k≥2, the set of contraction obstructions of the class of graphs with connected treewidth at most k is infinite. Our main result is a complete characterization of the obstruction set for k=2. We also show that, in contrast to the agile robber game, the price of connectivity is unbounded. [ABSTRACT FROM AUTHOR]

We introduce the graph theoretical parameter of edge-treewidth. This parameter occurs in a natural way as the tree-like analogue of cutwidth or, alternatively, as an edge-analogue of treewidth. We study the combinatorial properties of edge-treewidth. We first observe that edge-treewidth does not enjoy any closeness properties under the known partial ordering relations on graphs. We introduce a variant of the topological minor relation, namely, the weak topological minor relation and we prove that edge-treewidth is monotone with respect to weak topological minors. Based on this new relation we are able to provide universal obstructions for edge-treewidth. The proofs are based on the fact that edge-treewidth of a graph is parametrically equivalent with the maximum over the treewidth and the maximum degree of the blocks of the graph. We also prove that deciding whether the edge-treewidth of a graph is at most k is an NP -complete problem. [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, deciding whether there exists S ⊆ V (G) with |S| ≤ k such that G\S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function fF such that F-M-DELETION can be solved in time fF(tw) . nO(1) on n-vertex graphs. We prove that fF(tw) = 2²O(tw.logtw) for every collection F, that fF(tw) = 2O(tw.log tw) if F contains a planar graph, and that fF(tw) = 2O(tw) if in addition the input graph G is planar or embedded in a surface. We also consider the version of the problem where the graphs in F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring F to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic. [ABSTRACT FROM AUTHOR]

For a finite fixed collection of graphs F , the F -M-Deletion problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor. We provide lower bounds under the ETH on the smallest function f F such that F -M-Deletion can be solved in time f F (tw) ⋅ n O (1) on n -vertex graphs, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, f F (tw) = 2 Ω (tw) , even if G is planar. Our main result is that if F contains a single connected graph H that is either P 5 or is not a minor of the b a n n e r , then f F (tw) = 2 Ω (tw ⋅ log ⁡ tw). [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F , the F -M-Deletion (resp. F -TM-Deletion) problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G , denoted by tw , and specifically in the cases where F contains a single connected planar graph H. We present algorithms running in time 2 O (tw) ⋅ n O (1) , called single-exponential , when H is either P 3 , P 4 , C 4 , the paw , the chair , and the banner for both { H } -M-Deletion and { H } -TM-Deletion , and when H = K 1 , i , with i ≥ 1 , for { H } -TM-Deletion. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. (2015) [7]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of { H } -M-Deletion in terms of H. [ABSTRACT FROM AUTHOR]

We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formula φ, we consider the problem of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the resulting modification has the property expressible by φ. We provide sufficient and necessary conditions on the structure of the prefix of φ specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by k) and when it admits a polynomial kernel. [ABSTRACT FROM AUTHOR]

We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider , play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some vertices. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex. Divider aims to prevent the rendezvous of Facilitator's agents. We show that deciding whether Facilitator can win is PSPACE -hard and, when parameterized by k , co-W [ 2 ] -hard. Moreover, even deciding whether Facilitator can win within τ steps is co-NP -complete already for τ = 2. On the other hand, for chordal and P 5 -free graphs, we prove that the problem is solvable in polynomial time. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph's neighborhood diversity and the number of steps τ. [ABSTRACT FROM AUTHOR]

We consider the mixed search game against an agile and visible fugitive. This is the variant of the classic fugitive search game on graphs where searchers may be placed to (or removed from) the vertices or slide along edges. Moreover, the fugitive resides on the edges of the graph and can move at any time along unguarded paths. The mixed search number against an agile and visible fugitive of a graph G , denoted avms (G) , is the minimum number of searchers required to capture a fugitive in this graph searching variant. Our main result is that this graph searching variant is monotone in the sense that the number of searchers required for a successful search strategy does not increase if we restrict the search strategies to those that do not permit the fugitive to visit an already "clean" edge. This means that mixed search strategies against an agile and visible fugitive can be polynomially certified, and therefore that the problem of deciding, given a graph G and an integer k , whether avms (G) ≤ k is in NP. Our proof is based on the introduction of the notion of tight bramble , that serves as an obstruction for the corresponding search parameter. Our results imply that for a graph G , avms (G) is equal to the Cartesian tree product number of G , that is, the minimum k for which G is a minor of the Cartesian product of a tree and a clique on k vertices. [ABSTRACT FROM AUTHOR]

In the Red–Blue Dominating Set problem, we are given a bipartite graph G = ( V B ∪ V R , E ) and an integer k , and asked whether G has a subset D ⊆ V B of at most k “blue” vertices such that each “red” vertex from V R is adjacent to a vertex in D . We provide the first explicit linear kernel for this problem on planar graphs, of size at most 43 k . [ABSTRACT FROM AUTHOR]

We consider the connected variant of the classic mixed search game where, in each search step, cleaned edges form a connected subgraph. We consider graph classes with bounded connected (and monotone) mixed search number and we deal with the question whether the obstruction set, with respect of the contraction partial ordering, for those classes is finite. In general, there is no guarantee that those sets are finite, as graphs are not well quasi ordered under the contraction partial ordering relation. In this paper we provide the obstruction set for k = 2 , where k is the number of searchers we are allowed to use. This set is finite, it consists of 177 graphs and completely characterises the graphs with connected (and monotone) mixed search number at most 2. Our proof reveals that the “sense of direction” of an optimal search searching is important for connected search which is in contrast to the unconnected original case. We also give a double exponential lower bound on the size of the obstruction set for the classes where this set is finite. [ABSTRACT FROM AUTHOR]

For every r ∈ N , we denote by θ r the multigraph with two vertices and r parallel edges. Given a graph G , we say that a subgraph H of G is a model of θ r in G if H contains θ r as a contraction. We prove that the following edge variant of the Erdős–Pósa property holds for every r ⩾ 2 : if G is a graph and k is a positive integer, then either G contains a packing of k mutually edge-disjoint models of θ r , or it contains a set S of f r ( k ) edges such that G ∖ S has no θ r -model, for both f r ( k ) = O ( k 2 r 3 polylog k r ) and f r ( k ) = O ( k 4 r 2 polylog k r ) . [ABSTRACT FROM AUTHOR]

We introduce the parameter of block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class G , the class B (G) contains all graphs whose blocks belong to G and the class A (G) contains all graphs where the removal of a vertex creates a graph in G . Given a hereditary graph class G , we recursively define G (k) so that G (0) = B (G) and, if k ≥ 1 , G (k) = B (A (G (k - 1))) . We show that, for every non-trivial hereditary class G , the problem of deciding whether G ∈ G (k) is NP-complete. We focus on the case where G is minor-closed and we study the minor obstruction set of G (k) i.e., the minor-minimal graphs not in G (k) . We prove that the size of the obstructions of G (k) is upper bounded by some explicit function of k and the maximum size of a minor obstruction of G . This implies that the problem of deciding whether G ∈ G (k) is constructively fixed parameter tractable, when parameterized by k. Finally, we give two graph operations that generate members of G (k) from members of G (k - 1) and we prove that this set of operations is complete for the class O of outerplanar graphs.Please check and confirm if the authors Given and Family names have been correctly identified for author znur YaŸar Diner.All authors names have been identified correctly.Please confirm if the corresponding author is correctly identified. Amend if necessary.This is correct [ABSTRACT FROM AUTHOR]

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs ( K5 and K3, 3) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying i-edge-sums, for [ABSTRACT FROM AUTHOR]

Abstract: We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface and introduce the number of non-crossing partitions of a set of points lying on the boundary of . Our main result is an asymptotic estimate for . The proofs use bijective techniques arising from map enumeration, joint with the symbolic method and singularity analysis on generating functions. An outcome of our results is that the exponential growth of is the same as the one of the -th Catalan number, i.e., does not change when we move from the case where is a disk to general surfaces with boundary. [Copyright &y& Elsevier]

Abstract: We introduce a variant of the classic node search game called LIFO-search where searchers are assigned different numbers. The additional rule is that a searcher can be removed only if no searchers of lower rank are in the graph at that moment. We show that all common variations of the game require the same number of searchers. We then introduce the notion of (directed) shelters in (di)graphs and prove a min–max theorem implying their equivalence to the cycle-rank/tree-depth parameter in (di)graphs. As (directed) shelters provide escape strategies for the fugitive, this implies that the LIFO-search game is monotone and that the LIFO-search parameter is equivalent to the one of cycle-rank/tree-depth in (di)graphs. [Copyright &y& Elsevier]

Abstract: We give an algorithm that, for a fixed graph H and integer k, decides whether an n-vertex H-minor-free graph G contains a path of length k in steps. Our approach builds on a combination of Demaine–Hajiaghayiʼs bounds on the size of an excluded grid in such graphs with a novel combinatorial result on certain branch decompositions of H-minor-free graphs. This result is used to bound the number of ways vertex disjoint paths can be routed through the separators of such decompositions. The proof is based on several structural theorems from the Graph Minors series of Robertson and Seymour. With a slight modification, similar combinatorial and algorithmic results can be derived for many other problems. Our approach can be viewed as a general framework for obtaining time algorithms on H-minor-free graph classes. [Copyright &y& Elsevier]

Abstract: For , let be the class of graphs that contain vertices meeting all its cycles. The minor-obstruction set for is the set containing all minor-minimal graphs that do not belong to . We denote by the set of all outerplanar graphs in . In this paper, we provide a precise characterization of the class . Then, using singularity analysis over the counting series obtained with the Symbolic Method, we prove that where and ( is the smallest positive root of a quadratic equation). [Copyright &y& Elsevier]

Abstract: For every , we define as the class of graphs with tree-depth at most , i.e. the class containing every graph admitting a valid colouring such that every -path between two vertices where contains a vertex where . In this paper, we study the set of graphs not belonging in that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of ). We determine these sets for for each relation and prove a structural lemma for creating obstructions from simpler ones. As a consequence, we obtain a precise characterization of all acyclic obstructions of and we prove that there are exactly . Finally, we prove that each obstruction of has at most vertices. [Copyright &y& Elsevier]

Abstract: We provide two parameterized graphs , with the following property: for every positive integer k, there is a constant such that every graph G with treewidth at least , contains one of , , as a contraction, where is a complete graph on k vertices. These three parameterized graphs can be seen as “obstruction patterns” for the treewidth with respect to the contraction partial ordering. We also present some refinements of this result along with their algorithmic consequences. [Copyright &y& Elsevier]

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending the tractability of many problems in database theory and artificial intelligence. In this paper, we study the approximability of (generalized, fractional) hypertree width of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph H is constant factor sandwiched by the treewidth of its incidence graph when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above in which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some H-minor-free graph class. [ABSTRACT FROM AUTHOR]

Abstract: We prove that for any fixed , the tree-width of graphs not containing as a topological minor (resp. as a subgraph) is bounded by a linear (resp. polynomial) function of their rank-width. We also present refinements of our bounds for other graph classes such as -minor free graphs and graphs of bounded genus. [ABSTRACT FROM AUTHOR]

Abstract: We give a linear-time algorithm checking whether a graph is a subgraph of the -grid for some value of . Our algorithm is based on a detailed characterization of the structure of such graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate algorithms for some related graph parameters. Each of these asks for a linear ordering of the vertices of the graph (or can be formulated as such), and constructive linear time algorithms for the fixed parameter versions of the problems have been published for several of these. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present ideas in these algorithms in a different more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a trivial hypothetical non-deterministic algorithm. The methodology is applied to rederive known results for the cutwidth and the pathwidth problem, and obtain new results for several variants of these problems, like directed and weighted variants of cutwidth and modified cutwidth. [Copyright &y& Elsevier]

Abstract: We study the fixed parameter tractability of the counting version of a parameterization of the restrictive list H-coloring problem. The parameterization is defined by fixing the number of preimages of a subset C of the vertices in H through a weight assignment K on C. We show the fixed parameter tractability of counting the number of list -colorings, for the case in which is simple. We introduce the concept of compactor and a new algorithmic technique, compactor enumeration, that allow us to design fixed parameter algorithms for parameterized counting problems. [Copyright &y& Elsevier]

Abstract: We consider a bounded version of the restrictive and the restrictive list H-coloring problem in which the number of pre-images of certain vertices of H is taken as parameter. We consider the decision and the counting versions, as well as, further variations of those problems. We provide complexity results identifying the cases when the problems are NP-complete or #P-complete or polynomial time solvable. We conclude stating some open problems. [Copyright &y& Elsevier]

Bidimensionality provides a tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper extends the theory of bidimensionality for graphs of bounded genus (which is a minor-excluding family). Specifically we show that, for any problem whose solution value does not increase under contractions and whose solution value is large on a grid graph augmented by a bounded number of handles, the treewidth of any bounded-genus graph is at most a constant factor larger than the square root of the problem's solution value on that graph. Such bidimensional problems include vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, r-dominating set, connected dominating set, planar set cover, and diameter. On the algorithmic side, by showing that an augmented grid is the prototype bounded-genus graph, we generalize and simplify many existing algorithms for such problems in graph classes excluding a minor. On the combinatorial side, our result is a step toward a theory of graph contractions analogous to the seminal theory of graph minors by Robertson and Seymour. [ABSTRACT FROM AUTHOR]