Search

Let C and D be hereditary graph classes. Consider the following problem: given a graph G ∈ D , find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C . We prove that it can be solved in 2 o (n) time, where n is the number of vertices of G, if the following conditions are satisfied: the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices; the graphs in D admit balanced separators of size governed by their density, e.g., O (Δ) or O (m) , where Δ and m denote the maximum degree and the number of edges, respectively; and the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D : a largest induced forest in a P t -free graph can be found in 2 O ~ (n 2 / 3) time, for every fixed t; and a largest induced planar graph in a string graph can be found in 2 O ~ (n 2 / 3) time. [ABSTRACT FROM AUTHOR]

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show a dichotomy for the former problem restricted to (H 1 , H 2) -free graphs and a dichotomy for the latter problem restricted to H -free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H -free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree (assuming P ≠ NP). We also find that Edge Steiner Tree is polynomial-time solvable for (H 1 , H 2) -free graphs if and only if the treewidth of the class of (H 1 , H 2) -free graphs is bounded (subject to P ≠ NP). To obtain the latter result, we determine all pairs (H 1 , H 2) for which the class of (H 1 , H 2) -free graphs has bounded treewidth. [ABSTRACT FROM AUTHOR]

An independency (cliquy) tree of an n -vertex graph G is a spanning tree of G in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most ℓ leaves exists parameterized by ℓ are either Para - NP - or W[1] -hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is Para - NP -hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number k of internal vertices has an O ∗ (4 k) -time algorithm and a 2 k vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number k of internal vertices both have an O ∗ (1 8 k) -time algorithm and an O (k 2 k) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an O (3 n ⋅ f (n)) -time algorithm to find a spanning tree where the leaf set has a property that can be decided in f (n) time and has minimum or maximum size. [ABSTRACT FROM AUTHOR]

In algorithmic graph theory, a classic open question is to determine the complexity of the MAXIMUM INDEPENDENT SET problem on Pt-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t≤5 (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5-7, 2014, pp 570-581, 2014), and an algorithm for t=6 announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on P6-free graphs. CoRR, arXiv:1707.05491, 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any t≥1, there is an algorithm for MAXIMUM INDEPENDENT SET on Pt-free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in 2O(tnlogn) time on Pt-free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. SCATTERED SET is the generalization of MAXIMUM INDEPENDENT SET where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-SCATTERED SET on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges):If every component of H is a path, then d-SCATTERED SET on H-free graphs with n vertices and m edges can be solved in time 2O(|V(H)|n+mlog(n+m)), even if d is part of the input.Otherwise, assuming the Exponential-Time Hypothesis (ETH), there is no 2o(n+m)-time algorithm for d-SCATTERED SET for any fixed d≥3 on H-free graphs with n-vertices and m-edges. [ABSTRACT FROM AUTHOR]

A graph G is a ( Π A , Π B ) -graph if V ( G ) can be bipartitioned into A and B such that G [ A ] satisfies property Π A and G [ B ] satisfies property Π B . The ( Π A , Π B ) -Recognition problem is to recognize whether a given graph is a ( Π A , Π B ) -graph. There are many ( Π A , Π B ) - Recognition problems, including the recognition problems for bipartite, split, and unipolar graphs. We present efficient algorithms for many cases of ( Π A , Π B ) - Recognition based on a technique which we dub inductive recognition. In particular, we give fixed-parameter algorithms for two NP-hard ( Π A , Π B ) -Recognition problems, Monopolar Recognition and 2- Subcoloring , parameterized by the number of maximal cliques in G [ A ] . We complement our algorithmic results with several hardness results for ( Π A , Π B ) -Recognition . [ABSTRACT FROM AUTHOR]

The metric dimension of a graph G is the size of a smallest subset L ⊆ V ( G ) such that for any x , y ∈ V ( G ) with x ≠ y there is a z ∈ L such that the graph distance between x and z differs from the graph distance between y and z . Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree 6 is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs. [ABSTRACT FROM AUTHOR]

We consider the Steiner Multicut problem, which asks, given an undirected graph G , a collection T = { T 1 , … , T t } , T i ⊆ V ( G ) , of terminal sets of size at most p , and an integer k , whether there is a set S of at most k edges or nodes such that of each set T i at least one pair of terminals is in different connected components of G − S . We provide a dichotomy of the parameterized complexity of Steiner Multicut . For any combination of k , t , p , and the treewidth tw ( G ) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable, W [ 1 ] -hard, or (para-) NP -complete. Our characterization includes a dichotomy for Steiner Multicut on trees as well as a polynomial time versus NP -hardness dichotomy (by restricting k , t , p , tw ( G ) to constant or unbounded). [ABSTRACT FROM AUTHOR]

A path in an edge-colored graph is rainbow if no two edges of it are colored the same, and the graph is rainbow-connected if there is a rainbow path between each pair of its vertices. The minimum number of colors needed to rainbow-connect a graph G is the rainbow connection number of G , denoted by rc (G). A simple way to rainbow-connect a graph G is to color the edges of a spanning tree with distinct colors and then re-use any of these colors to color the remaining edges of G. This proves that rc (G) ≤ | V (G) | − 1. We ask whether there is a stronger connection between tree-like structures and rainbow coloring than that is implied by the above trivial argument. For instance, is it possible to find an upper bound of t (G) − 1 for rc (G) , where t (G) is the number of vertices in the largest induced tree of G ? The answer turns out to be negative, as there are counter-examples that show that even c ⋅ t (G) is not an upper bound for rc (G) for any given constant c. In this work we show that if we consider the forest number f (G) , the number of vertices in a maximum induced forest of G , instead of t (G) , then surprisingly we do get an upper bound. More specifically, we prove that rc (G) ≤ f (G) + 2. Our result indicates a stronger connection between rainbow connection and tree-like structures than that was suggested by the simple spanning tree based upper bound. [ABSTRACT FROM AUTHOR]