Search

Given a graph and two vertex sets satisfying a certain feasibility condition, a reconfiguration problem asks whether we can reach one vertex set from the other by repeating prescribed modification steps while maintaining feasibility. In this setting, as reported by Mouawad et al. (IPEC, Springer, Berlin, 2014) presented an algorithmic meta-theorem for reconfiguration problems that says if the feasibility can be expressed in monadic second-order logic (MSO), then the problem is fixed-parameter tractable parameterized by treewidth + ℓ , where ℓ is the number of steps allowed to reach the target set. On the other hand, it is shown by Wrochna (J Comput Syst Sci 93:1–10, 2018). https://doi.org/10.1016/j.jcss.2017.11.003) that if ℓ is not part of the parameter, then the problem is PSPACE-complete even on graphs of constant bandwidth. In this paper, we present the first algorithmic meta-theorems for the case where ℓ is not part of the parameter, using some structural graph parameters incomparable with bandwidth. We show that if the feasibility is defined in MSO, then the reconfiguration problem under the so-called token jumping rule is fixed-parameter tractable parameterized by neighborhood diversity. We also show that the problem is fixed-parameter tractable parameterized by treedepth + k , where k is the size of sets being transformed. We finally complement the positive result for treedepth by showing that the problem is PSPACE-complete on forests of depth 3. [ABSTRACT FROM AUTHOR]

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP -complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on O (k 2) vertices. [ABSTRACT FROM AUTHOR]

A map is a partition of the sphere into interior-disjoint regions homeomorphic to closed disks. Some regions are labeled as nations, while the remaining ones are labeled as holes. A map in which at most k nations touch at the same point is a k-map, while it is hole-free if it contains no holes. A graph is a map graph if there is a bijection between its vertices and the nations of a map, such that two nations touch if and only the corresponding vertices are connected by an edge. We present a fixed-parameter tractable algorithm for recognizing map graphs parameterized by treewidth. Its time complexity is linear in the size of the graph. It reports a certificate in the form of a so-called witness, if the input is a yes-instance. Our algorithmic framework is general enough to test, for any k, if the input graph admits a k-map or a hole-free k-map. [ABSTRACT FROM AUTHOR]

We study the model checking problem of an extended MSO with local and global cardinality constraints, called MSO Lin GL , introduced recently by Knop et al. (Log Methods Comput Sci, 15(4), 2019. https://doi.org/10.23638/LMCS-15(4:12)2019). We show that the problem is fixed-parameter tractable parameterized by vertex integrity, where vertex integrity is a graph parameter standing between vertex cover number and treedepth. Our result thus narrows the gap between the fixed-parameter tractability parameterized by vertex cover number and the W[1]-hardness parameterized by treedepth. [ABSTRACT FROM AUTHOR]

A graph G is weakly γ -closed if every induced subgraph of G contains one vertex v such that for each non-neighbor u of v it holds that | N (u) ∩ N (v) | < γ . The weak closure γ (G) of a graph, recently introduced by Fox et al. (SIAM J Comput 49(2):448–464, 2020), is the smallest number such that G is weakly γ -closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. (2020) on clique enumeration, we show that several problems related to finding dense subgraphs, such as the enumeration of bicliques and s-plexes, are fixed-parameter tractable with respect to γ (G) . Moreover, we show that the problem of determining whether a weakly γ -closed graph G has a subgraph on at least k vertices that belongs to a graph class G which is closed under taking subgraphs admits a kernel with at most γ k 2 vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by γ + k where k is the solution size. Furthermore, we show that Independent Dominating Set does not admit a polynomial kernel for constant γ under standard assumptions. [ABSTRACT FROM AUTHOR]

We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number c and weak closure number γ (Fox et al. SIAM J Comput 49(2):448–464, 2020) in addition to the standard parameter solution size k. The weak closure number γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size k O (γ) , k O (γ) , and (γ k) O (γ) , respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size k o (γ) by previous results on their kernelization complexity on degenerate graphs (Cygan et al. ACM Trans Algorithms 13(3):43:1–43:22, 2017). For Capacitated Vertex Cover, we show that even a kernel of size k o (c) is unlikely. In contrast, for Connected Vertex Cover, we obtain a kernel with O (c k 2) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class G admits a kernel of size k O (γ) when G contains all complete and all edgeless graphs. Finally, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number c and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs. [ABSTRACT FROM AUTHOR]

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. A widely-studied special case are edge-colored graphs, where a compatible walk is forbidden to take two edges of the same color in a row. We initiate the study of fundamental problems on finding paths, cycles and walks in forbidden-transition graphs from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth for finding a compatible Hamiltonian cycle in the edge-colored graph setting. [ABSTRACT FROM AUTHOR]

In the F -Minor-Free Deletion problem one is given an undirected graph G , an integer k , and the task is to determine whether there exists a vertex set S of size at most k , so that G - S contains no graph from the finite family F as a minor. It is known that whenever F contains at least one planar graph, then F -Minor-Free Deletion admits a polynomial kernel, that is, there is a polynomial-time algorithm that outputs an equivalent instance of size k O (1) [Fomin, Lokshtanov, Misra, Saurabh; FOCS 2012]. However, this result relies on non-constructive arguments based on well-quasi-ordering and does not provide a concrete bound on the kernel size. We study the Outerplanar Deletion problem, in which we want to remove at most k vertices from a graph to make it outerplanar. This is a special case of F -Minor-Free Deletion for the family F = { K 4 , K 2 , 3 } . The class of outerplanar graphs is arguably the simplest class of graphs for which no explicit kernelization size bounds are known. By exploiting the combinatorial properties of outerplanar graphs we present elementary reduction rules decreasing the size of a graph. This yields a constructive kernel with O ( k 4) vertices and edges. As a corollary, we derive that any minor-minimal obstruction to having an outerplanar deletion set of size k has O ( k 4) vertices and edges. [ABSTRACT FROM AUTHOR]

We study a natural variant of scheduling that we call partial scheduling: in this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f (k) n O (1) or n O (f (k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in P , N P -complete and fixed-parameter tractable by k, or W [ 1 ] -hard parameterized by k. Second, for many interesting cases we further investigate the runtime on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an O (8 k k (| V | + | E |)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V , E) is the graph with precedence constraints. [ABSTRACT FROM AUTHOR]

Graph Burning asks, given a graph G = (V , E) and an integer k, whether there exists (b 0 , ⋯ , b k - 1) ∈ V k such that every vertex in G has distance at most i from some b i . This problem is known to be NP-complete even on connected caterpillars of maximum degree 3. We study the parameterized complexity of this problem and answer all questions by Kare and Reddy [IWOCA 2019] about the parameterized complexity of the problem. We show that the problem is W[2]-complete parameterized by k and that it does not admit a polynomial kernel parameterized by vertex cover number unless NP ⊆ coNP / poly . We also show that the problem is fixed-parameter tractable parameterized by clique-width plus the maximum diameter among all connected components. This implies the fixed-parameter tractability parameterized by modular-width, by treedepth, and by distance to cographs. Using a different technique, we show that parameterization by distance to split graphs is also tractable. We finally show that the problem parameterized by max leaf number is XP. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , A ⊆ V , and integers k and ℓ , the (A , ℓ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly ℓ that have endpoints in A and internal points in V \ A . We study the parameterized complexity of this problem with parameters |A|, ℓ , k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when ℓ ≤ 3 , while it is NP-complete for constant ℓ ≥ 4 . We also show that the problem is W[1]-hard parameterized by pathwidth + | A | , while it is fixed-parameter tractable parameterized by treewidth + ℓ . Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at most ℓ . We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or ℓ is a constant. [ABSTRACT FROM AUTHOR]

For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that (1) the subgraph induced by each cluster is drawn in the interior of the corresponding disk, (2) each edge intersects any disk at most once, and (3) the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA'95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT (resp., XP) algorithm for embedded flat (resp., non-flat) clustered graphs, when parameterized by the carving-width of the dual graph of the input. These are the first FPT and XP algorithms for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. In particular, our algorithm runs in quadratic time for flat instances of bounded treewidth and bounded face size. To further strengthen the relevance of this result, we show that an algorithm with running time O(r(n)) for flat instances whose underlying graph has pathwidth 1 would result in an algorithm with running time O(r(n)) for flat instances and with running time O (r (n 2) + n 2) for general, possibly non-flat, instances. [ABSTRACT FROM AUTHOR]

We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural variant of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is hard: it has no efficient exp (- O (log n / log log n)) -approximation under the exponential time hypothesis, where n is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient exp (- O (log 0.63 n)) -approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming P ≠ NP . In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on n vertices contains a binary tree of size k in 2 k poly (n) time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas, ANALCO 2011, which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs. [ABSTRACT FROM AUTHOR]

We investigate the effect of crossover in the context of parameterized complexity on a well-known fixed-parameter tractable combinatorial optimization problem known as the closest string problem. We prove that a multi-start (μ +1) GA solves arbitrary length-n instances of closest string in 2 O (d 2 + d log k) · t (n) steps in expectation. Here, k is the number of strings in the input set, d is the value of the optimal solution, and n ≤ t (n) ≤ poly (n) is the number of iterations allocated to the (μ +1) GA before a restart, which can be an arbitrary polynomial in n. This confirms that the multi-start (μ +1) GA runs in randomized fixed-parameter tractable (FPT) time with respect to the above parameterization. On the other hand, if the crossover operation is disabled, we show there exist instances that require n Ω (log (d + k)) steps in expectation. The lower bound asserts that crossover is a necessary component in the FPT running time. [ABSTRACT FROM AUTHOR]

We introduce a dynamic version of the NP-hard graph modification problem Cluster Editing. The essential point here is to take into account dynamically evolving input graphs: having a cluster graph (that is, a disjoint union of cliques) constituting a solution for a first input graph, can we cost-efficiently transform it into a "similar" cluster graph that is a solution for a second ("subsequent") input graph? This model is motivated by several application scenarios, including incremental clustering, the search for compromise clusterings, or also local search in graph-based data clustering. We thoroughly study six problem variants (three modification scenarios edge editing, edge deletion, edge insertion; each combined with two distance measures between cluster graphs). We obtain both fixed-parameter tractability as well as (parameterized) hardness results, thus (except for three open questions) providing a fairly complete picture of the parameterized computational complexity landscape under the two perhaps most natural parameterizations: the distances of the new "similar" cluster graph to (1) the second input graph and to (2) the input cluster graph. [ABSTRACT FROM AUTHOR]

We study a class of multi-scenario single-machine scheduling problems. In this class of problems, we are given a set of scenarios with each one having a different realization of job characteristics. We consider these multi-scenario problems where the scheduling criterion can be any one of the following three: The total weighted completion time, the weighted number of tardy jobs, and the weighted number of jobs completed exactly at their due-date. As all the resulting problems are NP-hard, our analysis focuses on whether any one of the problems becomes tractable when some specific natural parameters are of limited size. The analysis includes the following parameters: The number of jobs with scenario-dependent processing times, the number of jobs with scenario-dependent weights, and the number of different due-dates. [ABSTRACT FROM AUTHOR]

We show that a problem of deleting a minimum number of vertices from a graph to obtain a graph embeddable on a surface of a given Euler genus is solvable in time 2 C g · k 2 log k n O (1) , where k is the size of the deletion set, C g is a constant depending on the Euler genus g of the target surface, and n is the size of the input graph. On the way to this result, we develop an algorithm solving the problem in question in time 2 O ((t + g) log (t + g)) n given a tree decomposition of the input graph of width t. The results generalize previous algorithms for the surface being a sphere by Marx and Schlotter (Algorithmica 62(3–4):807–822, 2012. 10.1007/s00453-010-9484-z), Kawarabayashi (in: 50th annual IEEE symposium on foundations of computer science, FOCS 2009, IEEE Computer Society, pp 639–648, 2009. 10.1109/FOCS.2009.45) and Jansen et al. (in: Chekuri (ed) 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, SIAM, pp 1802–1811, 2014. 10.1137/1.9781611973402.130). [ABSTRACT FROM AUTHOR]

There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed graphs; herein, we focus on arc insertions. To this end, we develop a general two-stage framework which consists of efficiently solving a problem-specific number problem and transferring its solution to a solution for the graph problem by applying flow computations. In this way, we obtain fixed-parameter tractability and polynomial kernelizability results, with the central parameter being the maximum vertex in- or outdegree of the output digraph. Although there are certain similarities with the much better studied undirected case, the flow computation used in the directed case seems not to work for the undirected case while f-factor computations as used in the undirected case seem not to work for the directed case. [ABSTRACT FROM AUTHOR]

A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics. For a target treewidthk, suppose the heuristic has already computed a partial elimination order of width at most k, but extending it by one more vertex exceeds the target width k. At this moment of regret, we solve a subproblem which is to recompute the last c positions of the partial elimination order such that it can be extended without exceeding width k. We show that this subproblem is fixed-parameter tractable when parameterized by k and c, but it is para-NP-hard and W[1]-hard when parameterized by only k or c, respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for the quality of the solution. [ABSTRACT FROM AUTHOR]

Cutwidth is one of the classic layout parameters for graphs. It measures how well one can order the vertices of a graph in a linear manner, so that the maximum number of edges between any prefix and its complement suffix is minimized. As graphs of cutwidth at most k are closed under taking immersions, the results of Robertson and Seymour imply that there is a finite list of minimal immersion obstructions for admitting a cut layout of width at most k. We prove that every minimal immersion obstruction for cutwidth at most k has size at most 2O(k3logk). As an interesting algorithmic byproduct, we design a new fixed-parameter algorithm for computing the cutwidth of a graph that runs in time 2O(k2logk)·n, where k is the optimum width and n is the number of vertices. While being slower by a logk-factor in the exponent than the fastest known algorithm, given by Thilikos et al. (J Algorithms 56(1):1-24, 2005; J Algorithms 56(1):25-49, 2005), our algorithm has the advantage of being simpler and self-contained; arguably, it explains better the combinatorics of optimum-width layouts. [ABSTRACT FROM AUTHOR]

Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). The common task of these two problems is to create so-called probe sequences (essentially a string) in a microarray. Here, the goal of the former problem is to determine an assignment of each probe sequence to a unique cell of the array and afterwards to construct the sequences at their respective cells while minimizing the border length of the probes. In contrast, for the latter problem the assignment of the probes to the cells is already given. In this paper we investigate the parameterized complexity of the natural exhaustive variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input (ℓ) and the number of rows of the microarray (r); and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and ℓ. We complement our tractability results with a number of corresponding hardness results. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of various graph theoretic problems in the dynamic framework where the input graph is being updated by a sequence of edge additions and deletions. Vertex subset problems on graphs typically deal with finding a subset of vertices having certain properties. In real world applications, the graph under consideration often changes over time and due to this dynamics, the solution at hand might lose the desired properties. The goal in the area of dynamic graph algorithms is to efficiently maintain a solution under these changes. Recomputing a new solution on the new graph is an expensive task especially when the number of modifications made to the graph is significantly smaller than the size of the graph. In the context of parameterized algorithms, two natural parameters are the size k of the symmetric difference of the edge sets of the two graphs (on n vertices) and the size r of the symmetric difference of the two solutions. We study the DYNAMICΠ-DELETION problem which is the dynamic variant of the classical Π-DELETION problem and show NP-hardness, fixed-parameter tractability and kernelization results. For specific cases of DYNAMICΠ-DELETION such as DYNAMIC VERTEX COVER and DYNAMIC FEEDBACK VERTEX SET, we describe improved algorithms and linear kernels. Specifically, we show that DYNAMIC VERTEX COVER has a deterministic algorithm with 1.0822knO(1) running time and DYNAMIC FEEDBACK VERTEX SET has a randomized algorithm with 1.6667knO(1) running time. We also show that DYNAMIC CONNECTED FEEDBACK VERTEX SET can be solved in 2O(k)nO(1) time. For each of DYNAMIC CONNECTED VERTEX COVER, DYNAMIC DOMINATING SET and DYNAMIC CONNECTED DOMINATING SET, we describe an algorithm with 2knO(1) running time and show that this is the optimal running time (up to polynomial factors) assuming the Set Cover Conjecture. [ABSTRACT FROM AUTHOR]

In the deletion version of the list homomorphism problem, we are given graphs G and H, a list $$L(v)\subseteq V(H)$$ for each vertex $$v\in V(G)$$ , and an integer k. The task is to decide whether there exists a set $$W \subseteq V(G)$$ of size at most k such that there is a homomorphism from $$G {\setminus } W$$ to H respecting the lists. We show that DL-Hom( $${H}$$ ), parameterized by k and | H|, is fixed-parameter tractable for any $$(P_6,C_6)$$ -free bipartite graph H; already for this restricted class of graphs, the problem generalizes Vertex Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the size of the cutset and the number of terminals. We conjecture that DL-Hom( $${H}$$ ) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable; by a result of Feder et al. (Combinatorica 19(4):487-505, 1999), a graph H belongs to this class precisely if it is a bipartite graph whose complement is a circular arc graph. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT. [ABSTRACT FROM AUTHOR]

The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of $${\mathcal O}(1.79^{\mathsf {run}(T)}\cdot n\cdot k)$$ , where $$\mathsf {run}(T)$$ denotes the number of alternating runs of T. This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since $$\mathsf {run}(T)

We present efficient fixed-parameter and approximation algorithms for the NP-hard problem of computing a maximum agreement forest (MAF) of a pair of multifurcating (nonbinary) rooted trees. Multifurcating trees arise naturally as a result of statistical uncertainty in current tree construction methods. The size of an MAF corresponds to the subtree prune-and-regraft distance of the two trees and is intimately connected to their hybridization number. These distance measures are essential tools for understanding reticulate evolution, such as lateral gene transfer, recombination, and hybridization. Our algorithms nearly match the running times of the currently best algorithms for the binary case. This is achieved using a combination of efficient branching rules (similar to but more complex than in the binary case) and a novel edge protection scheme that further reduces the size of the search space the algorithms need to explore. [ABSTRACT FROM AUTHOR]

We study parameterized complexity of a generalization of the classical Feedback Vertex Set problem, namely the Group Feedback Vertex Set problem: we are given a graph $$G$$ with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of $$G$$ that evaluate to a non-null element of the group. This problem generalizes not only Feedback Vertex Set, but also Subset Feedback Vertex Set, Multiway Cut and Odd Cycle Transversal . Completing the results of Guillemot (Discrete Optim 8(1):61-71, ), we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a blackbox performing group operations. [ABSTRACT FROM AUTHOR]

The article examines the parameterized complexity of the restriction of the Test Cover problem (T-r-C) in which each edge possesses a maximum of r ≥ 2 vertices. It states that two below-bound parameterizations of T-r-C are fixed-parameter tractable with polynomial kernels: deciding if a test cover of size n - k exists, and deciding if a test cover of size m - k exists where k is the parameter. It also talks about the lower bound on the minimum size of test covers.

We study the boundary of tractability for the Max-Cut problem in graphs. Our main result shows that Max-Cut parameterized above the Edwards-Erdős bound is fixed-parameter tractable: we give an algorithm that for any connected graph with n vertices and m edges finds a cut of size in time 2⋅ n, or decides that no such cut exists. This answers a long-standing open question from parameterized complexity that has been posed a number of times over the past 15 years. Our algorithm has asymptotically optimal running time, under the Exponential Time Hypothesis, and is strengthened by a polynomial-time computable kernel of polynomial size. [ABSTRACT FROM AUTHOR]

Homogeneous team formation is the task of grouping individuals into teams, each of which consists of members who fulfill the same set of prespecified properties. In this theoretical work, we propose, motivate, and analyze a combinatorial model where, given a matrix over a finite alphabet whose rows correspond to individuals and columns correspond to attributes of individuals, the user specifies lower and upper bounds on team sizes as well as combinations of attributes that have to be homogeneous (that is, identical) for all members of the corresponding teams. Furthermore, the user can define a cost for assigning any individual to a certain team. We show that some special cases of our new model lead to NP-hard problems while others allow for (fixed-parameter) tractability results. For example, the problem is already NP-hard even if (i) there are no lower and upper bounds on the team sizes, (ii) all costs are zero, and (iii) the matrix has only two columns. In contrast, the problem becomes fixed-parameter tractable for the combined parameter 'number of possible teams' and 'number of different individuals', the latter being upper-bounded by the number of rows. [ABSTRACT FROM AUTHOR]

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 $$\mathsf {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 $$\mathsf {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 $$\mathsf {NP}$$ -complete, depending on the connectivity of $$H$$ and the structure of $$G$$ . [ABSTRACT FROM AUTHOR]

In the Parameterized Connected Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there is a set S of at most k vertices in G-a connected dominating set of G-such that (i) S is a dominating set of G, and (ii) the subgraph G[ S] induced by S is connected; the parameter is k. The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. Parameterized Connected Dominating Set is W[2]-hard, and therefore it is unlikely (Downey and Fellows, Parameterized Complexity, Springer, ) that the problem has fixed-parameter tractable (FPT) algorithms or polynomial kernels in graphs in general. We investigate the effect of excluding short cycles, as subgraphs, on the kernelization complexity of Parameterized Connected Dominating Set. The girth of a graph G is the length of a shortest cycle in G. It turns out that the Parameterized Connected Dominating Set problem is hard on graphs with small cycles, and becomes progressively easier as the girth increases. More precisely, we obtain the following kernelization landscape: Parameterized Connected Dominating Set While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs. [ABSTRACT FROM AUTHOR]

Given a bipartite graph G=( V, V, E) and a nonnegative integer k, the NP-complete Minimum-Flip Consensus Tree problem asks whether G can be transformed, using up to k edge insertions and deletions, into a graph that does not contain an induced P with its first vertex in V (a so-called M-graph or Σ-graph). This problem plays an important role in computational phylogenetics, V standing for the characters and V standing for taxa. Chen et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3:165-173, ). showed that Minimum-Flip Consensus Tree is NP-complete and presented a parameterized algorithm with running time O(6⋅| V|⋅| V|). Subsequently, Böcker et al. (ACM Trans. Algorithms 8:7:1-7:17, ) presented a refined search tree algorithm with running time O(4.42(| V|+| V|)+| V|⋅| V|). We continue the study of Minimum-Flip Consensus Tree parameterized by k. Our main contribution are polynomial-time executable data reduction rules yielding a problem kernel with O( k) vertices. In addition, we present an improved search tree algorithm with running time O(3.68⋅| V|| V|). [ABSTRACT FROM AUTHOR]

We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity of various versions: undirected or directed graphs, vertex or edge deletions, with or without the requirement of connectivity, etc. The collection of results shows an interesting contrast: while the node-deletion variants remain intractable, i.e., W[1]-hard for all the studied cases, edge-deletion problems are either fixed-parameter tractable or polynomial-time solvable. Of particular interest is a randomized FPT algorithm for making an undirected graph Eulerian by deleting the minimum number of edges, based on a novel application of the color coding technique. For versions that remain NP-complete but fixed-parameter tractable we consider also possibilities of polynomial kernelization; unfortunately, we prove that this is not possible unless NP⊆coNP/poly. [ABSTRACT FROM AUTHOR]

We extend previous work on the parameterized complexity of local search for the Traveling Salesperson Problem (TSP). So far, its parameterized complexity has been investigated with respect to the distance measures (defining the local search area) 'Edge Exchange' and 'Max-Shift'. We perform studies with respect to the distance measures 'Swap' and ' r-Swap', 'Reversal' and ' r-Reversal', and 'Edit', achieving both fixed-parameter tractability and W[1]-hardness results. In particular, from the parameterized reduction showing W[1]-hardness we infer running time lower bounds (based on the exponential time hypothesis) for all corresponding distance measures. Moreover, we provide non-existence results for polynomial-size problem kernels and we show that some in general W[1]-hard problems turn fixed-parameter tractable when restricted to planar graphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider multi-objective evolutionary algorithms for the Vertex Cover problem in the context of parameterized complexity. We consider two different measures for the problem. The first measure is a very natural multi-objective one for the use of evolutionary algorithms and takes into account the number of chosen vertices and the number of edges that remain uncovered. The second fitness function is based on a linear programming formulation and proves to give better results. We point out that both approaches lead to a kernelization for the Vertex Cover problem. Based on this, we show that evolutionary algorithms solve the vertex cover problem efficiently if the size of a minimum vertex cover is not too large, i.e., the expected runtime is bounded by O( f(OPT)⋅ n), where c is a constant and f a function that only depends on OPT. This shows that evolutionary algorithms are randomized fixed-parameter tractable algorithms for the vertex cover problem. [ABSTRACT FROM AUTHOR]

We introduce the NP-hard graph-based data clustering problem s- Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s−1 other vertices; cliques are 1-plexes. We propose a new method based on 'approximation and tidying' for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing 'approximation and tidying', we develop data reduction rules that, in O( ksn) time, transform an s- Plex Cluster Vertex Deletion instance with n vertices into an equivalent instance with O( k s) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method. [ABSTRACT FROM AUTHOR]

A binary tanglegram is a drawing of a pair of rooted binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example, in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a tanglegram with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for binary trees. We show that the problem is NP-hard even if both trees are complete binary trees. For this case we give an O( n)-time 2-approximation and a new, simple fixed-parameter algorithm. We show that the maximization version of the dual problem for binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation. [ABSTRACT FROM AUTHOR]

Given n points, called terminals, in the plane ℝ and a positive integer k, the bottleneck Steiner tree problem is to find k Steiner points from ℝ and a spanning tree on the n+ k points that minimizes its longest edge length. Edge length is measured by an underlying distance function on ℝ, usually, the Euclidean or the L metric. This problem is known to be NP-hard. In this paper, we study this problem in the L metric for any 1≤ p≤∞, and aim to find an exact algorithm which is efficient for small fixed k. We present the first fixed-parameter tractable algorithm running in f( k)⋅ nlog n time for the L and the L metrics, and the first exact algorithm for the L metric for any fixed rational p with 1< p<∞ whose time complexity is f( k)⋅( n+ nlog n), where f( k) is a function dependent only on k. Note that prior to this paper there was no known exact algorithm even for the L metric. [ABSTRACT FROM AUTHOR]

The Cluster Editing problem is defined as follows: Given an undirected, loopless graph, we want to find a set of edge modifications (insertions and deletions) of minimum cardinality, such that the modified graph consists of disjoint cliques. We present empirical results for this problem using exact methods from fixed-parameter algorithmics and linear programming. We investigate parameter-independent data reduction methods and find that effective preprocessing is possible if the number of edge modifications k is smaller than some multiple of $\lvert V\rvert$ , where V is the vertex set of the input graph. In particular, combining parameter-dependent data reduction with lower and upper bounds we can effectively reduce graphs satisfying $k\leq25\lvert V\rvert$ . In addition to the fastest known fixed-parameter branching strategy for the problem, we investigate an integer linear program (ILP) formulation of the problem using a cutting plane approach. Our results indicate that both approaches are capable of solving large graphs with 1000 vertices and several thousand edge modifications. For the first time, complex and very large graphs such as biological instances allow for an exact solution, using a combination of the above techniques. (A preliminary version of this paper appeared under the title 'Exact algorithms for cluster editing: Evaluation and experiments' in the Proceedings of the 7th Workshop on Experimental Algorithms, WEA 2008, in: LNCS, vol. 5038, Springer, pp. 289-302.) [ABSTRACT FROM AUTHOR]

It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f( k)⋅ n α for some constant α not depending on k and some f depending only on k. For large values of n, such an algorithm is much better than trying all the O( n k) possibilities. Therefore, the chordal deletion problem parameterized by the number k of vertices or edges to be deleted is fixed-parameter tractable. This answers an open question of Cai (Discrete Appl. Math. 127:415–429, ). [ABSTRACT FROM AUTHOR]