Search

Fradkin and Seymour (J Comb Theory Ser B 110:19–46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk (in: Proceedings of the Algorithms—ESA 2013—21st Annual European Symposium, Sophia Antipolis, France, September 2–4, 2013, pp. 505–516, 2013), where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is a combinatorial result that proves that the yes-instances of the problems (defined above) have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, inductive reasoning and exploiting the structural properties of these digraphs. [ABSTRACT FROM AUTHOR]

In the Arc Disjoint Cycle Packing problem, we are given a simple directed graph (digraph) G, a positive integer k, and the task is to decide whether there exist k arc disjoint cycles. The problem is known to be W[1]-hard on general digraphs parameterized by the standard parameter k. In this paper we show that the problem admits a polynomial kernel on α-bounded digraphs. That is, we give a polynomial-time algorithm, that given an instance (D,k) of Arc Disjoint Cycle Packing, outputs an equivalent instance (D ′ , k ′) of Arc Disjoint Cycle Packing, such that k ′ ≤ k and the size of D ′ is upper-bounded by a polynomial function of k. For any integer α ≥ 1, the class of α-bounded digraphs, denoted by D α , contains a digraph D such that the maximum size of an independent set in D is at most α. That is, in D, any set of α + 1 vertices has an arc with both end-points in the set. For α = 1, this corresponds to the well-studied class of tournaments. Our results generalize the recent result by Bessy et al. [MFCS, 2019] about Arc Disjoint Cycle Packing on tournaments. [ABSTRACT FROM AUTHOR]

Hubs are high-degree nodes within a network, ubiquitous in complex networks such as telecommunication, biological, social and semantic networks. Here, we do not seek a hub that is a single node, but a hub consisting of k nodes. Formally, given a graph G = (V , E) , we a seek a set A ⊆ V of size k that induces a connected subgraph from which at least p edges emanate. Thus, we identify k nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). This problem, which we call Multi-Node Hub (MNH), is a variant of the classic Max Cut problem. While it is easy to see that MNH is W[1]-hard with respect to the parameter k , our main contribution is a parameterized algorithm that shows that MNH is FPT with respect to the parameter p. [ABSTRACT FROM AUTHOR]

For a family of graphs G , the G - Contraction problem takes as an input a graph G and an integer k , and the goal is to decide if there exists a subset F ⊆ E (G) of size at most k such that G / F is in G. Here, G / F is the graph obtained from G by contracting all the edges in F. In this article, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time 2 O (k) ⋅ | V (G) | O (1) , for this problem. We complement this result by proving that unless ETH fails, there is no algorithm for Grid Contraction with running time 2 o (k) ⋅ | V (G) | O (1). We also present a polynomial kernel for this problem. [ABSTRACT FROM AUTHOR]

In the Maximum Degree Contraction problem, the input is a graph G on n vertices, and integers k, d, and the objective is to check whether G can be transformed into a graph of maximum degree at most d, using at most k edge contractions. A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time n O (k) . As our first result, we prove that this algorithm is asymptotically optimal, upto constants in the exponents, under Exponential Time Hypothesis (ETH). Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of parameterized complexity and proved, among other things, that it admits an FPT algorithm running in time (d + k) 2 k · n O (1) = 2 O (k log (k + d)) · n O (1) , and remains NP-hard for every constant d ≥ 2 (Acta Informatica (2014)). We present a different FPT algorithm that runs in time 2 O (d k) · n O (1) . In particular, our algorithm runs in time 2 O (k) · n O (1) , for every fixed d. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by k + d . We answer this question in the negative and prove that it does not admit a polynomial compression unless NP ⊆ coNP / p o l y . [ABSTRACT FROM AUTHOR]

Every connected graph on n vertices has a cut of size at least n − 1. We call this bound the spanning tree bound. In the Max-Cut Above Spanning Tree (Max-Cut-AST) problem, we are given a connected n-vertex graph G and a non-negative integer k, and the task is to decide whether G has a cut of size at least n − 1 + k. We show that Max-Cut-AST admits an algorithm that runs in time O (8 k n O (1)) , and hence it is fixed parameter tractable with respect to k. Furthermore, we show that Max-Cut-AST has a polynomial kernel of size O (k 5) . [ABSTRACT FROM AUTHOR]

The family of judicious partitioning problems, introduced by Bollobàs and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection, and Max Cut. While these classical problems focus solely on the minimization/maximization of the number of edges crossing the cut, judicious (bi)partitioning problems ask the natural question of the minimization/maximization of the number of edges lying in the (two) sides of the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is "judicious" in the sense that neither side is burdened by too many edges, and Balanced JB (BJB) also requires that the sizes of the sides themselves are "balanced" in the sense that neither of them is too large. Both of these problems were defined in the work by Bollobàs and Scott and have received notable scientific attention since then. In this paper, we shed light on the study of judicious partitioning problems from the viewpoint of algorithm design. Specifically, we prove that BJB is fixed parameter tractable (FPT) (which also proves that JB is FPT). [ABSTRACT FROM AUTHOR]

For a family of graphs F , the F -Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S ⊆ E(G) of size at most k such that G/S belongs to F . Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al. [Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied F -Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F -Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a "parameterized way". Let T ℓ be the family of graphs such that each graph in T ℓ can be made into a tree by deleting at most ℓ edges. Thus, the problem we study is T ℓ -Contraction. We design an FPT algorithm for T ℓ -Contraction running in time O ((2 ℓ + 2) O (k + ℓ) ⋅ n O (1)) . Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for T ℓ -Contraction of size O ([ k (k + 2 ℓ) ] (⌈ α α − 1 ⌉ + 1)) . [ABSTRACT FROM AUTHOR]

The classic K-CYCLE problem asks if a graph G, with vertex-set V(G), has a simple cycle containing all vertices of a given set K⊆V(G). In terms of colored graphs, it can be rephrased as follows: Given a graph G, a set K⊆V(G) and an injective coloring c:K→{1,2,...,|K|}, decide if G has a simple cycle containing each color in {1,2,...,|K|} exactly once. Another problem widely known since the introduction of color coding is COLORFUL CYCLE. Given a graph G and a coloring c:V(G)→{1,2,...,k} for some k∈N, it asks if G has a simple cycle of length k containing each color in {1,2,...,k} exactly once. We study a generalization of these problems: Given a graph G, a set K⊆V(G), a list-coloring L:K→2{1,2,...,k∗} for some k∗∈N and a parameter k∈N, LISTK-CYCLE asks if one can assign a color to each vertex in K so that G has a simple cycle (of arbitrary length) containing exactly k vertices from K with distinct colors. We design a randomized algorithm for LISTK-CYCLE running in time 2knO(1) on an n-vertex graph, matching the best known running times of algorithms for both K-CYCLE and COLORFUL CYCLE. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of LISTK-CYCLE that generalizes the classic HAMILTONICITY problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Björklund, Husfeldt and Taslaman (SODA'12), Björklund, Kaski and Kowalik (STACS'13), and Björklund (FOCS'10). [ABSTRACT FROM AUTHOR]

MAX-CUT is a well-known classical NP-hard problem. This problem asks whether the vertex-set of a given graph G=(V,E) can be partitioned into two disjoint subsets, A and B, such that there exist at least p edges with one endpoint in A and the other endpoint in B. It is well known that if p≤|E|/2, the answer is necessarily positive. A widely-studied variant of particular interest to parameterized complexity, called (k,n-k)-MAX-CUT, restricts the size of the subset A to be exactly k. For the (k,n-k)-MAX-CUT problem, we obtain an O∗(2p)-time algorithm, improving upon the previous best O∗(4p+o(p))-time algorithm, as well as the first polynomial kernel. Our algorithm relies on a delicate combination of methods and notions, including independent sets, depth-search trees, bounded search trees, dynamic programming and treewidth, while our kernel relies on examination of the closed neighborhood of the neighborhood of a certain independent set of the graph G. [ABSTRACT FROM AUTHOR]

In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, we are given a digraph D on n vertices and a positive integer k, and the objective is to check whether there exists a set of vertices S such that F = D − S is an acyclic digraph. In a recent paper, Mnich and van Leeuwen [STACS 2016 ] studied the kernelization complexity of DFVS with an additional restriction on F—namely that F must be an out-forest, an out-tree, or a (directed) pumpkin—with an objective of shedding some light on the kernelization complexity of the DFVS problem, a well known open problem in the area. The vertex deletion problems corresponding to obtaining an out-forest, an out-tree, or a (directed) pumpkin are OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET, respectively. They showed that OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET admit polynomial kernels. Another open problem regarding DFVS is that, does DFVS admit an algorithm with running time 2O(k)nO(1)? We complement the kernelization programme of Mnich and van Leeuwen by designing fast FPT algorithms for the above mentioned problems. In particular, we design an algorithm for OUT-FOREST VERTEX DELETION SET that runs in time O(2.732knO(1)) and algorithms for PUMPKIN/OUT-TREE VERTEX DELETION SET that runs in time O(2.562knO(1)). As a corollary of our FPT algorithms and the recent result of Fomin et al. [STOC 2016] which gives a relation between FPT algorithms and exact algorithms, we get exact algorithms for OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET that run in time O(1.633nnO(1)), O(1.609nnO(1)) and O(1.609nnO(1)), respectively. [ABSTRACT FROM AUTHOR]

In this paper we continue our study of graph modification problems defined by reducing the rank of the adjacency matrix of the given graph, and extend our results from undirected graphs to modifying the rank of skew-adjacency matrix of oriented graphs. An instance of a graph modification problem takes as input a graph G and a positive integer k, and the objective is to either delete k vertices/edges or edit k edges so that the resulting graph belongs to a particular family F of graphs. Given a fixed positive integer r, we define Fr as the family of oriented graphs where for each G∈Fr, the rank of the skew-adjacency matrix of G is at most r. Using the family Fr we do algorithmic study, both in classical and parameterized complexity, of the following graph modification problems: r-RANK VERTEX DELETION, r-RANK EDGE DELETION. We first show that both the problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2O(klogr)nO(1) for r-RANK VERTEX DELETION, and an algorithm for r-RANK EDGE DELETION running in time 2O(f(r)klogk)nO(1). In addition to our FPT results we design polynomial kernels for these problems. Our main structural result, which is the fulcrum of all our algorithmic results, is that for a fixed integer r the size of any “reduced graph” in Fr is upper bounded by 3r. This result is of independent interest and generalizes a similar result of Kotlov and Lovász regarding reduced oriented graphs of rank r. [ABSTRACT FROM AUTHOR]

Multiwinner elections have proven to be a fruitful research topic with many real-world applications. We contribute to this line of research by improving the state of the art regarding the computational complexity of computing good committees. More formally, given a set of candidates C , a set of voters V —each ranking the candidates according to their preferences, and an integer k; a multiwinner voting rule identifies a k-sized committee, based on these given voter preferences. In this paper we consider several utilitarian and egailitarian ordered weighted average scoring rules, which are an extensively-researched family of rules (and a subfamily of the family of committee scoring rules). First, we improve the result of Betzler et al. (JAIR 47:475–519, 2013), which gave a O (n n) algorithm for computing winner under the Chamberlin–Courant rule, where n is the number of voters; to a running time of O (2 n) , which is optimal. Furthermore, we study the parameterized complexity of the Pessimist voting rule and describe a few tractable and intractable cases. Apart from such utilitarian voting rules, we extend our study and consider egalitarian median and egalitarian mean (both committee scoring rules), showing some tractable and intractable results, based on nontrivial structural observations. [ABSTRACT FROM AUTHOR]

Given a digraph D and an integer k , Directed Feedback Vertex Set (DFVS) asks whether there exists a set of vertices S of size at most k such that F = D ∖ S is DAG. Mnich and van Leeuwen [ STACS 2016  ] considered the kernelization complexity of DFVS with an additional restriction on F , namely that F must be an out-forest ( Out-Forest Vertex Deletion Set ), an out-tree ( Out-Tree Vertex Deletion Set ), or a (directed) pumpkin ( Pumpkin Vertex Deletion Set ). Their objective was to shed light on the kernelization complexity of DFVS , a well-known open problem in Parameterized Complexity. We improve the kernel sizes of Out-Forest Vertex Deletion Set from O ( k 3 ) to O ( k 2 ) and of Pumpkin Vertex Deletion Set from O ( k 18 ) to O ( k 3 ) . We also prove that the former kernel size is tight under certain complexity theoretic assumptions. [ABSTRACT FROM AUTHOR]

In this paper we study a generalization of classic Feedback Vertex Set problem in the realm of multivariate complexity analysis. We say that a graph F is an l -forest if we can delete at most l edges from F to get a forest. That is, F is at most l edges away from being a forest. In this paper we introduce the Almost Forest Deletion problem, where given a graph G and integers k and l , the question is whether there exists a subset of at most k vertices such that its deletion leaves us an l -forest. We show that this problem admits an algorithm with running time 2 O ( k + l ) n O ( 1 ) and a kernel of size O ( k l ( k + l ) ) . We also show that the problem admits a 2 O ( tw ) n O ( 1 ) algorithm on bounded treewidth graphs, using which we design a subexponential algorithm for the problem on planar graphs. [ABSTRACT FROM AUTHOR]

A well known result in graph algorithms, due to Edmonds, states that given a digraph D and a positive integer $$\ell $$ , we can test whether D contains $$\ell $$ arc-disjoint out-branchings in polynomial time. However, if we ask whether there exists an out-branching and an in-branching which are arc-disjoint, then the problem becomes NP-complete. In fact, even deciding whether a digraph D contains an out-branching which is arc-disjoint from some spanning tree in the underlying undirected graph remains NP-complete. In this paper we formulate some natural optimization questions around these problems and initiate its study in the realm of parameterized complexity. More precisely, the problems we study are the following: Arc- Disjoint Branchings and Non- Disconnecting Out- Branching. In Arc- Disjoint Branchings ( Non- Disconnecting Out- Branching), a digraph D and a positive integer k are given as input and the goal is to test whether there exist an out-branching and in-branching (respectively, a spanning tree in the underlying undirected graph) that differ on at least k arcs. We obtain the following results for these problems. The algorithm for Non- Disconnecting Out- Branching runs in time $$2^{\mathcal {O}(k)}n^{\mathcal {O}(1)}$$ and the approach we use to obtain this algorithms seems useful in designing other moderately exponential time algorithms for edge/arc partitioning problems. [ABSTRACT FROM AUTHOR]

It is known that the problem of deleting at most κ vertices to obtain a proper interval graph (Proper Interval Vertex Deletion) is fixed parameter tractable. However, whether the problem admits a polynomial kernel or not was open. Here, we answer this question in the affirmative by obtaining a polynomial kernel for Proper Interval Vertex Deletion. This resolves an open question of van Bevern et al. [Graph-Theoretic Concepts in Computer Science (WG 2010), Lecture Notes in Comput. Sci. 6410, Springer, Berlin, 2010, pp. 232-243]. [ABSTRACT FROM AUTHOR]

We give substantially improved exact exponential-time algorithms for a number of NP-hard problems. These algorithms are obtained using a variety of techniques. These techniques include: obtaining exact algorithms by enumerating maximal independent sets in a graph, obtaining exact algorithms from parameterized algorithms and a variant of the usual branch-and-bound technique which we call the "colored" branch-and-bound technique. These techniques are simple in that they avoid detailed case analyses and yield algorithms that can be easily implemented. We show the power of these techniques by applying them to several NP-hard problems and obtaining new improved upper bounds on the running time. The specific problems that we tackle are: (1) the Odd Cycle Transversal problem in general undirected graphs, (2) the Feedback Vertex Set problem in directed graphs of maximum degree 4, (3) Feedback Arc Set problem in tournaments, (4) the 4-Hitting Set problem and (5) the Minimum Maximal Matching and the Edge Dominating Set problems. The algorithms that we present for these problems are the best known and are a substantial improvement over previous best results. For example, for the Minimum Maximal Matching we give an O*(1.4425n) algorithm improving the previous best result of O*(1.4422m) [35]. For the Odd Cycle Transversal problem, we give an O*(1.62n) algorithm which improves the previous time bound of O*(1.7724n) [3]. [ABSTRACT FROM AUTHOR]

Abstract: The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions. We also address the parametric dual problems which are also natural optimization problems. We show that they are fixed parameter tractable not just in tournaments but in oriented directed graphs (where there is at most one directed arc between a pair of vertices). More specifically, the dual problem we show fixed parameter tractable are: Given an oriented directed graph, is there a subset of k vertices (arcs) that forms an acyclic directed subgraph of the graph? Our main results include: [ ] an 1 [1] is the exponent of the best matrix multiplication algorithm. algorithm for weighted feedback vertex set problem, and an algorithm for weighted feedback arc set problem in tournaments; [ ] an algorithm for the dual of feedback vertex set problem (maximum vertex induced acyclic graph) in oriented directed graphs, and an algorithm for the dual of feedback arc set problem (maximum arc induced acyclic graph) in general directed graphs. We also show that the dual of feedback vertex set is —hard in general directed graphs and the feedback arc set problem is fixed parameter tractable in dense directed graphs. Our results are the first non-trivial results for these problems. [Copyright &y& Elsevier]

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset S ⊆ V (G) of size at most k such that G - S is a forest. After a long line of improvement, recently, Li and Nederlof [TALG, 2022] designed a randomized algorithm for the problem running in time O ⋆ (2. 7 k) ∗ . In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in G - S has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers k , ℓ ∈ N , and the objective is to test whether there exists a vertex subset S of size at most k, such that G - S is ℓ edges away from a forest. In this paper, using the methodology of Li and Nederlof [TALG, 2022], we obtain the current fastest algorithms for all these problems. In particular we obtain the following randomized algorithms. Independent Feedback Vertex Set can be solved in time O ⋆ (2. 7 k) . Pseudo Forest Deletion can be solved in time O ⋆ (2. 85 k) . Almost Forest Deletion can be solved in time O ⋆ (min { 2. 85 k · 8. 54 ℓ , 2. 7 k · 36. 61 ℓ , 3 k · 1. 78 ℓ }) . [ABSTRACT FROM AUTHOR]

We study a set of voting problems where given an election E = (C , Π V) (where C is the set of candidates and Π V is a set of votes), and a non-empty subset of candidates J , the question under consideration is: Can we modify the election in a way so that none of the candidates in J wins the election? The modification operations allowed are that of either adding or deleting some candidates. Yang and Wang (2017) [44] introduced these problems as the Resolute Control problem , a generalization of the destructive control problem where J is a singleton. They studied parameterized complexity of Resolute Control for voting rules Borda (both addition and deletion), Maximin (addition), and Copeland (both addition and deletion). They primarily consider | J | as parameter. In this paper we study Resolute Control parameterized by the other natural parameters viz., the number of candidates added or deleted. We show that the Resolute Control for Borda (both addition and deletion), Maximin (addition) and Copeland (deletion) are W[2]-hard. We complement this by showing that when the number of voters is odd, Copeland (deletion) is FPT parameterized by the sum of the number of deleted candidates and the size of the feedback arc set of the majority graph of the election. [ABSTRACT FROM AUTHOR]

The ArtGallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of ArtGallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of ArtGallery are all W[1]-hard with respect to k [Bonnet and Miltzow in 24th Annual European Symposium on Algorithms (Aarhus 2016)], the classic variant has an O (log k) -approximation algorithm [Bonnet and Miltzow in 33rd International Symposium on Computational Geometry (Brisbane 2017)], and it may require irrational guards [Abrahamsen et al. in 33rd International Symposium on Computational Geometry (Brisbane 2017)]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ R -complete [Abrahamsen et al. in 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018)]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)]: Is ArtGallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of ArtGallery, this case can also be viewed as the classic DominatingSet problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-VertexArtGallery is solvable in time r O (r 2) · n O (1) . Furthermore, our approach extends to assert that Vertex-BoundaryArtGallery and Boundary-VertexArtGallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-VertexArtGallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions. [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid M , a weight function ω : E (M) → N , and integers k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of k bases B 1 , ⋯ , B k of M such that the weight of the symmetric difference of any pair of these bases is at least d . The input to the Weighted Diverse Common Independent Sets problem consists of two matroids M 1 , M 2 defined on the same ground set E , a weight function ω : E → N , and integers k ≥ 1 , d ≥ 1 . The task is to decide if there is a collection of k common independent sets I 1 , ⋯ , I k of M 1 and M 2 such that the weight of the symmetric difference of any pair of these sets is at least d . The input to the Diverse Perfect Matchings problem consists of a graph G and integers k ≥ 1 , d ≥ 1 . The task is to decide if G contains k perfect matchings M 1 , ⋯ , M k such that the symmetric difference of any two of these matchings is at least d . We show that none of these problems can be solved in polynomial time unless P = NP . We derive fixed-parameter tractable ( FPT ) algorithms for all three problems with (k , d) as the parameter, and present a p o l y (k , d) -sized kernel for Weighted Diverse Bases. [ABSTRACT FROM AUTHOR]

Balanced Stable Marriage (BSM) is a central optimization version of the classic Stable Marriage (SM) problem. We study BSM from the viewpoint of Parameterized Complexity. Informally, the input of BSM consists of n men, n women, and an integer k. Each person a has a (sub)set of acceptable partners, A (a) , whom a ranks strictly; we use p a (b) to denote the position of b ∈ A (a) in a 's preference list. The objective is to decide whether there exists a stable matching μ such that balance (μ) ≜ max ⁡ { ∑ (m , w) ∈ μ p m (w) , ∑ (m , w) ∈ μ p w (m) } ≤ k. In SM , all stable matchings match the same set of agents, A ⋆ which can be computed in polynomial time. As balance (μ) ≥ | A ⋆ | 2 for any stable matching μ , BSM is trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whether BSM is FPT with respect to k − | A ⋆ | 2. With this viewpoint in mind, we draw a line between tractability and intractability in relation to the target value. This line separates additional natural parameterizations higher/lower than ours (e.g., we automatically resolve the parameterization k − | A ⋆ | 2). The two extreme stable matchings are the man-optimal μ M and the woman-optimal μ W. Let O M = ∑ (m , w) ∈ μ M p m (w) , and O W = ∑ (m , w) ∈ μ W p w (m). In this work, we prove that • BSM parameterized by t = k − min ⁡ { O M , O W } admits (1) a kernel where the number of people is linear in t , and (2) a parameterized algorithm whose running time is single exponential in t. • BSM parameterized by t = k − max ⁡ { O M , O W } is W[1]-hard. [ABSTRACT FROM AUTHOR]

We develop new approximation algorithms for classical graph and set problems in the RAM model under space constraints. As one of our main results, we devise an algorithm for d - H I T T I N G S E T that runs in time n O (d 2 + (d / ϵ)) , uses O ((d 2 + (d / ϵ)) log n) bits of space, and achieves an approximation ratio of O ((d / ϵ) n ϵ) for any positive ϵ ≤ 1 and any d ∈ N . In particular, this yields a factor- O (log n) approximation algorithm which runs in time n O (log n) and uses O (log 2 n) bits of space (for constant d). As a corollary, we obtain similar bounds for V E R T E X C O V E R and several graph deletion problems. For bounded-multiplicity problem instances, one can do better. We devise a factor-2 approximation algorithm for V E R T E X C O V E R on graphs with maximum degree Δ , and an algorithm for computing maximal independent sets, both of which run in time n O (Δ) and use O (Δ log n) bits of space. For the more general d - H I T T I N G S E T problem, we devise a factor-d approximation algorithm which runs in time n O (d δ 2) and uses O (d δ 2 log n) bits of space on set families where each element appears in at most δ sets. For I N D E P E N D E N T S E T restricted to graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses O (log n) bits of space. We also devise a factor- O (d 2) approximation algorithm for D O M I N A T I N G S E T on d-degenerate graphs which runs in time n O (log n) and uses O (log 2 n) bits of space. For d-regular graphs, we show how a known randomized factor- O (log d) approximation algorithm can be derandomized to run in time n O (1) and use O (log n) bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms. [ABSTRACT FROM AUTHOR]

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighborhood of some vertex. The minimum number of colors required for any cd-coloring of G , denoted by χ c d (G) , is called the class domination chromatic number (cd-chromatic number) of G. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph G on n vertices, find its cd-chromatic number. (2) Given a graph G and integers k and q , can we delete at most k vertices such that the cd-chromatic number of the resulting graph is at most q ? For the first problem, we give an exact algorithm with running time O (2 n n 4 log n). Also, we show that the problem is FPT with respect to the number q of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with O (q 3) vertices. For the second (deletion) problem, we show NP -hardness for each q ≥ 2. Further, on split graphs, we show that the problem is NP -hard if q is a part of the input and FPT with respect to k and q as combined parameters. As recognizing graphs with cd-chromatic number at most q is NP -hard in general for q ≥ 4 , the deletion problem is unlikely to be FPT when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for q ∈ { 2 , 3 } using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines. • An exact algorithm that runs in time O (2 n n 4 log n). • An FPT algorithm parameterized by the number of colors and the treewidth. • FPT algorithms when input graph is restricted to special graph classes. • 3 - cd-Coloring is FPT parameterized by the solution size. [ABSTRACT FROM AUTHOR]

We know that Tree Contraction does not admit a polynomial kernel unless NP ⊆ coNP/poly , while Path Contraction admits a kernel with O (k) vertices. The starting point of this article is the following natural questions: What is the structure of the family of paths that allows Path Contraction to admit a polynomial kernel? Apart from the size of the solution, what other additional parameters should we consider so we can design polynomial kernels for these basic contraction problems? To design polynomial kernels, we consider the family of trees with the bounded number of leaves (note that the family of paths are trees with at most two leaves). In particular, we study Bounded Tree Contraction. Here, an input is a graph G , integers k and ℓ , and the goal is to decide whether, there is a subset F ⊆ E (G) of size at most k such that G / F is a tree with at most ℓ leaves. We design a kernel with O (k ℓ) vertices and O (k 2 + k ℓ) edges for this problem. We complement this result by giving kernelization lower bound. We also prove similar results for Bounded Out-Tree Contraction and Bounded Cactus Contraction. [ABSTRACT FROM AUTHOR]

Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. https://doi.org/10.1145/3265027) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). Here, we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (Sim-FES). In this problem, the input is an n-vertex graph G, a positive integer k, and a coloring function col: E (G) → 2 [ α ] , and the objective is to check whether there is an edge subset S of cardinality k in G such that for each i ∈ [ α ] , G i - S is acyclic. Unlike the vertex variant of the problem, when α = 1 , the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for α = 3 , Sim-FES is NP-hard, and does not admit an algorithm of running time 2 o (k) n O (1) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time 2 ω k α + α log k n O (1) where ω is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when α = 2 . We also give a kernel for Sim-FES with (k α) O (α) vertices. Finally, we consider a "dual" version of the problem called Maximum Simultaneous Acyclic Subgraph and give an FPT algorithm with running time 2 ω q α n O (1) , where q is the number of edges in the output subgraph. [ABSTRACT FROM AUTHOR]

In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that O (f (k) log O (1) n) space is enough, where f is an arbitrary computable function depending only on the parameter k. However, in the past few years very few positive results have been established. Most of the graph problems that do have streaming algorithms of the above nature are ones where localized checking is required, like Vertex Cover or Maximum Matching parameterized by the size k of the solution we are seeking. Chitnis et al. (SODA'16) have shown that many important parameterized problems that form the backbone of traditional parameterized complexity are known to require Ω (n) bits of storage for any streaming algorithm; e.g. Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal, Triangle Deletion or the more general F -Subgraph Deletion when parameterized by solution size k. Our contribution lies in overcoming the obstacles to efficient parameterized streaming algorithms in graph deletion problems by utilizing the power of parameterization. We focus on the vertex cover size K as the parameter for the parameterized graph deletion problems we consider. In this work, we consider the four most well-studied streaming models: the Ea, Dea, Va (vertex arrival) and Al (adjacency list) models. Surprisingly, the consideration of vertex cover size K in the different models leads to a classification of positive and negative results for problems like F -Subgraph Deletion and F -Minor Deletion. [ABSTRACT FROM AUTHOR]

We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour , the task is to decide whether a graph has an (s , t) -path of length at least dist G (s , t) + k. Bezáková et al. [7] proved that on undirected graphs the problem is fixed-parameter tractable (FPT). Our first main result establishes a connection between Longest Detour on directed graphs and 3- Disjoint Paths on directed graphs. Using these new insights, we design a 2 O (k) ⋅ n O (1) time algorithm for the problem on directed planar graphs. Furthermore, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path , namely Longest Path above Diameter , the task is to decide whether the graph has a path of length at least diam (G) + k. We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [ABSTRACT FROM AUTHOR]

Bidimensionality theory was introduced by [E. D. Demaine et al., J. ACM, 52 (2005), pp. 866--893] as a tool to obtain subexponential time parameterized algorithms on H-minor-free graphs. In [E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, 2005, pp. 590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (resp., contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO) admits a linear kernel for classes of graphs that exclude a fixed graph (resp., an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems admit linear kernels on the corresponding graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work. [ABSTRACT FROM AUTHOR]

We study the question of finding a set of at most k edges, whose removal makes the input n -vertex graph a disjoint union of s -clubs (graphs of diameter s). Komusiewicz and Uhlmann [DAM 2012] showed that Cluster Edge Deletion (i.e., for the case of 1-clubs (cliques)), cannot be solved in time 2 o (k) n O (1) unless the Exponential Time Hypothesis (ETH) fails. But, Fomin et al. [JCSS 2014] showed that if the number of cliques in the output graph is restricted to d , then the problem (d -Cluster Edge Deletion) can be solved in time O (2 O (d k) + m + n). We show that assuming ETH, there is no algorithm solving 2 -Club Cluster Edge Deletion in time 2 o (k) n O (1). Further, we show that the same lower bound holds in the case of s -Club d -Cluster Edge Deletion for any s ≥ 2 and d ≥ 2. [ABSTRACT FROM AUTHOR]

The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundamental combinatorial problem and has received extensive attention in various subdomains of algorithmics. In the area of kernelization, it is known that this problem is unlikely to have a polynomial kernelization algorithm. However, it has been shown in a recent work of Lokshtanov et al. (Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC 2017, Montreal, QC, Canada, 2017) that if one considered an appropriate notion of approximate kernelization, then this problem parameterized by the solution size does admit an approximate polynomial kernelization. In fact, Lokshtanov et al. were able to obtain a polynomial size approximate kernelization scheme (PSAKS) for Connected Vertex Cover parameterized by the solution size. A PSAKS is essentially a preprocessing algorithm whose error can be made arbitrarily close to 0. In this paper we revisit this problem, and consider parameters that are strictly smaller than the size of the solution and obtain the first polynomial size approximate kernelization schemes for the Connected Vertex Cover problem when parameterized by the deletion distance of the input graph to the class of cographs, the class of bounded treewidth graphs, and the class of all chordal graphs. [ABSTRACT FROM AUTHOR]

Given an undirected graph, its arboricity is the minimum number of edge disjoint forests that its edge set can be partitioned into. We develop the first fully dynamic algorithms to determine the arboricity of a graph under edge insertions and deletions. While our insertion algorithm is based on known static algorithms to determine the arboricity, our deletion algorithm is, to the best of our knowledge, new. Our algorithms take O (m log ⁡ n) time to insert or delete an edge where m is the number of edges in the graph while the best static algorithm to compute arboricity takes O (m 3 / 2 log ⁡ (n 2 / m)) time [9]. We complement our upper bound with a lower bound of amortized Ω (log ⁡ n) time for an update for an algorithm that maintains a forest decomposition of size arboricity of the graph under edge insertions and deletions. [ABSTRACT FROM AUTHOR]

In this paper, we study the NP-complete colorful variant of the classic matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, the goal is to decide whether there exists a matching of size at least k such that the edges in the matching have distinct colors. Previously, in [MFCS'17], we studied this problem from the view point of Parameterized Complexity and gave efficient FPT algorithms as well as a quadratic kernel on paths. In this paper we design a quadratic vertex kernel for Rainbow Matching on general graphs; generalizing the earlier quadratic kernel on paths to general graphs. For our kernelization algorithm we combine a graph decomposition method with an application of expansion lemma. [ABSTRACT FROM AUTHOR]

Given a network modeled by a directed graph D = (V , A) , it is natural to ask whether we can partition the vertex set of D into two disjoint subsets V 1 , V 2 (called a 2-partition), such that the digraphs D [ V 1 ] , D [ V 2 ] induced by each of these has one of the two properties of interest. This question gives rise to a rich realm of combinatorial problems. The complexity of many such problems was determined in [2,3]. We analyze a subset of those problems from the viewpoint of parameterized complexity, and present a complete dichotomy of basic, natural properties. More precisely, given a directed graph D = (V , A) and two non-negative integers k 1 and k 2 , we seek a 2-partition (V 1 , V 2) of the vertex set V such that | V 1 | ≥ k 1 , | V 2 | ≥ k 2 , and each of the subdigraphs induced by V 1 and V 2 has a structural property as defined by the problem at hand—for example, D [ V 1 ] is acyclic and D [ V 2 ] is strongly connected. Specifically, we consider the following eight structural properties: being strongly connected; being connected; having an out-branching; having an in-branching; having minimum degree at least one; having minimum semi-degree at least one; being acyclic; and being complete. [ABSTRACT FROM AUTHOR]

In the Cycle Packing problem, we are given an undirected graph G, a positive integer r, and the task is to check whether there exist r vertex-disjoint cycles. In this paper, we study Cycle Packing with respect to a structural parameter, namely, distance to proper interval graphs (indifference graphs). In particular, we show that Cycle Packing is fixed-parameter tractable (FPT) when parameterized by t, the size of a proper interval deletion set. For this purpose, we design an algorithm with O (2 O (t log t) n O (1)) running time. Bodlaender et al. (Theor Comput Sci 511:117–136, 2013) studied several structural parameterizations for Cycle Packing and our FPT algorithm fills a gap in their ecology of parameterizations. We combine color coding, greedy strategy and dynamic programming based on structural properties of proper interval graphs in a non-trivial fashion to obtain the FPT algorithm. Our belief is that this approach is quite general and can be useful in solving many other problems with the same parameterization. [ABSTRACT FROM AUTHOR]

In the Subset Feedback Vertex Set (Subset-FVS) problem the input is a graph G on n vertices, a subset T of vertices of G called the "terminal" vertices, and an integer k. The task is to determine whether there exists a subset of vertices of cardinality at most k which together intersect all cycles which pass through the terminals. Subset-FVS generalizes several well studied problems including Feedback Vertex Set and Multiway Cut. This problem is known to be NP-Complete, even in split graphs. Cygan et al. (SIAM J Discrete Math 27(1):290–309, 2013) proved that Subset-FVS is fixed parameter tractable (FPT ) in general graphs when parameterized by k. In split graphs a simple observation reduces the problem to an equivalent instance of the 3-Hitting Set problem with the same solution size. This directly implies, for Subset-FVSrestricted to split graphs, (i) an FPT algorithm which solves the problem in O ⋆ (2. 076 k) time (The O ⋆ () notation hides polynomial factors.) (Wahlström in Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. Thesis, Department of Computer and Information Science, Linköpings universitet, 2007), and (ii) a kernel of size O (k 3) . We improve both these results for Subset-FVS on split graphs; we derive (i) a kernel of size O (k 2) which is the best possible unless NP ⊆ coNP / poly , and (ii) an algorithm which solves the problem in time O ∗ (2 k) . Our algorithm, in fact, solves Subset-FVS on the more general class of chordal graphs, also in O ∗ (2 k) time. To the best of our knowledge, the fastest known exact algorithm for Subset-FVS on chordal graphs is based on the 3-Hitting Set algorithm of Fomin et al. (JACM 66(2):8, 2019) which runs in O ∗ (1. 5182 n) time. Applying the results of Fomin et al. (2019) to our FPT algorithm yields two exact exponential-time algorithms for Subset-FVS on chordal graphs: a randomized algorithm which runs in O ∗ (1. 5 n) time, and a deterministic algorithm which runs in O ∗ ((1.5 + ε) n) time for any fixed ε > 0 . [ABSTRACT FROM AUTHOR]

For a positive integer c, a graph G is said to be c-closed if every pair of nonadjacent vertices in G have at most c 1 neighbors in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is c-closed. The class of c-closed graphs was introduced by J. Fox, T. Roughgarden, C. Seshadhri, F. Wei, and N. Wein [Proceedings of the International Colloquium on Automata, Languages, and Programming (2018), 55; SIAM J. Comput., 49 (2020), pp. 448--464]. T. Koana, C. Komusiewicz, and F. Sommer [Proceedings of the European Symposium on Algorithms (2020), 65; SIAM J. Discrete Math., 36 (2022), pp. 2798--2821] started the study of using cl(G) as an additional structural parameter to design kernels for problems that are W-hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set, and (Threshold) Dominating Set and showed that each of these problems admits a polynomial kernel when parameterized either by k + c or by k for each fixed value of c. Here, k is the solution size and c = cl(G). The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable (FPT) algorithm and a polynomial kernel on c-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable when parameterized by k + cl(G), whereas Partial Dominating Set, parameterized by k, is W[1]-hard even when cl(G) = 2. We also show that for each fixed c, Perfect Code admits a polynomial kernel on the class of c-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs unless NP\subseteq co-NP/poly. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editors discuss various reports within the issue on topics including Nash equilibrium, chromatic polynomial, and fixed-parameter evolutionary algorithms.

An introduction is presented in which the editors discuss various reports within the issue on topics including the algorithmic applications of bounded treewidth graph, the fast minor testing for planar graphs and the multivariate complexity of swap bribery.

The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a long-standing, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and Wahlstrom on representative sets finally answered this question in the affirmative [FOCS 2012]. In this paper, we present an alternative, algebraic compression of the Vertex Cover Above LP problem into the Rank Vertex Cover problem. Here, the input consists of a graph G, a parameter k, and a bijection between V (G) and the set of columns of a representation of a matroid M, and the objective is to find a vertex cover whose rank is upper bounded by k. [ABSTRACT FROM AUTHOR]

The Cycle Packing problem asks whether a given undirected graph G = (V;E) con- tains k vertex-disjoint cycles. Since the publication of the classic Erd}os{Posa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particu- lar, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of Cycle Packing follows from the Robertson{Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2O(k2) jV j using exponential space. In the case a solu- tion exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2O(k log2 k) jV j-time (deterministic) algorithm using exponential space, which is a consequence of the Erd}os{Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time 2o(k log2 k) jV jO(1), beating the bound 2O(k log2 k) jV jO(1), has been found. In light of this, it seems natural to ask whether the 2O(k log2 k) jV jO(1) bound is essentially optimal. In this paper, we answer this question negatively by developing a 2 O(k log2 k log log k) jV j-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound 2O(k log2 k) jV jO(1), our algorithm runs in time linear in jV j, and its space complexity is polynomial in the input size. [ABSTRACT FROM AUTHOR]

In this paper, we study the NP-complete colorful variant of the classical Matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, this problem asks whether there exists a matching of size at least k such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves Rainbow Matching on paths in time O ⋆ 1 + 5 2 k and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a "divide-and-conquer-like" approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures "divided-and-conquered" pieces of the path. Our second result is a randomized algorithm that solves Rainbow Matching on general graphs in time O ⋆ (2 k) and polynomial-space. Here, we show how a result by Björklund et al. (J Comput Syst Sci 87:119–139, 2017) can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for Rainbow Matching on general and bounded-degree graphs. [ABSTRACT FROM AUTHOR]

VERTEX COVER is one of the most well studied problems in the realm of parameterized algorithms. It admits a kernel with O(ℓ2) edges and 2ℓ vertices where ℓ denotes the size of the vertex cover we are seeking for. A natural question is whether VERTEX COVER is fixed-parameter tractable or admits a polynomial kernel with respect to a parameter k, that is, provably smaller than the size of the vertex cover. Jansen and Bodlaender [STACS 2011, TOCS 2013] raised this question and gave a kernel for VERTEX COVER of size O(f3), where f is the size of a feedback vertex set of the input graph. We continue this line of work and study VERTEX COVER with respect to a parameter that is always smaller than the solution size and incomparable to the size of the feedback vertex set of the input graph. Our parameter is the number of vertices whose removal results in a graph of maximum degree two. While vertex cover with this parameterization can easily be shown to be fixed-parameter tractable (FPT), we show that it has a polynomial kernel. The input to our problem consists of an undirected graph G, S⊆V(G) such that |S|=k and G[V(G)∖S] has maximum degree at most two and a positive integer ℓ. Given (G,S,ℓ), in polynomial time we output an instance (G′,S′,ℓ′) such that |V(G′)| is O(k5), |E(G′)| is O(k6) and G has a vertex cover of size at most ℓ if and only if G′ has a vertex cover of size at most ℓ′. When G[V(G)∖S] has maximum degree at most one, we improve the known kernel bound from O(k3) vertices to O(k2) vertices (and O(k3) edges). More generally, given (G,S,ℓ) where every connected component of G∖S is a clique of at most d vertices (for constant d), in polynomial time, we output an equivalent instance (G′,S′,ℓ′) for the same problem where |V(G′)| is O(kd). We also show that for this problem, when d≥3, a kernel with O(kd−ε) bits cannot exist for any ε>0 unless NP⊆coNP/poly. [ABSTRACT FROM AUTHOR]

A vertex subset S in a graph G is a dominating set if every vertex not contained in S has a neighbor in S. A dominating set S is a connected dominating set if the subgraph G[S] induced by S is connected. A connected dominating set S is a minimal connected dominating set if no proper subset of S is also a connected dominating set. We prove that there exists a constant \epsilon ∊10-50 such that every graph G on n vertices has at most O(2(1-∊)n) minimal connected dominating sets. For the same ∊ we also give an algorithm with running time 2(1-∊)n· nO(1) to enumerate all minimal connected dominating sets in an input graph G. [ABSTRACT FROM AUTHOR]

A central problem in parameterized algorithms is to obtain algorithms with running time f(k) · nO(1) such that f is as slow growing a function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f(k) is single-exponential, that is, ck for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the f(k) appearing in the best-known running time is worse than single-exponential and it remained "slightly superexponential" even after serious attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is kO(k) = 2O(k log k) in the best-known running time, and for a number of such problems we show that the dependence on k in the running time cannot be improved to single-exponential. More precisely we prove the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the Closest String problem, given strings s1, ..., st over an alphabet Σ of length L each, and an integer d, the question is whether there exists a string s over Σ of length L, such that its hamming distance from each of the strings si, 1 ≤ i ≤ t, is at most d. The pattern matching problem Closest String is known to be solvable in times 2O(d log d) · nO(1) and 2O(d log |Σ|) · nO(1). We show that there are no 2o(d log d) · nO(1) or 2o(d log |Σ|) · nO(1) time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem Distortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be solved in time 2O(d log d) · nO(1). We show that there is no 2o(d log d) · nO(1) time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time 2O(w log w) · nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time 2O(w log w) ·nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. To obtain our results, we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. Several follow-up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future. [ABSTRACT FROM AUTHOR]