Search

Let $\mathcal{C}$ and $\mathcal{D}$ be hereditary graph classes. Consider the following problem: given a graph $G\in\mathcal{D}$, find a largest, in terms of the number of vertices, induced subgraph of $G$ that belongs to $\mathcal{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 $\mathcal{C}$ are sparse, i.e., they have linearly many edges in terms of the number of vertices; * the graphs in $\mathcal{D}$ admit balanced separators of size governed by their density, e.g., $\mathcal{O}(\Delta)$ or $\mathcal{O}(\sqrt{m})$, where $\Delta$ 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 $\mathcal{C}$ and $\mathcal{D}$: * a largest induced forest in a $P_t$-free graph can be found in $2^{\tilde{\mathcal{O}}(n^{2/3})}$ time, for every fixed $t$; and * a largest induced planar graph in a string graph can be found in $2^{\tilde{\mathcal{O}}(n^{3/4})}$ time., Comment: Appeared on IPEC 2019

A fundamental graph problem is to recognize whether the vertex set of a graph $G$ can be bipartitioned into sets $A$ and $B$ such that $G[A]$ and $G[B]$ satisfy properties $\Pi_A$ and $\Pi_B$, respectively. This so-called $(\Pi_A,\Pi_B)$-Recognition problem generalizes amongst others the recognition of $3$-colorable, bipartite, split, and monopolar graphs. In this paper, we study whether certain fixed-parameter tractable $(\Pi_A,\Pi_B)$-Recognition problems admit polynomial kernels. In our study, we focus on the first level above triviality, where $\Pi_A$ is the set of $P_3$-free graphs (disjoint unions of cliques, or cluster graphs), the parameter is the number of clusters in the cluster graph $G[A]$, and $\Pi_B$ is characterized by a set $\mathcal{H}$ of connected forbidden induced subgraphs. We prove that, under the assumption that NP is not a subset of coNP/poly, \textsc{$(\Pi_A,\Pi_B)$-Recognition} admits a polynomial kernel if and only if $\mathcal{H}$ contains a graph with at most $2$ vertices. In both the kernelization and the lower bound results, we exploit the properties of a pushing process, which is an algorithmic technique used recently by Heggerness et al. and by Kanj et al. to obtain fixed-parameter algorithms for many cases of $(\Pi_A,\Pi_B)$-Recognition, as well as several other problems., Comment: Full version of the corresponding article in the Proceedings of the 26th Annual European Symposium on Algorithms (ESA '18), 35 pages, 7 figures

In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on $$P_t$$ -free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for $$t\le 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 $${P}_6$$ -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\ge 1$$ , there is an algorithm for Maximum Independent Set on $$P_t$$ -free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in $$2^{\mathcal {O}(\sqrt{tn \log n})}$$ time on $$P_t$$ -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)

The Steiner Multicut problem asks, given an undirected graph G, terminals sets T1,...,Tt $\subseteq$ V(G) of size at most p, and an integer k, whether there is a set S of at most k edges or nodes s.t. of each set Ti at least one pair of terminals is in different connected components of G \ S. This problem generalizes several graph cut problems, in particular the Multicut problem (the case p = 2), which is fixed-parameter tractable for the parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. We provide a dichotomy of the parameterized complexity of Steiner Multicut. That is, 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 or that the problem is hard (W[1]-hard or even (para-)NP-complete). We highlight that: - The edge deletion version of Steiner Multicut is fixed-parameter tractable for the parameter k+t on general graphs (but has no polynomial kernel, even on trees). We present two proofs: one using the randomized contractions technique of Chitnis et al, and one relying on new structural lemmas that decompose the Steiner cut into important separators and minimal s-t cuts. - In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k+t on general graphs. - All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p=3 and the graph is a tree plus one node. Hence, the results of Marx and Razgon, and Bousquet et al. do not generalize to Steiner Multicut. Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1), and a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded)., As submitted to journal. This version also adds a proof of fixed-parameter tractability for parameter k+t using the technique of randomized contractions

The Induced Disjoint Paths problem is to test whether an graph G on n vertices with k distinct pairs of vertices ( s i , t i ) contains paths P 1 , ź , P k such that P i connects s i and t i for i = 1 , ź , k , and P i and P j have neither common vertices nor adjacent vertices (except perhaps their ends) for 1 ź i < j ź k . We present a linear-time algorithm that solves Induced Disjoint Paths and finds the corresponding paths (if they exist) on circular-arc graphs. For interval graphs, we exhibit a linear-time algorithm for the generalization of Induced Disjoint Paths where the pairs ( s i , t i ) are not necessarily distinct. In both cases, if a representation of the graph is given, then the algorithms run in O ( n + k ) time.

The Firefighter problem aims to save as many vertices of a graph as possible from a fire that starts in a vertex and spreads through the graph. At every time step a new firefighter may be placed on some vertex, and then the fire advances to every vertex that is not protected by a firefighter and has a neighbor on fire. The problem is notoriously hard: it is NP-hard even when the input graph is a bipartite graph or a tree of maximum degree 3, it is NP-hard to approximate within n 1 - ? for any ? 0 , and it is W 1 -hard when parameterized by the number of saved vertices. We show that Firefighter can be solved in polynomial time on interval graphs, split graphs, permutation graphs, and P k -free graphs for fixed k. To complement these results, we show that the problem remains NP-hard on unit disk graphs.

A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The decision problem whether a graph has a disconnected cut is called Disconnected Cut. This problem is closely related to several homomorphism and contraction problems, and fits in an extensive line of research on vertex cuts with additional properties. It is known that Disconnected Cut is NP-hard on general graphs, while polynomial-time algorithms are known for several graph classes. However, the complexity of the problem on claw-free graphs remained an open question. Its connection to the complexity of the problem to contract a claw-free graph to the 4-vertex cycle $C_4$ led Ito et al. (TCS 2011) to explicitly ask to resolve this open question. We prove that Disconnected Cut is polynomial-time solvable on claw-free graphs, answering the question of Ito et al. The centerpiece of our result is a novel decomposition theorem for claw-free graphs of diameter 2, which we believe is of independent interest and expands the research line initiated by Chudnovsky and Seymour (JCTB 2007-2012) and Hermelin et al. (ICALP 2011). On our way to exploit this decomposition theorem, we characterize how disconnected cuts interact with certain cobipartite subgraphs, and prove two further novel algorithmic results, namely Disconnected Cut is polynomial-time solvable on circular-arc graphs and line graphs.

The Induced Graph Matching problem asks to find k disjoint induced subgraphs isomorphic to a given graph H in a given graph G such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, among several other problems. We show that Induced Graph Matching is fixed-parameter tractable in k on claw-free graphs when H is a fixed connected graph, and even admits a polynomial kernel when H is a complete graph. Both results rely on a new, strong, and generic algorithmic structure theorem for claw-free graphs. Complementing the above positive results, we prove W[1]-hardness of Induced Graph Matching on graphs excluding K_1,4 as an induced subgraph, for any fixed complete graph H. In particular, we show that Independent Set is W[1]-hard on K_1,4-free graphs. Finally, we consider the complexity of Induced Graph Matching on a large subclass of claw-free graphs, namely on proper circular-arc graphs. We show that the problem is either polynomial-time solvable or NP-complete, depending on the connectivity of H and the structure of G., Conference version appeared in ESA 2012. This version is a substantial revision

International audience; TheFirefighterproblem is to place firefighters on the vertices ofa graph to prevent a fire with known starting point from lighting upthe entire graph. In each time step, a firefighter may be placed on anunburned vertex, permanently protecting it, and the fire spreads toall neighboring unprotected vertices of burning vertices. The goal isto let as few vertices burn as possible. This problem is known to beNP-complete, even when restricted to trees of maximum degree three.Initial study showed theFirefighterproblem to be fixed-parametertractable on trees in various parameterizations. In this paper, wecon-sider a generalization of this problem, where at each time stepb≥1firefighters can be deployed. Our results answer several open questionsraised by Cai et al. [8]. We show that this problem is W[1]-hard whenparameterized by the number of saved vertices, protected vertices, andburned vertices. We also investigate several combined parameteriza-tions for which the problem is fixed-parameter tractable. Some of ouralgorithms improve on previously known algorithms. We also establishlower bounds to polynomial kernelization

We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n+k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k = 0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be W[1]-hard and we design an XP algorithm for the recognition problem.

Paths P1,…,Pk in a graph G=(V,E) are said to be mutually induced if for any 1≤i

The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be permanently placed on an unburned vertex and the fire spreads to its neighborhood in the graph in so far no firefighters are protecting those vertices. The goal is to let as few vertices burn as possible. This problem is known to be NP-complete, even when restricted to bipartite graphs or to trees of maximum degree three. Initial study showed the Firefighter problem to be fixed-parameter tractable on trees in various parameterizations. We complete these results by showing that the problem is in FPT on general graphs when parameterized by the number of burned vertices, but has no polynomial kernel on trees, resolving an open problem. Conversely, we show that the problem is W[1]-hard when parameterized by the number of unburned vertices, even on bipartite graphs. For both parameterizations, we additionally give refined algorithms on trees, improving on the running times of the known algorithms.

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k≥8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k≤3 the problem becomes polynomially time solvable. publishedVersion