Search

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]

In their work I "Fixed parameter algorithms for unsplittable flow cover i , Andrés Cristi, Mathieu Mari and Andreas Wiese considered UFP under the view point of parameterized complexity. The topics of the chosen papers cover various areas of Theoretical Computer Science, that is, algorithmic graph theory, automata theory, linear dynamical systems, parameterized complexity analysis, and distributed algorithms. This special issue contains 7 articles which are based on extended abstracts presented at the 36th I Symposium on Theoretical Aspects of Computer Science i (STACS). [Extracted from the article]

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]

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]

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 consider a cops and robber game where the cops are blocking edges of a graph, while the robber occupies its vertices. At each round of the game, the cops choose some set of edges to block and right after the robber is obliged to move to another vertex traversing at most s unblocked edges (s can be seen as the speed of the robber). Both parts have complete knowledge of the opponent's moves and the cops win when they occupy all edges incident to the robbers position. We introduce the capture cost on G against a robber of speed s. This defines a hierarchy of invariants, namely δ e 1 , δ e 2 , ... , δ e ∞ , where δ e ∞ is an edge-analogue of the admissibility graph invariant, namely the edge-admissibility of a graph. We prove that the problem asking whether δ e s (G) ≤ k , is polynomially solvable when s ∈ { 1 , 2 , 3 , ∞ } while, otherwise, it is NP -complete. Our main result is a structural theorem for graphs of bounded edge-admissibility. We prove that every graph of edge-admissibility at most k can be constructed using (≤ k) -edge-sums, starting from graphs whose all vertices, except possibly from one, have degree at most k. Our structural result is approximately tight in the sense that graphs generated by this construction always have edge-admissibility at most 2 k − 1. Our proofs are based on a precise structural characterization of the graphs that do not contain θ r as an immersion, where θ r is the graph on two vertices and r parallel edges. [ABSTRACT FROM AUTHOR]

This article belongs to the Topical Collection: Special Issue on Theoretical Aspects of Computer Science (2019) Guest Editors: Rolf Niedermeier and Christophe Paul This special issue contains five articles which are based on extended abstracts presented at the 35th I Symposium on Theoretical Aspects of Computer Science i (STACS). The token sliding problem is one of the most well-studied problems in the area of combinatorial reconfiguration. In their paper I "Space Lower Bounds for the Signal Detection Problem" i , Faith Ellen, Rati Gelashvili, Philipp Woelfel, and Leqi Zhu address a basic communication problem. [Extracted from the article]

We prove that the strong immersion order is a well‐quasi‐ordering on the class of semicomplete digraphs, thereby strengthening a result of Chudnovsky and Seymour (2011, J. Comb. Theory, Series B, 101, 47–53) that this holds for the class of tournaments. [ABSTRACT FROM AUTHOR]

During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices. In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. F -Packing is a typical example: for a family F of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph G contains k vertex-disjoint subgraphs such that each of them contains a graph in F as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of F -Packing: for an integer ℓ ⩾ 1 , one aims at finding either minor-models that are pairwise at distance at least ℓ in G (ℓ - F -Packing), or such that each vertex in G belongs to at most ℓ minors-models (F -Packing with ℓ -Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors. [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]

We design FPT -algorithms for the following problems. The first is List Digraph Homomorphism : given two digraphs G and H , with order n and h , respectively, and a list of allowed vertices of H for every vertex of G , does there exist a homomorphism from G to H respecting the list constraints? Let ℓ be the number of edges of G mapped to non-loop edges of H . The second problem is Min-Max Multiway Cut : given a graph G , an integer ℓ ≥ 0 , and a set T of r terminals, can we partition V ( G ) into r parts such that each part contains one terminal and there are at most ℓ edges with only one endpoint in this part? We solve both problems in time 2 O ( ℓ ⋅ log ⁡ h + ℓ 2 ⋅ log ⁡ ℓ ) ⋅ n 4 ⋅ log ⁡ n and 2 O ( ( ℓ r ) 2 log ⁡ ℓ r ) ⋅ n 4 ⋅ log ⁡ n , respectively, via a reduction to a new problem called List Allocation , which we solve adapting the randomized contractions technique of Chitnis et al. (2012) [4] . [ABSTRACT FROM AUTHOR]

In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species X; these relationships are often depicted via a phylogenetic tree-a tree having its leaves labeled bijectively by elements of X and without degree-2 nodes-called the 'species tree.' One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g., DNA sequences originating from some species in X), and then constructing a single phylogenetic tree maximizing the 'concordance' with the input trees. The obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping-but not identical-sets of labels, is called 'supertree.' In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of 'containing as a minor' and 'containing as a topological minor' in the graph community. Both problems are known to be fixed parameter tractable in the number of input trees k, by using their expressibility in monadic second-order logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on k of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time $$2^{O(k^2)} \cdot n$$ , where n is the total size of the input. [ABSTRACT FROM AUTHOR]

Background: Orthologs inference is the starting point of most comparative genomics studies and a plethora of methods have been designed in the last decade to address this challenging task. In this paper we focus on the problems of deciding consistency with a species tree (known or not) of a partial set of orthology/paralogy relationships C on a collection of n genes. Results: We give the first polynomial algorithm-more precisely a O(n3) time algorithm-to decide whether C is consistent, even when the species tree is unknown. We also investigate a biologically meaningful optimization version of these problems, in which we wish to minimize the number of duplication events; unfortunately, we show that all these optimization problems are NP-hard and are unlikely to have good polynomial time approximation algorithms. Conclusions: Our polynomial algorithm for checking consistency has been implemented in Python and is available. [ABSTRACT FROM AUTHOR]

We develop a technique, that we call conflict packing , to obtain (and improve) polynomial kernels for several well-studied editing problems. We first illustrate our technique on Feedback Arc Set in Tournaments ( k -FAST ) yielding an alternative and simple proof of a linear kernel for this problem. The technique is then applied to obtain the first linear kernel for the Dense Rooted Triplet Inconsistency ( k -dense-RTI ) problem. A linear kernel for Betweenness in Tournaments ( k -BIT ) is also proved. All these problems share common features. First, they can be expressed as modification problems on a dense set of constant-arity constraints. Also the consistency of the set of constraints can be characterized by means of a bounded size obstructions. The conflict packing technique basically consists of computing a maximal set of small obstructions allowing us either to bound the size of the input or to reduce the input. [ABSTRACT FROM AUTHOR]

This paper looks at reading in French immersion and how learning French is seen more as a skill rather than a social practice that could be examined through a more critical lens. Most of the teachers often teach students how to read but rarely will they discuss the role of French in Canadian society and how this is manifested in the texts they read and the world around them. This critical knowledge of how French and bilingualism are regarded in French immersion schools is lacking and brings several challenges to students inside and outside of the program. They learn how to read but can be quickly discouraged from using their French outside of school due to ideological assumptions that fail to recognize these students as bilingual, instead requiring cultural and native-like demonstrations of competence in the language in order to be accepted and allowed to speak. [ABSTRACT FROM AUTHOR]

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [(Meta) kernelization, in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2009, pp. 629– 638] on graphs of bounded genus, then generalized by Fomin et al. [Bidimensionality and kernels, in Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadephia, 2010, pp. 503–510] to graphs excluding a fixed minor, and by Kim et al. [Linear kernels and single-exponential algorithms via protrusion decompositions, in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Comput. Sci., 7965 (2013), pp. 613–624] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions, but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper, we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in counting monadic second order logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-Dominating Set and r-Scattered Set on apex-minor-free graphs, and for PLANAR-F-DELETION on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected. [ABSTRACT FROM AUTHOR]

Given a graph G and a parameter k ∈ N , the parameterized K 4 - minor cover problem asks whether at most k vertices can be deleted to turn G into a K 4 -minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set , which can also be expressed as Treewidth - t Vertex Deletion problems: t = 0 for Vertex Cover and t = 1 for Feedback Vertex Set . While single-exponential FPT algorithms, i.e. running in 2 O ( k ) ⋅ n O ( 1 ) time, are known for these two latter problems, it was open whether the K 4 - minor cover problem could be solved in single-exponential FPT time. This paper answers this question in the affirmative. Observe that it is known to be unlikely that Treewidth - t Vertex Deletion can be solved in time 2 o ( k ) ⋅ n O ( 1 ) . [ABSTRACT FROM AUTHOR]

Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decomposition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split decomposition algorithm that runs in time O( n+ m) α( n+ m), where α is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Compared to Dahlhaus' linear time split decomposition algorithm (Dahlhaus in J. Algorithms 36(2):205-240, ), which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation details are given in this paper. Also, our algorithm extends to circle graph recognition, whereas no such extension is known for Dahlhaus' algorithm. The companion paper (Gioan et al. in , ) uses our algorithm to derive the first sub-quadratic circle graph recognition algorithm. [ABSTRACT FROM AUTHOR]

Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is O( n+ m) times the inverse Ackermann function, α( n+ m), whose value is smaller than 4 for any practical graph. The algorithm is based on a new incremental Lexicographic Breadth-First Search characterization of circle graphs, and a new efficient data-structure for circle graphs, both developed in the paper. The algorithm is an extension of a Split Decomposition algorithm with the same running time developed by the authors in a companion paper. [ABSTRACT FROM AUTHOR]

The c-pumpkin is the graph with two vertices linked by c ≥ 1 parallel edges. A c-pumpkin-model in a graph G is a pair {A, B} of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on hitting and packing c-pumpkin-models in a given graph in the realm of approximation algorithms and parameterized algorithms. We give a fixed-parameter tractable (FPT) algorithm running in time 2...(κ)(n...(1) deciding, for any fixed c ≥ 1, whether all c-pumpkin-models can be hit by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex SET, which correspond to the cases c = 1, 2 respectively. Finally, we present an ...(log n)-approximation algorithm for both the problems of hitting all c-pumpkin-models with a smallest number of vertices and packing a maximum number of vertex-disjoint c-pumpkin-models. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give structural and incremental characterizations, leading to optimal fully dynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on the new combinatorial framework of graph-labelled trees used to represent the split decomposition of general graphs (and also the modular decomposition). The point of the paper is to use bijections between the aforementioned graph classes and graph-labelled trees whose nodes are labelled by cliques and stars. We mention that this bijective viewpoint yields directly an intersection model for the class of distance hereditary graphs. [Copyright &y& Elsevier]

This paper considers the problem of maintaining a compact representation ( O( n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O( n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs. [ABSTRACT FROM AUTHOR]

Abstract: A graph is a 3-leaf power iff there exists a tree the leaf set of which is and such that iff and are at distance at most 3 in . The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion are FPT when parameterized by the size of the edge set modification. However, polynomial kernels were known for none of these three problems. For each of them, we provide kernels with vertices that can be computed in linear time. We thereby answer an open problem first mentioned by Dom et al. (2004) . [ABSTRACT FROM AUTHOR]

Abstract: This paper revisits the ‘branchwidth territories’ of Kloks, Kratochvíl and Müller [T. Kloks, J. Kratochvíl, H. Müller, New branchwidth territories, in: 16th Ann. Symp. on Theoretical Aspect of Computer Science, STACS, in: Lecture Notes in Computer Science, vol. 1563, 1999, pp. 173–183] to provide a simpler proof, and a faster algorithm for computing the branchwidth of an interval graph. We also generalize the algorithm to the class of chordal graphs, albeit at the expense of exponential running time. Compliance with the ternary constraint of the branchwidth definition is facilitated by a simple new tool called -troikas: three sets of size at most each are a -troika of set , if any two have union . We give a straightforward algorithm, computing branchwidth for an interval graph on edges, vertices and maximal cliques. We also prove a conjecture of Mazoit [F. Mazoit, A general scheme for deciding the branchwidth, Technical Report RR2004-34, LIP — École Normale Supérieure de Lyon, 2004. http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2004/RR2004-34.pdf], by showing that branchwidth can be computed in polynomial time for a chordal graph given with a clique tree having a polynomial number of subtrees. [Copyright &y& Elsevier]

Abstract: Treewidth and branchwidth are two closely related connectivity parameters of graphs. Graphs of treewidth at most have well-known alternative characterizations as subgraphs of chordal graphs and as partial -trees. In this paper we give analogous alternative characterizations for graphs of branchwidth at most . We first show that they are the subgraphs of chordal graphs where every maximal clique has three subsets of size at most each such that any two subsets have union , with the property that every minimal separator contained in is contained in one of the three subsets. Secondly, we give a characterization of the edge-maximal graphs of branchwidth , that we call -branches. [Copyright &y& Elsevier]

Abstract: Given a set of points (clients) on a weighted tree , a -centre of corresponds to a set of points (facilities) on such that the maximum graph distance between any client and its nearest facility is minimised. We consider the mobile -centre problem on trees. Let denote a set of mobile clients, each of which follows a continuous trajectory on a weighted tree . We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of . When each client in moves with linear motion along a path on , the motions of the corresponding 1-centre and 2-centre are piecewise linear; we derive a tight combinatorial bound of on the complexity of the motion of the 1-centre and corresponding bounds of and for a 2-centre, where denotes the inverse Ackermann function. We describe efficient algorithms for calculating the trajectories of the 1-centre and 2-centre of : the 1-centre can be found in optimal time and a 2-centre can be found in time . These algorithms lend themselves to implementation within the framework of kinetic data structures. Finally, we examine properties of the mobile 1-centre on graphs and describe an optimal unit-velocity 2-approximation. [Copyright &y& Elsevier]

Abstract: In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the -free graphs (where denotes the path with 4 vertices). The recognition process works in two steps. First, we use partition refinement techniques to produce a factorizing permutation, i.e., an ordering of the vertices in which the strong modules appear consecutively. Then a very simple test algorithm is provided to check whether the given graph is a cograph, using a single sweep of the permutation obtained in the first step. [Copyright &y& Elsevier]

A distance labeling scheme is a distributed data-structure designed to answer queries about distance between any two vertices of a graph G. The data-structure consists in a label L(x,G) assigned to each vertex x of G such that the distance dG(x,y) between any two vertices x and y can be estimated as a function f(L(x,G),L(y,G)). In this paper, by the use of split decomposition of graphs, we combine several types of distance labeling schemes. This yields to optimal label length schemes for the family of distance-hereditary graphs and for other families of graphs, allowing distance estimation in constant time once the labels have been constructed. [Copyright &y& Elsevier]

Partition refinement techniques lead to simple and efficient algorithms for various applications: automation minimization, string sorting&hellips; and also for algorithms on graphs. A generic algorithm that can be used for all these applications is presented and briefly discussed. Such an approach is interesting in an algorithmic tool kit perspective. New instances of the generic algorithm are presented: O(n + m log n) very simple and practical algorithms for cographs recognition and for modular decomposition are designed. Although these algorithms are not linear, they are very easy to implement (as an instantiation of a generic procedure) and based on new ideas. [ABSTRACT FROM AUTHOR]

Presents author's reaction to Joel Rudinow's article `Race, Ethnicity, Expressive Authenticity: Can White People Sing the Blues?' regarding the nuances of the racialist discourse from which Rudinow's claim emerges. Summary of Rudinow's argument based on the Black Blues Authenticity Thesis (BBA); The blues experience as an experience of being; Confusion over the possibility of defining a black experience.

Examines the reason for the changes in Portuguese foreign policy since 1960 in terms of key ideas, interests and knowledge of the domestic elites and their relationship with the international environment. Conceptual issues; Isolationist foreign policy; Radicalization of Portuguese foreign policy from 1974 to 1976; Normalization of foreign policy from 1976 to 1995.

The effect of three plant growth-promoting Bacillus strains inoculated either alone or as a consortium was tested on oat (Avena sativa) growth. The bioinoculants were applied as vegetative cells or endospores at low cell densities on the seeds and their effect was tested in sterile in vitro conditions, pot experiments, and a field trial. The in vitro seed germination assay showed that both individual bacterial inocula and bacterial consortia had positive effects on seed germination. Greenhouse pot experiments with sterile and non-sterile soil showed that consortia increased the total dry biomass of oat plants as compared to single strain inoculation and uninoculated controls. However, the positive impact on plant growth was less prominent when the bioinoculated strains had to compete with native soil microbes. Finally, the field experiment demonstrated that the consortium of vegetative cells was more efficient in promoting oat growth than the endospore consortium and the uninoculated control. Moreover, both consortia successfully colonized the roots and the rhizosphere of oat plants, without modifying the overall structure of the autochthonous soil microbial communities. [ABSTRACT FROM AUTHOR]

Lake Liambezi is located at the Eastern side of Caprivi Strip, straddling the border between Namibia and Botswana. The drainage basin of the lake is a large, flat wetland, including some woodlands, which contains a typically slow-flowing floodplain river (Seaman et al., 1978; Peel et al., 2015). The Lake changes its shape, size, and depth seasonally and over the years due to fluctuating contributions of water from its distinct source regions. The lake forms two elongated basins with a South-West to North-West direction joined by a main channel.The present study is based on multiple methods conducted on the watershed as well as on the lake. The aim is to give a paleoecological interpretation of the lake with isotopic and multi-proxy records. During the two field campaigns conducted during the dry season (September 2016) as well as at the end of the rainy season during March 2017, water from multiple sources of ground and surface waters were collected to better understand the drainage and hydrodynamics (Dyer, 2017). It was also established that the present climate supports a vegetation representing both the C3 and C4 photosynthetic cycles (Ballif, 2018). As they discriminate very differently against 13C during photosynthesis, such that the C-isotope composition of organic matter accumulated in soils or sediments may provide valuable information on the local ecosystem. In parallel to these geochemical studies three cores of 40 cm each were sampled in the lake. Sediments of the cores were first characterized by scanning electron microscopy that indicated a large fraction of diatoms in the sediments. Subsequent isotope analysis of carbon (13C/12C and 14C), nitrogen, hydrogen and oxygen of the organic matter and also RockEval measurements will evaluate the composition and quality of the organic matter. The lithogenic fraction is analysed via X-ray diffraction and fluorescence for the mineralogy and bulk chemical composition. Collectively, these analyses should allow for good estimates of the sedimentation rates, age of the sediment and a paleoecological interpretation that will then be compared to information obtained from endospore forming communities, a novel biological marker proposed in paleoecological reconstructions.REFERENCESBallif, L. 2018: Carbon and nitrogen stable isotope compositions as environmental proxies in savannas of northern Botswana. Unpubl. Master of Science in Biogeosciences, UNIL.Dyer, S. 2017: Water cycle in the Northern Kalahari. Unpubl. Master of Science in Biogeosciences, UNIL.Peel, RA., Tweddle, D., Simasiku, EK., Martin, GD., Lubanda, J., Hay, CJ., Weyl, OLF. 2015: Ecology, fish and fishery of Lake Liambezi, a recently refilled floodplain lake in the Zambezi Region, Namibia. African Journal of Aquatic Science 40:4, 417-424.Seaman, M.T., Scott, W.E., Walmsley, R.D., van der Waal, B.C.W., & Toerien, D.F. 1978: A limnological investigation of Lake Liambezi, Caprivi. Journal of the Limnological Society of Southern Africa 4:2, 129-144. [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]

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The Minimum Changeover Cost Arborescence ( MinCCA ) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gözüpek et al. (2016) that the MinCCA problem when parameterized by the treewidth and the maximum degree of the input graph is in FPT . In this article we present the following hardness results for MinCCA : • the problem is W [1]-hard when parameterized by the vertex cover number of the input graph, even on graphs of degeneracy at most 3. In particular, it is W [1]-hard parameterized by the treewidth of the input graph, which answers the main open problem in the work of Gözüpek et al. (2016); • it is W [1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph; and • it remains NP -hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs. [ABSTRACT FROM AUTHOR]

The Saprolegnia-Achlya clade comprises species of major environmental and economic importance due to their negative impact on aquaculture and aquatic ecosystems by threatening fishes, amphibians, and crustaceans. However, their taxonomy and phylogenetic relationships remain unresolved and suffer from many inconsistencies, which is a major obstacle to the widespread application of molecular barcoding to identify pathogenic strains with quarantine implications. We assessed phylogenetic relationships of major genera using three commonly used markers (ITS, SSU rRNA, and LSU rRNA). A consensus tree of the three genes provided support for nine clades encompassing eleven documented genera and a new clade (SAP1) that has not been described morphologically. In the course of this study, we isolated a new species, Newbya dichotoma sp. nov., which provided the only culture available for this genus. In parallel, we attempted to summarize the evolution of traits in the different genera, but their successive reversals rendered the inference of ancestral states impossible. This highlights even more the importance of a bar-coding strategy for saprolegniacean parasite detection and monitoring. [ABSTRACT FROM AUTHOR]

Given a graph G=( V, E) and a positive integer k, an edge modification problem for a graph property Π consists in deciding whether there exists a set F of pairs of V of size at most k such that the graph $H=(V,E\vartriangle F)$ satisfies the property Π. In the Π edge-completion problem, the set F is constrained to be disjoint from E; in the Π edge-deletion problem, F is a subset of E; no constraint is imposed on F in the Π edge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171-176, ; Fellows et al. in FCT, pp. 312-321, ; Heggernes et al. in STOC, pp. 374-381, ). When parameterized by the size k of the set F, it has been proved that if Π is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the three Π edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171-176, ). It was then natural to ask (Bodlaender et al. in IWPEC, ) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance ( G′, k′) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively (Kratsch and Wahlström in IWPEC, pp. 264-275, ). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that Parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the P- free edge-deletion and the C- free edge-deletion problems for l⩾7 and l≥4 respectively. Indeed, if they exist, then NP⊆ coNP/ poly. [ABSTRACT FROM AUTHOR]

Phylogenetic networks were introduced to describe evolution in the presence of exchanges of genetic material between coexisting species or individuals. Split networks in particular were introduced as a special kind of abstract network to visualize conflicts between phylogenetic trees which may correspond to such exchanges. More recently, methods were designed to reconstruct explicit phylogenetic networks (whose vertices can be interpreted as biological events) from triplet data. In this article, we link abstract and explicit networks through their combinatorial properties, by introducing the unrooted analog of level-k networks. In particular, we give an equivalence theorem between circular split systems and unrooted level-1 networks. We also show how to adapt to quartets some existing results on triplets, in order to reconstruct unrooted level-k phylogenetic networks. These results give an interesting perspective on the combinatorics of phylogenetic networks and also raise algorithmic and combinatorial questions. [ABSTRACT FROM AUTHOR]

We present an algorithm with runtime O(k2kn³m) for the following NP-complete problem [M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979, problem GT35]: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k new edges to G? This resolves the long-standing open question [H. Kaplan, R. Shamir, and R. E. Tarjan, SIAM J. Comput., 28 (1999), pp. 1906-1922; R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999; M. Serna and D. Thilikos, Bull. Eur. Assoc. Theory Comput. Sci. EATCS, 86 (2005), pp. 41-65; G. Gutin, S. Szeider, and A. Yeo, in Proceedings IWPEC 2006, Lecture Notes in Comput. Sci. 4169, Springer-Verlag, Berlin, 2006, pp. 60-71], first posed by Kaplan, Shamir, and Tarjan, of whether this problem was fixed parameter tractable. The problem has applications in profile minimization for sparse matrix computations [J. A. George and J. W. H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981; R. E. Tarjan, in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, 1976, pp. 3-22], and our results show tractability for the case of a small number k of zero elements in the envelope. Our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph and combines this with a greedy algorithm when graphs of a certain structure are reached by the search. [ABSTRACT FROM AUTHOR]

We exemplify an optimization criterion for divide-and-conquer algorithms with a technique called generic competitive graph search. The technique is then applied to solve two problems arising from biocomputing, so-called Common Connected Components and Cograph Sandwich. The first problem can be defined as follows: given two graphs on the same set of vertices, find the coarsest partition of the vertex set into subsets which induce connected subgraphs in both input graphs. The second problem is an instance of sandwich problems: given a partial subgraph of , find a partial subgraph of that is partial supergraph of (sandwich), and that is a cograph. For the former problem our generic algorithm not only achieves the current best known performance on arbitrary graphs and forests, but also improves by a factor when the input is made of planar graphs. However, our complexity for intervals graphs is slightly lower than a recent result. For the latter problem, we first study the relationship between the common connected components problem and the cograph sandwich problem, then, using our competitive graph search paradigm, we improve the computation of cograph sandwiches from down to , where is the number of vertices and of total edges. [Copyright &y& Elsevier]

We consider small world graphs as defined by Kleinberg (2000), i.e., graphs obtained from a d-dimensional mesh by adding links chosen at random according to the d-harmonic distribution. In these graphs, greedy routing performs in O(log 2 n) expected number of steps. We introduce indirect-greedy routing. We show that giving O(log 2 n) bits of topological awareness per node enables indirect-greedy routing to perform in O(log 1+1/ d n) expected number of steps in d-dimensional augmented meshes. We also show that, independently of the amount of topological awareness given to the nodes, indirect-greedy routing performs in Ω(log 1+1/ d n) expected number of steps. In particular, augmenting the topological awareness above this optimum of O(log 2 n) bits would drastically decrease the performance of indirect-greedy routing. Our model demonstrates that the efficiency of indirect-greedy routing is sensitive to the “world’s dimension,” in the sense that high dimensional worlds enjoy faster greedy routing than low dimensional ones. This could not be observed in Kleinberg’s routing. In addition to bringing new light to Milgram’s experiment, our protocol presents several desirable properties. In particular, it is totally oblivious, i.e., there is no header modification along the path from the source to the target, and the routing decision depends only on the target, and on information stored locally at each node. [ABSTRACT FROM AUTHOR]

Knowledge of associations between fungal hosts and their bacterial associates has steadily grown in recent years as the number and diversity of examinations have increased, but current knowledge is predominantly limited to a small number of fungal taxa and bacterial partners. Here, we screened for potential bacterial associates in over 700 phylogenetically diverse fungal isolates, representing 366 genera, or a tenfold increase compared with previously examined fungal genera, including isolates from several previously unexplored phyla. Both a 16 S rDNA-based exploration of fungal isolates from four distinct culture collections spanning North America, South America and Europe, and a bioinformatic screen for bacterial-specific sequences within fungal genome sequencing projects, revealed that a surprisingly diverse array of bacterial associates are frequently found in otherwise axenic fungal cultures. We demonstrate that bacterial associations with diverse fungal hosts appear to be the rule, rather than the exception, and deserve increased consideration in microbiome studies and in examinations of microbial interactions. Robinson et al. explore bacterial associations in over 700 phylogenetically diverse fungal isolates with 16 S rRNA sequencing of fungal collections from across the globe and bioinformatic screening of publicly available fungal genome sequencing projects. This study reveals that bacterial associations with fungal hosts are widespread, and represents a vast increase in the representation of explored fungal-bacterial relationships. [ABSTRACT FROM AUTHOR]

Bacteria–fungi interactions (BFIs) are essential in ecosystem functioning. These interactions are modulated not only by local nutritional conditions but also by the physicochemical constraints and 3D structure of the environmental niche. In soils, the unsaturated and complex nature of the substrate restricts the dispersal and activity of bacteria. Under unsaturated conditions, some bacteria engage with filamentous fungi in an interaction (fungal highways) in which they use fungal hyphae to disperse. Based on a previous experimental device to enrich pairs of organisms engaging in this interaction in soils, we present here the design and validation of a modified version of this sampling system constructed using additive printing. The 3D printed devices were tested using a novel application in which a target fungus, the common coprophilous fungus Coprinopsis cinerea , was used as bait to recruit and identify bacterial partners using its mycelium for dispersal. Bacteria of the genera Pseudomonas , Sphingobacterium and Stenotrophomonas were highly enriched in association with C. cinerea. Developing and producing these new easy-to-use tools to investigate how bacteria overcome dispersal limitations in cooperation with fungi is important to unravel the mechanisms by which BFIs affect processes at an ecosystem scale in soils and other unsaturated environments. [ABSTRACT FROM AUTHOR]

In this paper we consider the Maximum Independent Set problem (MIS) on B 1 -EPG graphs, that is the one-bend (B 1) Edge intersection graphs of Paths on a Grid (EPG graphs). The graph class EPG was introduced in Golumbic et al. (2019) as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class B k -EPG denotes EPG-graphs where every path has at most k bends. The study of MIS on B 1 -EPG graphs has been initiated in Epstein et al. (2013) where authors prove that MIS is NP-complete on B 1 -EPG graphs, and provide a polynomial 4-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on B 1 -EPG. We show that the class of k ≥ 4 subdivided graphs is a subclass of B 1 -EPG, even if there is only one shape of path and if each path has its vertical part or its horizontal part of length at most 1. This implies that there is no PTAS for MIS (and several other classical problems) on these particular B 1 -EPG graphs. On the positive side, we show that if the length of the horizontal part of every path is bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on B 1 -EPG restricted to only three shapes of path, and W [ 1 ] -hard on B 2 -EPG. The status for general B 1 -EPG (with the four shapes) is left open. [ABSTRACT FROM AUTHOR]

The Outerplanar Diameter Improvement problem asks, given a graph G and an integer D , whether it is possible to add edges to G in a way that the resulting graph is outerplanar and has diameter at most D . We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open. [ABSTRACT FROM AUTHOR]

Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour (J Comb Theory Ser B 96(4):514-528, 2006). Motivated from recent development on graph modification problems regarding classes of graphs of bounded treewidth or pathwidth, we study the Linear Rankwidth- 1 Vertex Deletion problem (shortly, LRW1- Vertex Deletion). In the LRW1- Vertex Deletion problem, given an n-vertex graph G and a positive integer k, we want to decide whether there is a set of at most k vertices whose removal turns G into a graph of linear rankwidth at most 1 and find such a vertex set if one exists. While the meta-theorem of Courcelle, Makowsky, and Rotics implies that LRW1- Vertex Deletion can be solved in time $$f(k)\cdot n^3$$ for some function f, it is not clear whether this problem allows a running time with a modest exponential function. We first establish that LRW1- Vertex Deletion can be solved in time $$8^k\cdot n^{{\mathcal {O}}(1)}$$ . The major obstacle to this end is how to handle a long induced cycle as an obstruction. To fix this issue, we define necklace graphs and investigate their structural properties. Later, we reduce the polynomial factor by refining the trivial branching step based on a cliquewidth expression of a graph, and obtain an algorithm that runs in time $$2^{{\mathcal {O}}(k)}\cdot n^4$$ . We also prove that the running time cannot be improved to $$2^{o(k)}\cdot n^{{\mathcal {O}}(1)}$$ under the Exponential Time Hypothesis assumption. Lastly, we show that the LRW1- Vertex Deletion problem admits a polynomial kernel. [ABSTRACT FROM AUTHOR]