Search

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]

Abstract: One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computational tasks. Almost no computational tasks in real life are specified by their size alone. It is not hard to imagine that some parameters contribute more intractability than others and it seems reasonable to develop a theory of computational complexity which seeks to exploit this fact. Such a theory should be able to address the needs of practitioners in algorithmics. The last twenty years have seen the development of such a theory. This theory has a large number of successes in terms of a rich collection of algorithmic techniques, both practical and theoretical, and a fine-grained intractability theory. Whilst the theory has been widely used in a number of areas of applications including computational biology, linguistics, VLSI design, learning theory and many others, knowledge of the area is highly varied. We hope that this article will show the basic theory and point at the wide array of techniques available. Naturally the treatment is condensed, and the reader who wants more should go to the texts of Downey and Fellows (1999) , Flum and Grohe (2006) , Niedermeier (2006) , and the upcoming undergraduate text (Downey and Fellows 2012) . [Copyright &y& Elsevier]

Abstract: For every graph H, there exists a polynomial-time algorithm deciding if a planar input graph G can be contracted to H. However, the degree of the polynomial depends on the size of H. We identify a class of graphs such that for every fixed , there exists a linear-time algorithm deciding whether a given planar graph G can be contracted to H. The class is the closure of planar triangulated graphs under taking of contractions. In fact, we prove that a graph if and only if there exists a constant such that if the treewidth of a graph is at least , it contains H as a contraction. We also provide a characterization of in terms of minimal forbidden contractions. [Copyright &y& Elsevier]

Abstract: We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints. [Copyright &y& Elsevier]

Abstract: The r-Regular Induced Subgraph problem asks, given a graph G and a non-negative integer k, whether G contains an r-regular induced subgraph of size at least k, that is, an induced subgraph in which every vertex has degree exactly r. In this paper we examine its parameterization k-Size r-Regular Induced Subgraph with k as parameter and prove that it is -hard. We also examine the parameterized complexity of the dual parameterized problem, namely, the k-Almost r-Regular Graph problem, which asks for a given graph G and a non-negative integer k whether G can be made r-regular by deleting at most k vertices. For this problem, we prove the existence of a problem kernel of size . [Copyright &y& Elsevier]

Abstract: We give a review of a series of techniques and results on the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch (or tree) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is the Bidimensionality Theory. Here we present not only the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of subexponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have time algorithms for a wide variety of parameterized problems on graphs, where is the size of the graph and is the parameter. [Copyright &y& Elsevier]

Abstract: We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton. [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]

The concept of compactor has been introduced in Kim et al. (2018) as a general data-reduction concept for parametrized counting problems. For a function F : Σ ∗ → N and a parameterization κ : Σ ∗ → N , a compactor (C , E) consists of a polynomial-time computable function P , called condenser , and a computable function M , called extractor , such that F = M ∘ P. If the size of P (x) is bounded by a polynomial function of κ (x) , then we say that the compactor (C , E) is of polynomial size. Compactors can be seen as an attempt to formalize the notion of preprocessing for counting problems. [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]