Search

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]

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]

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]

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]

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]

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]

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]

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]

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51-63, ] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: [ABSTRACT FROM AUTHOR]

Vertex deletion and edge deletion problems play a central role in parameterized complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. The study of analogous edge contraction problems has so far been left largely unexplored from a parameterized perspective. We consider two basic problems of this type: Tree Contraction and Path Contraction. These two problems take as input an undirected graph G on n vertices and an integer k, and the task is to determine whether we can obtain a tree or a path, respectively, by a sequence of at most k edge contractions in G. For Tree Contraction, we present a randomized 4 n time polynomial-space algorithm, as well as a deterministic 4.98 n time algorithm, based on a variant of the color coding technique of Alon, Yuster and Zwick. We also present a deterministic 2+ n time algorithm for Path Contraction. Furthermore, we show that Path Contraction has a kernel with at most 5 k+3 vertices, while Tree Contraction does not have a polynomial kernel unless NP ⊆ coNP/poly. We find the latter result surprising because of the connection between Tree Contraction and Feedback Vertex Set, which is known to have a kernel with 4 k vertices. [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]

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]

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]