In the d-Euclidean Distance Matrix Completion (d-EDMC) problem, one aims to determine whether a given partial matrix of pairwise distances can be extended to a full Euclidean distance matrix in d dimensions. This problem is a cornerstone of computational geometry with numerous applications. While classical work on this problem often focuses on exploiting connections to semidefinite programming typically leading to approximation algorithms, we focus on exact algorithms and propose a novel distance-from-triviality parameterization framework to obtain tractability results for d-EDMC. We identify key structural patterns in the input that capture entry density, including chordal substructures and coverability of specified entries by fully specified principal submatrices. We obtain: 1) The first fixed-parameter algorithm (FPT algorithm) for d-EDMC parameterized by d and the maximum number of unspecified entries per row/column. This is achieved through a novel compression algorithm that reduces a given instance to a submatrix on 𝒪(1) rows (for fixed values of the parameters). 2) The first FPT algorithm for d-EDMC parameterized by d and the minimum number of fully specified principal submatrices whose entries cover all specified entries of the given matrix. This result is also achieved through a compression algorithm. 3) A polynomial-time algorithm for d-EDMC when both d and the minimum fill-in of a natural graph representing the specified entries are fixed constants. This result is achieved by combining tools from distance geometry and algorithms from real algebraic geometry. Our work identifies interesting parallels between EDM completion and graph problems, with our algorithms exploiting techniques from both domains.

Ma and Wong [IEEE TCAD '12] introduced and studied the Rectangle Escape problem, motivated by bus escape routing in printed circuit board design. In this problem, we are given an axis-parallel rectangle R, a set 𝒮 of axis-parallel rectangles fully contained in R, and an integer d. The goal is to determine whether each rectangle in 𝒮 can be extended in one of the four axis-parallel directions (up, down, left, or right) to the boundary of R such that no point is covered by more than d extended rectangles. We revisit Rectangle Escape and resolve several open complexity questions. Ahmadinejad et al. [TCS '17] studied Rectangle Escape and its variants where rectangles are only allowed to be extended in a subset of directions - most notably, in two directions, a variant they termed Bidirectional REP. They showed that the problem is NP-complete when extensions are limited to two adjacent directions and d = 3, but left open the complexity of the case when d = 2. Additionally, the case for two opposite directions remained unresolved for any d ≥ 2. We resolve the first question by showing that Bidirectional REP is NP-complete even when extensions are restricted to two adjacent directions and d = 2. We also settle the complexity of Rectangle Escape with two opposite directions by proving that the problem is NP-complete when d is part of the input but solvable in 𝒪(n log n) time for any constant d. Finally, we consider the special case where all extended rectangles must be disjoint, that is, d = 1. We show an unconditional lower bound of Ω(n log n) with a matching upper bound of 𝒪(n log n) for all variants. This improves upon a sequence of algorithms for the setting with all four directions allowed and d = 1, starting with an 𝒪(n⁶)-time algorithm, later improved to 𝒪(n⁴), and then to O(n³).

Geometric covering problems typically ask for a small family of geometric objects whose union contains all input points. In this paper we study a more rigid variant, boundary covering, where every point must lie on the boundary of at least one chosen object. Motivated by the framework of Langerman and Morin [Discret. Comput. Geom., 2005] for boundary covering by hyperspheres, we initiate a systematic study of boundary covering by axis-parallel rectangles in the plane. We first consider the discrete setting, where the rectangles must be chosen from a given family. We define Boundary Covering with Discrete Axis-Parallel Rectangles (BCDAPR) as follows: given a point set P ⊆ ℝ², a collection ℛ of axis-parallel rectangles, and an integer k, decide whether P can be covered by the boundaries of at most k rectangles from ℛ. We prove that this discrete boundary-covering problem is W[1]-hard when parameterized by k. This motivates the continuous variant, where we are allowed to place rectangles freely. We define Boundary Covering with Continuous Axis-Parallel Rectangles (BCCAPR) as follows: given a point set P ⊆ ℝ² and an integer k, decide whether P can be covered by the boundaries of at most k axis-parallel rectangles. In contrast to the discrete case, we show that BCCAPR is fixed-parameter tractable parameterized by k, with running time 2^𝒪(k log k) ⋅ n^𝒪(1), where n = |P|. Our results does a fine-grained structural analysis of how k rectangles can interact with the point set. On the hardness side, we show that moving from lines to slightly richer shapes already incurs intractability: we prove NP-completeness for boundary covering by axis-aligned L-shapes, and then lift it to NP-completeness of BCCAPR. For the algorithm we reduce BCCAPR to at most 2^𝒪(k log k) instances of Distinct Domain Monotone ,$-CSP, each solvable in polynomial time.

We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set (PartialConRBDS). Given a bipartite graph G = (R∪ B,E) with red vertices R and blue vertices B, an auxiliary connectivity graph G_{conn} on R, and integers k,t, the task is to find a set S ⊆ R with |S| ≤ k such that G_{conn}[S] is connected and S dominates at least t blue vertices. This formulation captures connected variants of Maximum Coverage [Hochbaum-Rao, Inf. Proc. Lett., 2020; D'Angelo-Delfaraz, AAMAS 2025], Partial Vertex Cover, and Partial Dominating Set [Khuller et al., SODA 2014; Lamprou et al., TCS 2021] via standard encodings. Limits to parameterized tractability. PartialConRBDS is W[1]-hard parameterized by k even under strong restrictions: it remains hard when G_{conn} is a clique or a star and the incidence graph G is 3-degenerate, or when G is K_{2,2}-free. Inapproximability. For every ε > 0, there is no polynomial-time (1, 1-1/e+ε)-approximation unless 𝖯 = NP. Moreover, under ETH, no algorithm running in f(k)⋅ n^{o(k)} time achieves an g(k)-approximation for k for any computable function g(⋅), or for any ε > 0, a (1-1/e+ε)-approximation for t. Graphical special cases. Partial Connected Dominating Set is W[2]-hard parameterized by k and inherits the same ETH-based f(k)⋅ n^{o(k)} inapproximability bound as above; Partial Connected Vertex Cover is W[1]-hard parameterized by k. These hardness boundaries delineate a natural "sweet spot" for study: within appropriate structural restrictions on the incidence graph, one can still aim for fine-grained (FPT) approximations. Our algorithms. We solve PartialConRBDS exactly by reducing it to Relaxed Directed Steiner Out-Tree in time (2e)^t ⋅ n^{𝒪(1)}. For biclique-free incidences (i.e., when G excludes K_{d,d} as an induced subgraph), we obtain two complementary parameterized schemes: - An Efficient Parameterized Approximation Scheme (EPAS) running in time 2^{𝒪(k² d/ε)}⋅ n^{𝒪(1)} that either returns a connected solution of size at most k covering at least (1-ε)t blue vertices, or correctly reports that no connected size-k solution covers t; and - A Parameterized Approximation Scheme (PAS) running in time 2^{𝒪(kd(k²+log d))}⋅ n^{𝒪(1/ε)} that either returns a connected solution of size at most (1+ε)k covering at least t blue vertices, or correctly reports that no connected size-k solution covers t. Together, these results chart the boundary between hardness and FPT-approximability for connectivity-constrained coverage.

We study Maximum Span, motivated by the recent Maximum Span Hypothesis of Karthik and Khot [SODA 2025], which suggests strong parameterized intractability for finding large structured subsets in vector spaces. Formally, given a matrix M and integers k and t, the task is to decide whether there exists a linearly independent set S of at most k columns such that at least t additional columns of M lie in span(S). Equivalently, the goal is to identify a low-rank witness whose span covers many input columns. We initiate a systematic study of the parameterized complexity of Maximum Span on natural matroid classes, revealing a diverse complexity landscape. We first show that the problem is polynomial-time solvable on laminar matroids, via a dynamic program over the laminar tree. In sharp contrast, on graphic matroids the problem is W[1]-hard parameterized by k+t, and, assuming Gap-ETH, admits no f(k)⋅ n^𝒪(1)-time k^o(1)-approximation. On cographic matroids, we show that the problem is equivalent to deleting at most k+t edges so as to create at least t+1 connected components; this yields fixed-parameter tractability parameterized by k+t, and W[1]-hardness parameterized by t. On transversal matroids, using a Hall-type interpretation, we prove W[1]-hardness parameterized by k+t. For strict gammoids, we develop a separator-based formulation. We prove W[1]-hardness parameterized by k+t, give an XP algorithm parameterized by t, and obtain FPT 2^k-approximation algorithms in both the directed and undirected settings. For general gammoids, we establish W[1]-hardness parameterized by k+t, NP-hardness already for t = 1, and an XP algorithm parameterized by k. Together, these results give a detailed parameterized complexity map for Maximum Span across fundamental matroid classes, ranging from polynomial-time solvability to fixed-parameter algorithms, XP algorithms, approximation algorithms, and strong hardness.

We study bi-criteria approximation algorithms for vertex deletion problems in the (k,W) setting, where both the solution size and total weight are bounded simultaneously. Given a graph G, a weight function w:V → ℚ^+, a size bound k, and a weight budget W, a bi-criteria (a,b)-approximation algorithm either certifies that no solution of size at most k and weight at most W exists, or returns a solution of size at most ak and weight at most bW. Parameterizing by the solution size k - rather than the weight budget W - allows our algorithms to handle arbitrary positive rational weights without any lower bound assumption, addressing a fundamental limitation of prior W-parameterized approaches. We obtain two families of results. For general vertex deletion problems Π-Deletion admitting a polynomial-time weighted α-approximation, we obtain a polynomial-time (α(λ+1),α(1+1/(λ)))-approximation for any λ > 0, a randomized FPT improvement for problems admitting a sampling step, and a deterministic FPT version for problems with bounded obstruction size. For (k,W)-d-Hitting Set, which captures vertex deletion problems with obstruction size at most d, we design a polynomial-time (d,d)-approximation, a parameterized family of ((1-ε)d, d)-approximations improving the size factor below d, and two algorithms that simultaneously push both factors below d: a ((d+1)/2,(d+1)/2)-approximation and a more refined (d-γ,d-γ)-approximation for any γ ∈ (0,(d-1)/2). All algorithms work with arbitrary positive rational weights and are parameterized by the solution size k. To demonstrate the broad applicability of our framework, we instantiate our results on six well-studied vertex deletion problems: Cluster Vertex Deletion, FVS in Tournaments, Split Vertex Deletion, Feedback Vertex Set, d-Path Vertex Cover, and Pathwidth-One Vertex Deletion. In fact, our general results apply to any vertex deletion problem admitting a polynomial-time weighted approximation algorithm, and the six problems serve as representative examples spanning a range of obstruction structures - from bounded-size obstructions to unbounded ones. For (k,W) setting of Feedback Vertex Set and Pathwidth-One Vertex Deletion, we establish new sampling steps enabling the FPT approximation results. For Pathwidth-One Vertex Deletion, we additionally prove a polynomial-time 3-approximation for the weighted version on general graphs.

The starting point of our work is the decade-old open question concerning the subexponential parameterized complexity of the 2-Layer Crossing Minimization problem. In this problem, the input is an \(n\)-vertex graph \(G\) whose vertices are divided into two independent sets \(V_1, V_2\), and a non-negative integer \(k\). The question is whether \(G\) supports a 2-layered drawing with at most \(k\) crossings. Here, a 2-layered drawing refers to a drawing of \(G\) where each set \(V_i\) for \(i \in \{1,2\}\) is placed on a distinct straight line parallel to the \(x\)-axis, and all edges are drawn as straight lines connecting vertices. Our first theorem resolves the aforementioned question in the affirmative by providing a fixed-parameter tractable (FPT) subexponential algorithm with running time \(2^{\mathcal O(\sqrt{k}\log k)} + n \cdot k^{\mathcal O(1)}\).

In the last decade, FPT approximation has witnessed tremendous growth, with the development of several powerful upper- and lower-bound techniques. Within this framework, a newly emerging direction focuses on problems that admit algorithms with running time of the form ck · nO(1) for some constant c. This line of inquiry naturally leads to the notion of time–approximation ratio trade-offs (or time-ratio trade-offs): by relaxing the approximation guarantee in a controlled manner, one can improve the exponential dependence on the parameter in the running time. The contribution of this paper is threefold: (i) a formal language for parameterized randomized branching algorithms (called Oracle Subset Problems); (ii) a meta-algorithm applicable to all problems expressible in this language; and (iii) new time–ratio trade-offs obtained by instantiating the framework on fundamental problems, including Above-Guarantee Vertex Cover (parameterized by excess over the LP lower bound), Odd Cycle Transversal, Node Multiway Cut, Subset/Group Feedback Vertex Set, Min-Weight d-SAT, and Matroid-Rank d-Hitting Set (where solution is measured by the rank in a matroid accessible via an independence oracle), among others. Our applications demonstrate substantially broader applicability. For the first time, they apply to cut problems, problems with parity constraints (Odd Cycle Transversal), “complex” cycle hitting problems (hitting all cycles whose length mod73 is non-zero), and even a generalization where the user specifies the subset of vertices such that only the cycles passing through that subset of vertices should be hit. These results are obtained by developing time–ratio trade-offs for two meta-algorithms, expressed in our language: (i) the biased-graph framework [Wahlström, SODA 2017; Lee and Wahlström, arXiv 2020], and (ii) the Vertex Cover above LP framework [Lokshtanov et al., TALG 2014].

Courcelle’s theorem states that there exists an algorithm that takes as input a graph G of treewidth at most t and a MSO formula φ, and determines whether G satisfies φ in time f(φ,t) · n. It is folklore that the function f contains a tower of exponentials whose height depends as a linear function of the number of quantifier alternations of the input formula φ. A classic reduction of Frick and Grohe shows that, assuming the Exponential Time Hypothesis (ETH), the linear growth of the height of the tower is unavoidable. Nevertheless, there is still a huge gap between existing upper and lower bounds – after all, there is quite a difference between a single exponential and a double exponential running time. In addition, this only gives us a very coarse understanding in the time complexity of Courcelle’s theorem. In this paper, we prove a fine-grained version of Courcelle’s theorem with nearly ETH-tight dependence on the treewidth parameter t and the quantifier structure of φ (specifically, the number of first order and second order variables in each quantifier alternation block).

Abstract We study the following Independent Stable Set problem. Let $$\varvec{G}$$ G be an undirected graph and $$\varvec{\mathcal {M}} \varvec{=} \varvec{(V(G),} \varvec{\mathcal {I})}$$ M = ( V ( G ) , I ) be a matroid whose elements are the vertices of $$\varvec{G}$$ G . For an integer $$\varvec{k}\varvec{\ge } \varvec{1}$$ k ≥ 1 , the task is to decide whether $$\varvec{G}$$ G contains a set $$\varvec{S}\varvec{\subseteq } \varvec{V(G)}$$ S ⊆ V ( G ) of size at least $$\varvec{k}$$ k which is independent (stable) in $$\varvec{G}$$ G and independent in $$\varvec{\mathcal {M}}$$ M . This problem generalizes several well-studied algorithmic problems, including Rainbow Independent Set , Rainbow Matching , and Bipartite Matching with Separation . We show that when the matroid $$\varvec{\mathcal {M}}$$ M is represented by an independence oracle, then for any computable function $$\varvec{f}$$ f , no algorithm can solve Independent Stable Set using $$\varvec{f(k)} \varvec{\cdot } \varvec{n}^{\varvec{o(k)}}$$ f ( k ) · n o ( k ) calls to the oracle. On the other hand, when the graph $$\varvec{G}$$ G

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Björklund and Husfeldt, ICALP 2014; Mari et al., SODA 2024] or request the paths to be shortest [Lochet, SODA 2021], we consider the following cycle packing problems: Min-Sum Cycle Packing and Shortest Cycle Packing . In Min-Sum Cycle Packing , we try to find, in a weighted undirected graph, \( k \) vertex-disjoint cycles of minimum total weight. Our first main result is an algorithm that, for any fixed \( k \) , solves the problem in polynomial time. We complement this result by establishing the W[1]-hardness of Min-Sum Cycle Packing parameterized by \( k \) . The same results hold for the version of the problem where the task is to find \( k \) edge-disjoint cycles. Our second main result concerns Shortest Cycle Packing , which is a special case of Min-Sum Cycle Packing that asks to find a packing of \( k \) shortest cycles in a graph. We prove this problem to be Fixed-Parameter Tractable (FPT) when parameterized by \( k \) on weighted planar graphs. We also obtain a polynomial kernel for the edge-disjoint variant of the problem on planar graphs. Whether Min-Sum Cycle Packing is FPT on planar graphs, or Shortest Cycle Packing on general graphs, remains open.

Max-SAT with cardinality constraint ( CC-Max-Sat ) is one of the classical NP-complete problems, that generalizes Maximum Coverage , Partial Vertex Cover , Max-2-SAT with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF formula \(\Phi\) , and a positive integer \( k \) , and the goal is to find an assignment \(\beta\) with at most \( k \) variables set to true (also called a \( k \) -weight assignment) such that the number of clauses satisfied by \(\beta\) is maximized. The problem is known to admit an approximation algorithm with factor \(1-\frac{1}{e}\) , which is probably optimal. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any \(\epsilon > 0\) and any function \( h \) , no \(h(k)(n+m)^{o(k)}\) time algorithm can approximate Maximum Coverage (a monotone version of CC-Max-Sat ) with \( n \) elements and \( m \) sets to within a factor \((1-\frac{1}{e}+\epsilon)\) , even with a promise that there exist \( k \) sets that fully cover the whole universe. In fact, the problem is hard to approximate within 0.929, assuming Unique Games Conjecture, even when the input formula is 2-CNF. These intractable results lead us to explore families of formula, where we can circumvent these barriers. Toward this, we consider \(K_{d,d}\) -free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes \(K_{d,d}\) as an induced subgraph). We show that for every \(\epsilon > 0\) , there exists an algorithm for CC-Max-Sat on \(K_{d,d}\) -free formulas with approximation ratio \((1-\epsilon)\) and running in time \(2^{{\mathcal{O}}((\frac{dk}{\epsilon})^{d})}(n+m)^{{\mathcal{O}}(1)}\) (these algorithms are called FPT-AS). For Maximum Coverage on \(K_{d,d}\) -free set families, we obtain FPT-AS with running time \((\frac{dk}{\epsilon})^{{\mathcal{O}}(dk)}n^{{\mathcal{O}}(1)}\) . Our second result considers “optimizing \( k \) ,” with fixed covering constraint for the Maximum Coverage problem. To explain our result, we first recast the Maximum Coverage problem as the Max Red Blue Dominating Set with Covering Constraint problem. Here, the input is a bipartite graph \(G=(A,B,E)\) , a positive integer \( t \) , and the objective is to find a minimum sized subset \(S\subseteq A\) , such that \(|N(S)|\) (the size of the set of neighbors of \( S \) ) is at least \( t \) . We design an additive approximation algorithm for Max Red Blue Dominating Set with Covering Constraint , on \(K_{d,d}\) -free bipartite graphs, running in FPT time. In particular, if

In Two-Sets Cut-Uncut , we are given an undirected graph G = ( V , E ) and two terminal sets S and T . The task is to find a minimum cut C in G (if there is any) separating S from T under the following “uncut” condition. In the graph ( V, E ∖ C ), the terminals in each terminal set remain in the same connected component. In spite of the superficial similarity to the classic problem Minimum s-t-Cut , Two-Sets Cut-Uncut is computationally challenging. In particular, even deciding whether such a cut of any size exists, is already NP-complete. We initiate a systematic study of Two-Sets Cut-Uncut within the context of parameterized complexity. By leveraging known relations between many well-studied graph parameters, we characterize the structural properties of input graphs that allow for polynomial kernels, fixed-parameter tractability (FPT), and slicewise polynomial algorithms (XP). Our main contribution is the near-complete establishment of the complexity of these algorithmic properties within the described hierarchy of graph parameters. On a technical level, our main results are fixed-parameter tractability for the (vertex-deletion) distance to cographs and an OR-cross composition excluding polynomial kernels for the vertex cover number of the input graph (under the standard complexity assumption NP ¬ ⊆ coNP/poly).

Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in ℝ^d (d ≥ 1), or equivalently, distance spaces that can be isometrically embedded in ℝ^d. In this work, we investigate whether a distance space can be isometrically embedded in ℝ^d after applying a limited number of modifications. Specifically, we focus on two types of modifications: outlier deletion (removing points) and distance modification (adjusting distances between points). The central problem, Euclidean Embedding Editing, asks whether an input distance space on n points can be transformed, using at most k modifications, into a space that is isometrically embeddable in ℝ^d. We present several fixed-parameter tractable (FPT) and approximation algorithms for this problem. Our first result is an algorithm that solves Euclidean Embedding Editing in time (dk)^𝒪(d+k) + n^𝒪(1). The core subroutine of this algorithm, which is of independent interest, is a polynomial-time method for compressing the input distance space into an equivalent instance of Euclidean Embedding Editing with 𝒪((dk)²) points. For the special but important case of Euclidean Embedding Editing where only outlier deletions are allowed, we improve the parameter dependence of the FPT algorithm and obtain a running time of min{(d+3)^k, 2^{d+k}} ⋅ n^𝒪(1). Additionally, we provide an FPT-approximation algorithm for this problem, which outputs a set of at most 2 ⋅ Opt outliers in time 2^d ⋅ n^{𝒪(1)}. This 2-approximation algorithm improves upon the previous (3+ε)-approximation algorithm by Sidiropoulos, Wang, and Wang [SODA '17]. Furthermore, we complement our algorithms with hardness results motivating our choice of parameterizations.

The pathwidth of a graph is a measure of how path-like the graph is. The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most one. This is a natural variation of the classical Feedback vertex Set (FVS) problem, where the deletion of at most k vertices results in a graph of treewidth at most one. In this work, we investigate POVD in the realm of approximation algorithms. We first design a 3-approximation algorithm for POVD running in polynomial time. Then, using this constant factor approximation algorithm, we obtain a randomized parameterized approximation algorithm for POVD running in time 𝒪^*((h_β)^k), that improves the fastest existing running times for approximation ratios in the range (1.76147,3). Here the constant h_β depends on the approximation factor β alone and has value 2^{(3-β)}, which lies in the range (1,2.3596), when β ∈ (1.76147,3). Taking inspiration from two extensively studied problems, namely Connected FVS and Independent FVS, we investigate two variations of the POVD problem from the perspective of parameterized algorithms. These variations are the connected variant, called Connected pathwidth One Vertex Deletion (CPOVD) and the independent variant, called Independent Pathwidth One Vertex Deletion (IPOVD). While in CPOVD the subgraph G[S] induced by the vertices to be deleted needs to be connected, in IPOVD it needs to be independent. Specifically, we show the following results. - CPOVD can be solved in {𝒪}^*(14^k) time and admits no polynomial kernel unless NP ⊆ {co-NP/poly}. - IPOVD can be solved in {𝒪}^*(7^k) time, and admits a kernel of size 𝒪(k³).

We prove a robust contraction decomposition theorem for $H$-minor-free graphs, which states that given an $H$-minor-free graph $G$ and an integer $p$, one can partition in polynomial time the vertices of $G$ into $p$ sets $Z_1,\dots,Z_p$ such that $\operatorname{tw}(G/(Z_i \setminus Z')) = O(p + |Z'|)$ for all $i \in [p]$ and $Z' \subseteq Z_i$. Here, $\operatorname{tw}(\cdot)$ denotes the treewidth of a graph and $G/(Z_i \setminus Z')$ denotes the graph obtained from $G$ by contracting all edges with both endpoints in $Z_i \setminus Z'$. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning $E(G)$, and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time $2^{\widetilde{O}(\sqrt{k})} \cdot n^{O(1)}$ or $n^{O(\sqrt{k})}$ for every vertex/edge deletion problems on $H$-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on $H$-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on $H$-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time.

Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. Given a set of candidates, C, a set of voters, V, approving a subset of candidates (called approval set of a voter), and an integer k, we consider the problem of selecting a ``good'' committee using Thiele rules. This problem is computationally challenging for most Thiele rules with monotone submodular satisfaction functions, as there is no (1-1/e- epsilon) approximation algorithm in f(k)(|C| + |V|)^(o(k)) time for any fixed epsilon > 0 and any computable function f, and no PTAS even when the length of approval set is two. Skowron designed an approximation scheme running in FPT time parameterized by the combined parameter, size of the approval set, and k. In this paper, we consider a parameter d+k (no d voters approve the same set of d candidates), where d is upper bounded by the size of the approval set (thus, can be much smaller). With respect to this parameter, we design parameterized approximation schemes, a lossy polynomial-time preprocessing method, and show that an extra committee member suffices to achieve the desired score (i.e., 1-additive approximation). Additionally, we resolve an open question by Yang and Wang regarding the fixed-parameter tractability of the problem under the PAV rule with the total score as the parameter, demonstrating that it admits an FPT algorithm.

The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph $G$ and an integer $k\in\mathbb{N}$ as input, the goal is to determine whether we can perform at most $k$ operations on $G$ to transform it into a graph belonging to a specified graph class $\mathcal{F}$. Typical operations are combinatorial and include vertex deletions and edge deletions, insertions, and contractions. However, in many real-world scenarios, when the input graph is constrained to be a geometric intersection graph, the modification of the graph is influenced by changes in the geometric properties of the underlying objects themselves, rather than by combinatorial modifications. It raises the question of whether vertex deletions or adjacency modifications are necessarily the most appropriate modification operations for studying modifications of geometric graphs. We propose the study of the disk intersection graph modification through the scaling of disks. This operation is typical in the realm of topology control but has not yet been explored in the context of Parameterized Complexity. We design parameterized algorithms and kernels for modifying to the most basic graph classes: edgeless, connected, and acyclic. Our technical contributions encompass a novel combination of linear programming, branching, and kernelization techniques, along with a fresh application of bidimensionality theory to analyze the area covered by disks, which may have broader applicability.

In this paper, we study the Achromatic Number problem. Given a graph G and an integer k, the task is to determine whether there exists a proper coloring of G, using at least k colors, in which every pair of distinct colors appears on the endpoints of some edge. It was established early on that the problem is fixed-parameter tractable (FPT)- even before the formal development of parameterized complexity. In fact, Farber, Hahn, Hell, and Miller [JCTB, 1986] devised an algorithm with a running time of 𝒪(f(k) ⋅ |E(G)|). Although the exact form of f(k) was not specified, it appears to be at least doubly exponential in k. In our work, we first present an algorithm with an explicit dependence on k, and then introduce another algorithm that is parameterized by the vertex cover number of the graph. More formally, we show the following. - Achromatic Number is solvable in time 2^𝒪(k⁵)+𝒪(|E(G)|). - Achromatic Number admits a polynomial kernel when the input is restricted to a d-degenerate graph and a more efficient kernel on trees. - We also study the parameterized complexity of the problem with respect to Vertex Cover and show that it admits an FPT algorithm running in time 2^𝒪(𝓁²) ⋅ n^𝒪(1), where 𝓁 is the size of a vertex cover.

In this paper, we suggest to extend the notion of a kernel to permit the kernelization algorithm to be executed in quasi-polynomial time rather than polynomial time. So far, we are only aware of one work that addressed this negatively, showing that some lower bounds on kernel sizes proved for kernelization also hold when quasi-polynomial time complexity is allowed. When we, anyway, deal with an NP-hard problem, sacrificing polynomial time in preprocessing for quasi-polynomial time may often not be a big deal, but, of course, the question is - does it give us more power? The only known work, mentioned above, seems to suggest that the answer is "no". In this paper, we show that this is not the case - in particular, we show that this notion is extremely powerful for derandomization. Some of the most basic kernelization algorithms in the field are based on inherently randomized tools whose derandomization is a huge problem that has remained (and may still remain) open for many decades. Still, some breakthrough advances for derandomization in quasi-polynomial time have been made. Can we harness these advancements to design quasi-polynomial deterministic kernelization algorithms for basic problems in the field? To this end, we revisit the question of deterministic polynomial-time computation of a linear representation of transversal matroids and gammoids, which is a longstanding open problem. We present a deterministic computation of a representation matrix of a transversal matroid in time quasipolynomial in the rank of the matroid, where each entry of the matrix can be represented in quasipolynomial (in the rank of the matroid) bits. As a corollary, we obtain a linear representation of a gammoid in deterministic quasipolynomial time and quasipolynomial bits in the size of the underlying ground set of the gammoid. In turn, as applications of our results, we present deterministic quasi-polynomial time kernels of polynomial size for several central problems in the field.

The Euclidean Traveling Salesman Problem with Neighborhoods (ETSPN) is a well-studied problem in computational geometry and has a wealth of results. In this problem, given a set of geometric neighborhoods (or regions), the goal is to compute a shortest route that visits at least one point of each neighborhood. The problem is a generalization of the standard Euclidean TSP and hence is also NP-hard, even when the neighborhoods are disjoint unit disks or unit squares in the plane. A longstanding open problem on this topic is the existence of PTASes for ETSPN with unit disk (and unit square) neighborhoods. Prior to this work, the best-known approximation factor for unit disks is 6.75, and PTASes are only known for the special case where the unit disks/squares are of bounded depth, i.e., each point lies in at most a constant number of disks.

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Björklund, Husfeldt, ICALP 2014;

In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph. Ghaffari, Karger, and Panigrahi [SODA 2017] showed that Hedge Cut can be solved in quasipolynomial-time, raising the hope for a polynomial time algorithm. Jaffke, Lima, Masarik, Pilipczuk, and Souza [SODA 2023] complemented this result by showing that assuming the Exponential Time Hypothesis (ETH), no polynomial-time algorithm exists. In this paper, we show that Hedge Cut is fixed-parameter tractable parameterized by the solution size ℓ by providing an algorithm with running time , which can be upper bounded by Cℓ · (n + m)O (1) for any constant c > 1. This running time captures at the same time the fact that the problem is quasipolynomial-time solvable, and that it is fixed-parameter tractable parameterized by ℓ. We further generalize this algorithm to an algorithm with running time for Hedge k-CUT.

A drawing of an (undirected) graph G is a mapping φ that assigns to each vertex a distinct point in the plane and to each edge uw a continuous curve φ (uυ ) in the plane from φ (η ) to φ(ν ), not passing through the image of any other vertex. Two edges e and f cross in a point p if p € φ (e ) ∩ φ (f ) and p is not the image of a vertex of G. In a drawing no three edges are allowed to cross in the same point. The crossing number of a drawing of G is the number of points p such that some two edges e and f cross in p. In the CROSSING Number problem, the input consists of a graph G and integer k. The task is to determine whether there exists a drawing of G with crossing number at most k, and to output such a drawing if it exists.

In the CAPACITATED d-HlTTING Set problem input is a universe U equipped with a capacity function cap : U → ℕ, and a collection A of subsets of U, each of size at most d. The task is to find a minimum size subset S of U and an assignment φ : A → S such that, for every set A ∈ A we have φ (Α ) ∈ A and for every x ∈ U we have |φ-1(χ)| ≤ cap(x ). Here φ-1(χ) is the collection of sets in A mapped to x by φ. Such a set S is called a capacitated hitting set. When d = 2 the problem is known under the name CAPACITATED VERTEX COVER. In Weighted Capacitated d-HlTTING Set each element of U has a positive integer weight and the goal is to find a capacitated hitting set of minimum weight.

The classic greedy coloring (first-fit) algorithm considers the vertices of an input graph $G$ in a given order and assigns the first available color to each vertex $v$ in $G$. In the {\sc Grundy Coloring} problem, the task is to find an ordering of the vertices that will force the greedy algorithm to use as many colors as possible. In the {\sc Partial Grundy Coloring}, the task is also to color the graph using as many colors as possible. This time, however, we may select both the ordering in which the vertices are considered and which color to assign the vertex. The only constraint is that the color assigned to a vertex $v$ is a color previously used for another vertex if such a color is available. Whether {\sc Grundy Coloring} and {\sc Partial Grundy Coloring} admit fixed-parameter tractable (FPT) algorithms, algorithms with running time $f(k)n^{\OO(1)}$, where $k$ is the number of colors, was posed as an open problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et al. (STACS 2020 and Algorithmica 2022) resolved the question for \Grundycol\ in the negative by showing that the problem is W[1]-hard. For {\sc Partial Grundy Coloring}, they obtain an FPT algorithm on graphs that do not contain $K_{i,j}$ as a subgraph (a.k.a. $K_{i,j}$-free graphs). Aboulker et al.~re-iterate the question of whether there exists an FPT algorithm for {\sc Partial Grundy Coloring} on general graphs and also asks whether {\sc Grundy Coloring} admits an FPT algorithm on $K_{i,j}$-free graphs. We give FPT algorithms for {\sc Partial Grundy Coloring} on general graphs and for {\sc Grundy Coloring} on $K_{i,j}$-free graphs, resolving both the questions in the affirmative. We believe that our new structural theorems for partial Grundy coloring and ``representative-family'' like sets for $K_{i,j}$-free graphs that we use in obtaining our results may have wider algorithmic applications.

Let G be a weighted graph embedded in a metric space (M, d_M). The vertices of G correspond to the points in M, with the weight of each edge uv being the distance d_M(u,v) between their respective points in M. The dilation (or stretch) of G is defined as the minimum factor t such that, for any pair of vertices u,v, the distance between u and v - represented by the weight of a shortest u,v-path - is at most t⋅ d_M(u,v). We study Dilation t-Augmentation, where the objective is, given a metric M, a graph G, and numerical values k and t, to determine whether G can be transformed into a graph with dilation t by adding at most k edges. Our primary focus is on the scenario where the metric M is the shortest path metric of an unweighted graph Γ. Even in this specific case, Dilation t-Augmentation remains computationally challenging. In particular, the problem is W[2]-hard parameterized by k when Γ is a complete graph, already for t = 2. Our main contribution lies in providing new insights into the impact of combinations of various parameters on the computational complexity of the problem. We establish the following. - The parameterized dichotomy of the problem with respect to dilation t, when the graph G is sparse: Parameterized by k, the problem is FPT for graphs excluding a biclique K_{d,d} as a subgraph for t ≤ 2 and the problem is W[1]-hard for t ≥ 3 even if G is a forest consisting of disjoint stars. - The problem is FPT parameterized by the combined parameter k+t+Δ, where Δ is the maximum degree of the graph G or Γ.

Abstract In this paper, we introduce a directed variant of the classical Bandwidthproblem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph $$\varvec{D}$$ D and an ordering $$\varvec{\sigma }$$ σ of its vertices, the digraph bandwidth of $$\varvec{\sigma }$$ σ with respect to $$\varvec{D}$$ D is equal to the maximum value of $$\varvec{\sigma (v)}-\varvec{\sigma (u)}$$ σ ( v ) - σ ( u ) over all arcs $$\varvec{(u,v)}$$ ( u , v ) of $$\varvec{D}$$ D going forward along $$\varvec{\sigma }$$ σ (that is, when $$\varvec{\sigma (u)} < \varvec{\sigma (v)}$$ σ ( u ) < σ ( v ) ). The Digraph Bandwidth problem takes as input a digraph $$\varvec{D}$$ D and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidtheasily reduces to Digraph Bandwidth and thus, it immediately implies that Digraph Bandwidth is -hard. While an $$\varvec{\mathcal {O}}^{\star }\varvec{(n!)}$$ O ⋆ ( n ! ) time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form $$\varvec{2}^{\varvec{\mathcal {O}(n)}}$$ 2 O ( n ) . In particular, we obtain the following results. Here, $$\varvec{n}$$ n and $$\varvec{m}$$ m denote the number of vertices and arcs of the input digraph $$\varvec{D}$$ D , respectively. Digraph Bandwidth can be solved in $$\varvec{\mathcal {O}}^\star (\varvec{3}^{\varvec{n}} \cdot \varvec{2}^{\varvec{m}})$$ O ⋆ ( 3

Abstract. In the disjoint paths problem, the input is an undirected graph [Formula: see text] on [Formula: see text] vertices and a set of [Formula: see text] vertex pairs, [Formula: see text], and the task is to find [Formula: see text] pairwise vertex-disjoint paths such that the [Formula: see text]’th path connects [Formula: see text] to [Formula: see text]. In this paper, we give a parameterized algorithm with running time [Formula: see text] for planar disjoint paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [ J. Combin. Theory Ser. B, 122 (2017), pp. 815–843], the algebraic cohomology based technique of Schrijver [ SIAM J. Comput., 23 (1994), pp. 780–788], and one of the key combinatorial insights developed by Cygan et al. [ Proceedings of the 2013 IEEE 54 th Annual Symposium on Foundations of Computer Science, 2013, pp. 197–206] in their algorithm for disjoint paths on directed planar graphs. To the best of our knowledge, our algorithm is the first parameterized algorithm to exploit the fact that the treewidth of the input graph is small, and it does so in a way that is completely different from the use of dynamic programming.

An independent set in a graph \(G\) is a set of pairwise non-adjacent vertices. A graph \(G\) is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, the input is a graph \(G\) along with a weight function w associating a rational weight with each vertex, and the task is to find a minimum weight vertex subset \(S\) in \(G\) such that \(G-S\) is bipartite; the weight of \(S\) , \(\text{w}(S)=\sum_{v\in S}\text{w}(v)\) . We show that Odd Cycle Transversal is polynomial-time solvable on graphs excluding \(P_{5}\) (a path on five vertices) as an induced subgraph. The problem was previously known to be polynomial-time solvable on \(P_{4}\) -free graphs and NP -hard on \(P_{6}\) -free graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rzążewski, Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma [Algorithmica 2019] posed the existence of a polynomial-time algorithm on \(P_{5}\) -free graphs as an open problem. This was later re-stated by Rzążewski [Dagstuhl Reports, 9(6): 2019], by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [SIDMA 2021] who gave an algorithm with running time \(n^{O(\sqrt{n})}\) for the problem, and by Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024] who gave a quasi-polynomial time algorithm.

We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clusetring problem, given a set P of points in R^d, an integer k, and a non-negative real r, our objective is to position k closed balls of radius r to minimize the sum of distances from points not covered by the balls to their closest balls. Equivalently, we seek an optimal L_1-fitting of a union of k balls of radius r to a set of points in the Euclidean space. When r=0, this corresponds to k-median; when the minimum sum is zero, indicating complete coverage of all points, it is k-center. Our primary result is a bicriteria approximation algorithm that, for a given ε>0, produces a hybrid k-clustering with balls of radius (1+ε)r. This algorithm achieves a cost at most 1+εof the optimum, and it operates in time 2^{(kd/ε)^{O(1)}} n^{O(1)}. Notably, considering the established lower bounds on k-center and k-median, our bicriteria approximation stands as the best possible result for Hybrid k-Clusetring.

In a disk graph, every vertex corresponds to a disk in $\mathbb{R}^2$ and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an important class of geometric intersection graphs, which generalizes both planar graphs and unit-disk graphs. We study a fundamental optimization problem in algorithmic graph theory, Bipartization (also known as Odd Cycle Transversal), on the class of disk graphs. The goal of Bipartization is to delete a minimum number of vertices from the input graph such that the resulting graph is bipartite. A folklore (polynomial-time) $3$-approximation algorithm for Bipartization on disk graphs follows from the classical framework of Goemans and Williamson [Combinatorica'98] for cycle-hitting problems. For over two decades, this result has remained the best known approximation for the problem (in fact, even for Bipartization on unit-disk graphs). In this paper, we achieve the first improvement upon this result, by giving a $(3-α)$-approximation algorithm for Bipartization on disk graphs, for some constant $α>0$. Our algorithm directly generalizes to the broader class of pseudo-disk graphs. Furthermore, our algorithm is robust in the sense that it does not require a geometric realization of the input graph to be given.

$\newcommand{\eps}{\varepsilon}$ We observe that a $(1-\eps)$-approximation algorithm to Independent Set, that works for any induced subgraph of the input graph, can be used, via a polynomial time reduction, to provide a $(1+\eps)$-approximation to Vertex Cover. This basic observation was made before, see [BHR11]. As a consequence, we get a PTAS for VC for unweighted pseudo-disks, QQPTAS for VC for unweighted axis-aligned rectangles in the plane, and QPTAS for MWVC for weighted polygons in the plane. To the best of our knowledge all these results are new.

Learning the structure of a Bayesian network from data is one of the key problems in probabilistic graphical models. Unfortunately, the problem is NP-hard and this has motivated recent works where the problem has been studied from the perspective of algorithmic paradigms meant for coping with hardness, such as parameterized complexity. We contribute to this area by designing fixed parameter tractable algorithms (FPT) to learn the Bayesian network structure when only a few variables are important. In particular, we study score-based structure learning where each graph is given with a score, based on how well it fits to the data, and the goal is to select the acyclic directed graph (DAG) that maximizes the score. Typically, one uses decomposable scores, where the score of a DAG is the sum of local scores for node-parent set pairs. We study a variant of this problem in which our objective is to find a k-heavy DAG, which is a DAG whose k most scoring nodes have a total score of at least some target value ℓ. We show that 1. if there is a k-heavy DAG with a maximum degree of d, then we can learn it in time f(k,d)nO(d) and 2. if there is a k-heavy DAG whose moralized graph has a treewidth of t and a maximum degree of t, then we can learn it in time f(k,t)nO(t). These algorithms leverage the color-coding technique from the field of Parameterized Complexity in a non-trivial manner.

Vertex (s, t)-Cut and Vertex Multiway Cut are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these problems, where in addition to the usual input, we are given a representation R ∈ 𝔽^{r × n} of a linear matroid ℳ = (V(G), ℐ) of rank r in the input, and the goal is to determine whether there exists a vertex subset S ⊆ V(G) that has the required cut properties, as well as is independent in the matroid ℳ. We refer to these problems as Independent Vertex (s, t){-cut}, and Independent Multiway Cut, respectively. We show that these problems are fixed-parameter tractable (FPT) when parameterized by the solution size (which can be assumed to be equal to the rank of the matroid ℳ). These results are obtained by exploiting the recent technique of flow augmentation [Kim et al. STOC '22], combined with a dynamic programming algorithm on flow-paths á la [Feige and Mahdian, STOC '06] that maintains a representative family of solutions w.r.t. the given matroid [Marx, TCS '06; Fomin et al., JACM]. As a corollary, we also obtain FPT algorithms for the independent version of Odd Cycle Transversal. Further, our results can be generalized to other variants of the problems, e.g., weighted versions, or edge-deletion versions.

We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input n-vertex m-edge hypergraph$H$of fractional hypertree width at most$\omega$, runs in polynomial time and produces a tree decomposition of$H$of fractional hypertree width$\mathcal{O}(\omega\log n\log\omega)$, i.e., it is an$\mathcal{O}(\log n\log\omega)$-approximation algorithm. As an immediate corollary this yields poly-nomial time$\mathcal{O}(\log^{2}n\log\omega)$-approximation algorithms for (generalized) hypertree width as well. To the best of our knowledge our algorithm is the first non-trivial polynomial-time approximation algorithm for fractional hypertree width and (generalized) hypertree width, as opposed to algorithms that run in polynomial time only when$\omega$is considered a constant. For hypergraphs where every pair of hyperedges have at most$\eta$vertices in common, the al-gorithm outputs a hypertree decomposition with fractional hypertree width$\mathcal{O}(\eta\omega^{2}\log\omega)$and generalized hypertree width$\mathcal{O}(\eta\omega^{2}\log\omega(\log\eta+\text{log}\omega))$. This ratio is comparable with the recent algorithm of Lanzinger and Razgon [STACS 2024], which produces a hypertree decomposition with generalized hypertree width${\mathcal{O}}(\omega^{2}(\omega+\eta))$, but uses time (at least) exponential in$\eta$and$\omega$. The second algorithm runs in time$n^{\omega}m^{\mathcal{O}(1)}$and pro-duces a tree decomposition of$H$of fractional hypertree width$\mathcal{O}(\omega{\mathrm{l}}\text{og}^{2}\omega)$. This significantly improves over the$(n+m)^{\mathcal{O}(\omega^{3})}$time algorithm of Marx [ACM TALG 2010], which produces a tree decomposition of fractional hyper-tree width$\mathcal{O}(\omega^{3})$, both in terms of running time and the approximation ratio. Our main technical contribution, and the key insight behind both algorithms, is a variant of the classic Menger's Theorem for clique separators in graphs: For every graph$G$, vertex sets$A$and$B$, family$\mathcal{F}$of cliques in$G$, and positive rational$f$, either there exists a sub-family of$\mathcal{O}(f \cdot {\mathrm{l}}\text{og}^{2}n)$cliques in$\mathcal{F}$whose union separates$A$from$B$, or there exist$f\cdot\log\vert \mathcal{F}\vert$paths from$A$to$B$such that no clique in$\mathcal{F}$intersects more than$\log\vert \mathcal{F}\vert$paths.

Classical work on metric space based committee selection problem interprets distance as ``near is better''. In this work, motivated by real-life situations, we interpret distance as ``far is better''. Formally stated, we initiate the study of ``obnoxious'' committee scoring rules when the voters' preferences are expressed via a metric space. To this end, we propose a model where large distances imply high satisfaction and study the egalitarian avatar of the well-known Chamberlin-Courant voting rule and some of its generalizations. For a given integer value $1 \le λ\le k$, the committee size k, a voter derives satisfaction from only the $λ$-th favorite committee member; the goal is to maximize the satisfaction of the least satisfied voter. For the special case of $λ= 1$, this yields the egalitarian Chamberlin-Courant rule. In this paper, we consider general metric space and the special case of a $d$-dimensional Euclidean space. We show that when $λ$ is $1$ and $k$, the problem is polynomial-time solvable in $\mathbb{R}^2$ and general metric space, respectively. However, for $λ= k-1$, it is NP-hard even in $\mathbb{R}^2$. Thus, we have ``double-dichotomy'' in $\mathbb{R}^2$ with respect to the value of λ, where the extreme cases are solvable in polynomial time but an intermediate case is NP-hard. Furthermore, this phenomenon appears to be ``tight'' for $\mathbb{R}^2$ because the problem is NP-hard for general metric space, even for $λ=1$. Consequently, we are motivated to explore the problem in the realm of (parameterized) approximation algorithms and obtain positive results. Interestingly, we note that this generalization of Chamberlin-Courant rules encodes practical constraints that are relevant to solutions for certain facility locations.

In the MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k-assignment) such that the number of clauses satisfied by β is maximized. Maximum Coverage can be seen as a special case of CC-MaxSat, where the formula Φ is monotone, i.e., does not contain any negative literals. CC-MaxSat and Maximum Coverage are extremely well-studied problems in the approximation algorithms as well as the parameterized complexity literature. Our first conceptual contribution is that CC-MaxSat and Maximum Coverage are equivalent to each other in the context of FPT-Approximation parameterized by k (here, the approximation is in terms of the number of clauses satisfied/elements covered). In particular, we give a randomized reduction from CC-MaxSat to Maximum Coverage running in time 𝒪(1/ε)^{k} ⋅ (m+n)^{𝒪(1)} that preserves the approximation guarantee up to a factor of (1-ε). Furthermore, this reduction also works in the presence of "fairness" constraints on the satisfied clauses, as well as matroid constraints on the set of variables that are assigned true. Here, the "fairness" constraints are modeled by partitioning the clauses of the formula Φ into r different colors, and the goal is to find an assignment that satisfies at least t_j clauses of each color 1 ≤ j ≤ r. Armed with this reduction, we focus on designing FPT-Approximation schemes (FPT-ASes) for Maximum Coverage and its generalizations. Our algorithms are based on a novel combination of a variety of ideas, including a carefully designed probability distribution that exploits sparse coverage functions. These algorithms substantially generalize the results in Jain et al. [SODA 2023] for CC-MaxSat and Maximum Coverage for K_{d,d}-free set systems (i.e., no d sets share d elements), as well as a recent FPT-AS for Matroid Constrained Maximum Coverage by Sellier [ESA 2023] for frequency-d set systems.

We introduce a new framework for the analysis of preprocessing routines for parameterized counting problems. Existing frameworks that encapsulate parameterized counting problems permit the usage of exponential (rather than polynomial) time either explicitly or by implicitly reducing the counting problems to enumeration problems. Thus, our framework is the only one in the spirit of classic kernelization (as well as lossy kernelization). Specifically, we define a compression of a counting problem P into a counting problem Q as a pair of polynomial-time procedures: reduce and lift. Given an instance of P, reduce outputs an instance of Q whose size is bounded by a function f of the parameter, and given the number of solutions to the instance of Q, lift outputs the number of solutions to the instance of P. When P = Q, compression is termed kernelization, and when f is polynomial, compression is termed polynomial compression. Our technical (and other conceptual) contributions can be classified into two categories: Upper Bounds. We prove two theorems: (i) The #Vertex Cover problem parameterized by solution size admits a polynomial kernel; (ii) Every problem in the class of #Planar F-Deletion problems parameterized by solution size admits a polynomial compression. Lower Bounds. We introduce two new concepts of cross-compositions: EXACT-cross-composition and SUM-cross-composition. We prove that if a #P-hard counting problem P EXACT-cross-composes into a parameterized counting problem Q, then Q does not admit a polynomial compression unless the polynomial hierarchy collapses. We conjecture that the same statement holds for SUM-cross-compositions. Then, we prove that: (i) #Min (s,t)-Cut parameterized by treewidth does not admit a polynomial compression unless the polynomial hierarchy collapses; (ii) #Min (s,t)-Cut parameterized by minimum cut size, #Odd Cycle Transversal parameterized by solution size, and #Vertex Cover parameterized by solution size minus maximum matching size, do not admit polynomial compressions unless our conjecture is false.

Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gain new insights about our surroundings. Even if the final application concerns a different problem (such as traversal, finding paths, trees, and flows), decomposing large graphs is often an important subproblem for complexity reduction or parallelization. This report is a summary of discussions that happened at Dagstuhl seminar 23331 on "Recent Trends in Graph Decomposition" and presents currently open problems and future directions in the area of (hyper)graph decomposition.

An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph G is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, the input is a graph G along with a weight function w associating a rational weight with each vertex, and the task is to find a smallest weight vertex subset S in G such that G — S is bipartite; the weight of . We show that Odd Cycle Transversal admits an algorithm with running time on graphs excluding P5 (a path on five vertices) as an induced subgraph. The problem was previously known to be polynomial time solvable on P4-free graphs and NP-hard on P6-free graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rzążewski, Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma [Algorithmica 2019] posed the existence of a polynomial time algorithm on P5-free graphs as an open problem, this was later re-stated by Rzążewski [Dagstuhl Reports, 9(6): 2019] and by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [SIDMA 2021], who gave an algorithm with running time . While our time algorithm falls short of completely resolving the complexity status of Odd Cycle Transversal on P5-free graphs it shows that the problem is not NP-hard unless every problem in NP is solvable in quasi-polynomial time.

In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of n points in ℝ2 called terminals and a parameter k, and the goal is to compute a Steiner tree that spans all the terminals and contains at most k points of ℝ2 as Steiner points such that the maximum edge-length of the Steiner tree is minimized, where the length of a tree edge is the Euclidean distance between its two endpoints. The problem is well-studied and is known to be NP-hard. In this paper, we give a kO(k)nO(1)-time algorithm for Euclidean Bottleneck Steiner Tree, which implies that the problem is fixed-parameter tractable (FPT). This settles an open question explicitly asked by Bae et al. [Algorithmica, 2011], who showed that the ℓ1 and ℓ∞ variants of the problem are FPT. Our approach can be generalized to the problem with ℓp metric for any rational 1 ≤ ρ ≤ ∞, or even other metrics on ℝ2.

The streaming model was introduced to parameterized complexity independently by Fafianie and Kratsch [MFCS14] and by Chitnis, Cormode, Hajiaghayi and Monemizadeh [SODA15]. Subsequently, it was broadened by Chitnis, Cormode, Esfandiari, Hajiaghayi and Monemizadeh [SPAA15] and by Chitnis, Cormode, Esfandiari, Hajiaghayi, McGregor, Monemizadeh and Vorotnikova [SODA16]. Despite its strong motivation, the applicability of the streaming model to central problems in parameterized complexity has remained, for almost a decade, quite limited. Indeed, due to simple Ω(n)-space lower bounds for many of these problems, the kO(1) · polylog(n)-space requirement in the model is too strict.

Abstract The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of n equal disks packed into a rectangle and integers k and h, we ask whether it is possible by changing positions of at most h disks to pack $$n+k$$ n + k disks. Thus the problem of packing equal disks is the special case of our problem with $$n=h=0$$ n = h = 0 . While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for $$h=0$$ h = 0 . Our main algorithmic contribution is an algorithm that solves the repacking problem in time $$(h+k)^{\mathcal {O}(h+k)}\cdot |I|^{\mathcal {O}(1)}$$ ( h + k ) O ( h + k ) · | I | O ( 1 ) , where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h.

In the Min $k$-Cut problem, the input consists of an edge weighted graph $G$ and an integer $k$, and the task is to partition the vertex set into $k$ nonempty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$ is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta, Lee, and Li [ Proceedings of the 29 th Annual ACM-SIAM Symposium on Discrete Algorithms, A. Czumaj, ed., SIAM, Philadelphia, 2018, pp. 2821–2837] initiated the study of FPT-approximation for the Min $k$-Cut problem and gave a 1.9997-approximation algorithm running in time $2^{\mathcal{O}(k^6)}n^{\mathcal{O}(1)}$. Later, the same set of authors [ Proceedings of the 59 th IEEE Annual Symposium on Foundations of Computer Science, M. Thorup, ed., 2018, pp. 113–123] designed a $(1 +\epsilon)$-approximation algorithm that runs in time $(k/\epsilon)^{\mathcal{O}(k)}n^{k+\mathcal{O}(1)}$ and a 1.81-approximation algorithm running in time $2^{\mathcal{O}(k^2)}n^{\mathcal{O}(1)}$. More, recently, Kawarabayashi and Lin [ Proceedings of the 31 st ACM-SIAM Symposium on Discrete Algorithms, S. Chawla, ed., SIAM, Philadelphia, 2020, pp. 990–999] gave a $(5/3 + \epsilon)$-approximation for Min $k$-Cut running in time $2^{\mathcal{O}(k^2 \log k)}n^{\mathcal{O}(1)}$. In this paper, we give a parameterized approximation algorithm with best possible approximation guarantee and best possible running time dependence on said guarantee (up to the exponential time hypothesis and constants in the exponent). In particular, for every $\epsilon > 0$, the algorithm obtains a $(1 +\epsilon)$-approximate solution in time $(k/\epsilon)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. The main ingredients of our algorithm are a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time $s^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ on unweighted (multi-) graphs. Here, $s$ denotes the number of edges in a minimum $k$-cut. The latter two are of independent interest.

Abstract. Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received a lot of attention in parameterized complexity. In this paper, we initiate the study of a wide generalization of this problem called the [Formula: see text]-free Strong Connected Component Deletion problem, where [Formula: see text] is a finite family of digraphs. Here, one is given a digraph [Formula: see text] and an integer [Formula: see text], and the objective is to decide whether there is a vertex set of size at most [Formula: see text] whose deletion results in a digraph where every strongly connected component excludes graphs in family [Formula: see text] as (not necessarily induced) subgraphs. When [Formula: see text] comprises only the digraph with a single arc, then this problem is precisely the DFVS problem. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if [Formula: see text] only contains rooted graphs or if [Formula: see text] contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the results of Göke, Marx, and Mnich [ Proceedings of the International Conference on Algorithms and Complexity, Springer, 2019, pp. 249–261] for the 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion problems. Moreover, we design algorithms for the two above-mentioned problems, whose running times are better and that match with the best bounds for DFVS, without using the heavy machinery of shadow removal as is done by Göke, Marx, and Mnich [ Proceedings of the International Conference on Algorithms and Complexity, Springer, 2019, pp. 249–261].

We prove a structural theorem for unit-disk graphs, which (roughly) states that given a set \(\mathcal{D}\) of \(n\) unit disks inducing a unit-disk graph \(G_{\mathcal{D}}\) and a number \(p\in[n]\) , one can partition \(\mathcal{D}\) into \(p\) subsets \(\mathcal{D}_{1},\dots,\mathcal{D}_{p}\) such that for every \(i\in[p]\) and every \(\mathcal{D}^{\prime}\subseteq\mathcal{D}_{i}\) , the graph obtained from \(G_{\mathcal{D}}\) by contracting all edges between the vertices in \(\mathcal{D}_{i}\backslash\mathcal{D}^{\prime}\) admits a tree decomposition in which each bag consists of \(O(p+|\mathcal{D}^{\prime}|)\) cliques. Our theorem can be viewed as an analog for unit-disk graphs of the structural theorems for planar graphs and almost-embeddable graphs proved recently by Marx et al. [SODA ’22] and Bandyapadhyay et al. [SODA ’22]. By applying our structural theorem, we give several new combinatorial and algorithmic results for unit-disk graphs. On the combinatorial side, we obtain the first Contraction Decomposition Theorem for unit-disk graphs, resolving an open question in the work by Panolan et al. [SODA ’19]. On the algorithmic side, we obtain a new algorithm for bipartization (also known as odd cycle transversal) on unit-disk graphs, which runs in \(2^{O(\sqrt{k}\log k)}\cdot n^{O(1)}\) time, where \(k\) denotes the solution size. Our algorithm significantly improves the previous slightly subexponential-time algorithm given by Lokshtanov et al. [SODA ’22] which runs in \(2^{O(k^{27/28})}\cdot n^{O(1)}\) time. We also show that the problem cannot be solved in \(2^{o(\sqrt{k})}\cdot n^{O(1)}\) time assuming the Exponential Time Hypothesis, which implies that our algorithm is almost optimal.

We give a new decomposition theorem in unit disk graphs (UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits an “almost” Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010], and H -minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, and therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi ( www.youtube.com/watch?v=2Bq2gy1N01w ) regarding the existence of contraction decompositions for classes of graphs beyond H -minor free graphs though under a relaxation of the original formulation. Second, we present a “parameteric version” of our new decomposition theorem. We prove that there is an algorithm that, given a UDG G and a positive integer k , runs in polynomial time and outputs a collection of \(\mathcal {O}(k)\) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into \(\mathcal {O}(k)\) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G , there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece that is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or slightly super-exponential) algorithms for well-studied problems such as Min Bisection , Steiner Cut , s -Way Cut , and Edge Multiway Cut-Uncut on UDGs; these algorithms are substantially faster than the best-known algorithms for these problems on general graphs.

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k and m, the clustering with outliers aims to exclude m points from X, and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m (i.e., an algorithm with running time of the form f(k, m) * poly(n) for some function f), that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.

We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set $S$ of points and a set $\mathcal{R}$ of geometric objects, and the goal is to find a subset $\mathcal{R}^*\subseteq\mathcal{R}$ to cover all points in $S$ such that the \textit{membership} of $S$ with respect to $\mathcal{R}^*$, denoted by $\mathsf{memb}(S,\mathcal{R}^*)$, is minimized, where $\mathsf{memb}(S,\mathcal{R}^*)=\max_{p\in S}|\{R\in\mathcal{R}^*: p\in R\}|$. We achieve the following two main results. * We give the first polynomial-time constant-approximation algorithm for MMGSC with unit squares. This answers a question left open since the work of Erlebach and Leeuwen [SODA'08], who gave a constant-approximation algorithm with running time $n^{O(\mathsf{opt})}$ where $\mathsf{opt}$ is the optimum of the problem (i.e., the minimum membership). * We give the first polynomial-time approximation scheme (PTAS) for MMGSC with halfplanes. Prior to this work, it was even unknown whether the problem can be approximated with a factor of $o(\log n)$ in polynomial time, while it is well-known that the minimum-size set cover problem with halfplanes can be solved in polynomial time. We also consider a problem closely related to MMGSC, called minimum-ply geometric set cover (MPGSC), in which the goal is to find $\mathcal{R}^*\subseteq\mathcal{R}$ to cover $S$ such that the ply of $\mathcal{R}^*$ is minimized, where the ply is defined as the maximum number of objects in $\mathcal{R}^*$ which have a nonempty common intersection. Very recently, Durocher et al. gave the first constant-approximation algorithm for MPGSC with unit squares which runs in $O(n^{12})$ time. We give a significantly simpler constant-approximation algorithm with near-linear running time.

Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general metric into $k$ clusters to minimize the sum of cluster radii, subject to non-uniform hard capacity constraints. In particular, we give a $(15+ε)$-approximation algorithm that runs in $2^{0(k^2\log k)}\cdot n^3$ time. When capacities are uniform, we obtain the following improved approximation bounds: A (4 + $ε$)-approximation with running time $2^{O(k\log(k/ε))}n^3$, which significantly improves over the FPT 28-approximation of Inamdar and Varadarajan [ESA 2020]; a (2 + $ε$)-approximation with running time $2^{O(k/ε^2 \cdot\log(k/ε))}dn^3$ and a $(1+ε)$-approximation with running time $2^{O(kd\log ((k/ε)))}n^{3}$ in the Euclidean space; and a (1 + $ε$)-approximation in the Euclidean space with running time $2^{O(k/ε^2 \cdot\log(k/ε))}dn^3$ if we are allowed to violate the capacities by (1 + $ε$)-factor. We complement this result by showing that there is no (1 + $ε$)-approximation algorithm running in time $f(k)\cdot n^{O(1)}$, if any capacity violation is not allowed.

In the Minimum Bisection problem input is a graph G and the goal is to partition the vertex set into two parts A and B, such that ||A|-|B|| ≤ 1 and the number k of edges between A and B is minimized. The problem is known to be NP-hard, and assuming the Unique Games Conjecture even NP-hard to approximate within a constant factor [Khot and Vishnoi, J.ACM'15]. On the other hand, a 𝒪(log n)-approximation algorithm [Räcke, STOC'08] and a parameterized algorithm [Cygan et al., ACM Transactions on Algorithms'20] running in time k^𝒪(k) n^𝒪(1) is known. The Minimum Bisection problem can be viewed as a clustering problem where edges represent similarity and the task is to partition the vertices into two equally sized clusters while minimizing the number of pairs of similar objects that end up in different clusters. Motivated by a number of egregious examples of unfair bias in AI systems, many fundamental clustering problems have been revisited and re-formulated to incorporate fairness constraints. In this paper we initiate the study of the Minimum Bisection problem with fairness constraints. Here the input is a graph G, positive integers c and k, a function χ:V(G) → {1, …, c} that assigns a color χ(v) to each vertex v in G, and c integers r_1,r_2,⋯,r_c. The goal is to partition the vertex set of G into two almost-equal sized parts A and B with at most k edges between them, such that for each color i ∈ {1, …, c}, A has exactly r_i vertices of color i. Each color class corresponds to a group which we require the partition (A, B) to treat fairly, and the constraints that A has exactly r_i vertices of color i can be used to encode that no group is over- or under-represented in either of the two clusters. We first show that introducing fairness constraints appears to make the Minimum Bisection problem qualitatively harder. Specifically we show that unless FPT=W[1] the problem admits no f(c)n^𝒪(1) time algorithm even when k = 0. On the other hand, our main technical contribution shows that is that this hardness result is simply a consequence of the very strict requirement that each color class i has exactly r_i vertices in A. In particular we give an f(k,c,ε)n^𝒪(1) time algorithm that finds a balanced partition (A, B) with at most k edges between them, such that for each color i ∈ [c], there are at most (1±ε)r_i vertices of color i in A. Our approximation algorithm is best viewed as a proof of concept that the technique introduced by [Lampis, ICALP'18] for obtaining FPT-approximation algorithms for problems of bounded tree-width or clique-width can be efficiently exploited even on graphs of unbounded width. The key insight is that the technique of Lampis is applicable on tree decompositions with unbreakable bags (as introduced in [Cygan et al., SIAM Journal on Computing'14]). An important ingredient of our approximation scheme is a combinatorial result that may be of independent interest, namely that for every k, every graph G admits a tree decomposition with adhesions of size at most 𝒪(k), unbreakable bags, and logarithmic depth.

In the Vertex Connectivity Survivable Network Design (VC-SNDP) problem, the input is a graph G and a function d: V(G) × V(G) → ℕ that encodes the vertex-connectivity demands between pairs of vertices. The objective is to find the smallest subgraph H of G that satisfies all these demands. It is a well-studied NP-complete problem that generalizes several network design problems. We consider the case of uniform demands, where for every vertex pair (u,v) the connectivity demand d(u,v) is a fixed integer κ. It is an important problem with wide applications. We study this problem in the realm of Parameterized Complexity. In this setting, in addition to G and d we are given an integer 𝓁 as the parameter and the objective is to determine if we can remove at least 𝓁 edges from G without violating any connectivity constraints. This was posed as an open problem by Bang-Jansen et.al. [SODA 2018], who studied the edge-connectivity variant of the problem under the same settings. Using a powerful classification result of Lokshtanov et al. [ICALP 2018], Gutin et al. [JCSS 2019] recently showed that this problem admits a (non-uniform) FPT algorithm where the running time was unspecified. Further they also gave an (uniform) FPT algorithm for the case of κ = 2. In this paper we present a (uniform) FPT algorithm any κ that runs in time 2^{O(κ² 𝓁⁴ log 𝓁)}⋅ |V(G)|^O(1). Our algorithm is built upon new insights on vertex connectivity in graphs. Our main conceptual contribution is a novel graph decomposition called the Wheel decomposition. Informally, it is a partition of the edge set of a graph G, E(G) = X₁ ∪ X₂ … ∪ X_r, with the parts arranged in a cyclic order, such that each vertex v ∈ V(G) either has edges in at most two consecutive parts, or has edges in every part of this partition. The first kind of vertices can be thought of as the rim of the wheel, while the second kind form the hub. Additionally, the vertex cuts induced by these edge-sets in G have highly symmetric properties. Our main technical result, informally speaking, establishes that "nearly edge-minimal’’ κ-vertex connected graphs admit a wheel decomposition - a fact that can be exploited for designing algorithms. We believe that this decomposition is of independent interest and it could be a useful tool in resolving other open problems.

We consider the following problem about dispersing points. Given a set of points in the plane, the task is to identify whether by moving a small number of points by small distance, we can obtain an arrangement of points such that no pair of points is "close" to each other. More precisely, for a family of n points, an integer k, and a real number d > 0, we ask whether at most k points could be relocated, each point at distance at most d from its original location, such that the distance between each pair of points is at least a fixed constant, say 1. A number of approximation algorithms for variants of this problem, under different names like distant representatives, disk dispersing, or point spreading, are known in the literature. However, to the best of our knowledge, the parameterized complexity of this problem remains widely unexplored. We make the first step in this direction by providing a kernelization algorithm that, in polynomial time, produces an equivalent instance with 𝒪(d²k³) points. As a byproduct of this result, we also design a non-trivial fixed-parameter tractable (FPT) algorithm for the problem, parameterized by k and d. Finally, we complement the result about polynomial kernelization by showing a lower bound that rules out the existence of a kernel whose size is polynomial in k alone, unless NP ⊆ coNP/poly.

We re-visit the complexity of polynomial time pre-processing (kernelization) for the d-Hitting Set problem. This is one of the most classic problems in Parameterized Complexity by itself, and, furthermore, it encompasses several other of the most well-studied problems in this field, such as Vertex Cover, Feedback Vertex Set in Tournaments (FVST) and Cluster Vertex Deletion (CVD). In fact, d-Hitting Set encompasses any deletion problem to a hereditary property that can be characterized by a finite set of forbidden induced subgraphs. With respect to bit size, the kernelization complexity of d-Hitting Set is essentially settled: there exists a kernel with 𝒪(k^d) bits (𝒪(k^d) sets and 𝒪(k^{d-1}) elements) and this it tight by the result of Dell and van Melkebeek [STOC 2010, JACM 2014]. Still, the question of whether there exists a kernel for d-Hitting Set with fewer elements has remained one of the most major open problems in Kernelization. In this paper, we first show that if we allow the kernelization to be lossy with a qualitatively better loss than the best possible approximation ratio of polynomial time approximation algorithms, then one can obtain kernels where the number of elements is linear for every fixed d. Further, based on this, we present our main result: we show that there exist approximate Turing kernelizations for d-Hitting Set that even beat the established bit-size lower bounds for exact kernelizations - in fact, we use a constant number of oracle calls, each with "near linear" (𝒪(k^{1+ε})) bit size, that is, almost the best one could hope for. Lastly, for two special cases of implicit 3-Hitting set, namely, FVST and CVD, we obtain the "best of both worlds" type of results - (1+ε)-approximate kernelizations with a linear number of vertices. In terms of size, this substantially improves the exact kernels of Fomin et al. [SODA 2018, TALG 2019], with simpler arguments.

For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as parameterization has led to a long and successful line of research. Recently, however, there has been an extensive study of structural parameters that are potentially much smaller than the modulator size. In particular, recent papers [Jansen et al. STOC 2021; Agrawal et al. SODA 2022] have studied parameterization by the size of the modulator to a graph family $\mathcal{H}$ ($\textbf{mod}_{\mathcal{H}}$), elimination distance to $\mathcal{H}$ ($\textbf{ed}_{\mathcal{H}}$), and $\mathcal{H}$-treewidth ($\textbf{tw}_{\mathcal{H}}$). While these new parameters have been successfully exploited to design fast exact algorithms their utility (especially that of latter two) in the context of approximation algorithms is mostly unexplored. The conceptual contribution of this paper is to present novel algorithmic meta-theorems that expand the impact of these structural parameters to the area of FPT Approximation, mirroring their utility in the design of exact FPT algorithms. Precisely, we show that if a covering or packing problem is definable in Monadic Second Order Logic and has a property called Finite Integer Index, then the existence of an FPT Approximation Scheme (FPT-AS, i.e., ($1\pm ε$)-approximation) parameterized these three parameters is in fact equivalent. As concrete exemplifications of our meta-theorems, we obtain FPT-ASes for well-studied graph problems such as Vertex Cover, Feedback Vertex Set, Cycle Packing and Dominating Set, parameterized by these three parameters.

Given an edge-weighted graph, how many minimum $k$-cuts can it have? This is a fundamental question in the intersection of algorithms, extremal combinatorics, and graph theory. It is particularly interesting in that the best known bounds are algorithmic: they stem from algorithms that compute the minimum $k$-cut. In 1994, Karger and Stein obtained a randomized contraction algorithm that finds a minimum $k$-cut in $O(n^{(2-o(1))k})$ time. It can also enumerate all such $k$-cuts in the same running time, establishing a corresponding extremal bound of $O(n^{(2-o(1))k})$. Since then, the algorithmic side of the minimum $k$-cut problem has seen much progress, leading to a deterministic algorithm based on a tree packing result of Thorup, which enumerates all minimum $k$-cuts in the same asymptotic running time, and gives an alternate proof of the $O(n^{(2-o(1))k})$ bound. However, beating the Karger--Stein bound, even for computing a single minimum $k$-cut, has remained out of reach. In this paper, we give an algorithm to enumerate all minimum $k$-cuts in $O(n^{(1.981+o(1))k})$ time, breaking the algorithmic and extremal barriers for enumerating minimum $k$-cuts. To obtain our result, we combine ideas from both the Karger--Stein and Thorup results, and draw a novel connection between minimum $k$-cut and extremal set theory. In particular, we give and use tighter bounds on the size of set systems with bounded dual VC-dimension, which may be of independent interest.

For any fixed positive integer r and a given budget k, the r-Eigenvalue Vertex Deletion (r-EVD) problem asks if a graph G admits a subset S of at most k vertices such that the adjacency matrix of G⧵S has at most r distinct eigenvalues. The edge deletion, edge addition, and edge editing variants are defined analogously. For r = 1, r-EVD is equivalent to the Vertex Cover problem. For r = 2, it turns out that r-EVD amounts to removing a subset S of at most k vertices so that G⧵ S is a cluster graph where all connected components have the same size. We show that r-EVD is NP-complete even on bipartite graphs with maximum degree four for every fixed r > 2, and FPT when parameterized by the solution size and the maximum degree of the graph. We also establish several results for the special case when r = 2. For the vertex deletion variant, we show that 2-EVD is NP-complete even on triangle-free and 3d-regular graphs for any d ≥ 2, and also NP-complete on d-regular graphs for any d ≥ 8. The edge deletion, addition, and editing variants are all NP-complete for r = 2. The edge deletion problem admits a polynomial time algorithm if the input is a cluster graph, while - in contrast - the edge addition variant is hard even when the input is a cluster graph. We show that the edge addition variant has a quadratic kernel. The edge deletion and vertex deletion variants admit a single-exponential FPT algorithm when parameterized by the solution size alone. Our main contribution is to develop the complexity landscape for the problem of modifying a graph with the aim of reducing the number of distinct eigenvalues in the spectrum of its adjacency matrix. It turns out that this captures, apart from Vertex Cover, also a natural variation of the problem of modifying to a cluster graph as a special case, which we believe may be of independent interest.

Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a \emph{fair} version of \textsc{Hitting Set}. In the classical \textsc{Hitting Set} problem, the input is a universe $\mathcal{U}$, a family $\mathcal{F}$ of subsets of $\mathcal{U}$, and a non-negative integer $k$. The goal is to determine whether there exists a subset $S \subseteq \mathcal{U}$ of size $k$ that \emph{hits} (i.e., intersects) every set in $\mathcal{F}$. Inspired by several recent works, we formulate a fair version of this problem, as follows. The input additionally contains a family $\mathcal{B}$ of subsets of $\mathcal{U}$, where each subset in $\mathcal{B}$ can be thought of as the group of elements of the same \emph{type}. We want to find a set $S \subseteq \mathcal{U}$ of size $k$ that (i) hits all sets of $\mathcal{F}$, and (ii) does not contain \emph{too many} elements of each type. We call this problem \textsc{Fair Hitting Set}, and chart out its tractability boundary from both classical as well as multivariate perspective. Our results use a multitude of techniques from parameterized complexity including classical to advanced tools, such as, methods of representative sets for matroids, FO model checking, and a generalization of best known kernels for \textsc{Hitting Set}.

MAX-SAT with cardinality constraint (CC-MAX-SAT) is one of the classical NP-complete problems, that generalizes MAXIMUM COVERAGE, PARTIAL VERTEX COYER, MAX-2-SAT with bisection constraints, and has been extensively studied across all algorithmic paradigms. In this problem, we are given a CNF-formula Φ, and a positive integer k, and the goal is to find an assignment β with at most k variables set to true (also called a weight k-assignment) such that the number of clauses satisfied by β is maximized. The problem is known to admit an approximation algorithm with factor , which is probably optimal. In fact, the problem is hard to approximate within 0.944, assuming Unique Games Conjecture, even when the input formula is 2-CNF. Furthermore, assuming Gap-Exponential Time Hypothesis (Gap-ETH), for any ε > 0 and any function h, no h(k)(n + m)o(k) time algorithm can approximate MAXIMUM COVERAGE (a monotone version of CC-MAX-SAT) with n elements and m sets to within a factor , even with a promise that there exist k sets that fully cover the whole universe. These intractable results lead us to explore families of formula, where we can circumvent these barriers. Towards this we consider Kd,d-free formulas (that is, the clause-variable incidence bipartite graph of the formula excludes Kd,d as an induced subgraph). We show that for every ε > 0, there exists an algorithm for CC-MAX-SAT on Kd,d-free formulas with approximation ratio (1 — ε) and running in time (these algorithms are called FPT-AS). For, MAXIMUM COVERAGE on Kd,d-free set families, we obtain FPT-AS with running time . Our second result considers “optimizing k”, with fixed covering constraint for the Maximum Coverage problem. To explain our result, we first recast the MAXIMUM COVERAGE problem as the MAX RED BLUE DOMINATING SET WITH COVERING CONSTRAINT problem. Here, input is a bipartite graph G = (A, B, E), a positive integer t, and the objective is to find a minimum sized subset S ⊆ A, such that |N(S)| (the size of the set of neighbors of S) is at least t. We design an additive approximation algorithm for MAX RED BLUE DOMINATING SET WITH COVERING CONSTRAINT, on Kd,d-free bipartite graphs, running in FPT time. In particular, if k denotes the minimum size of S ⊆ A, such that |N(S)| ≥ t, then our algorithm runs in time (kd)O(kd)nO(1) and returns a set S' such that |N(S')| ≥ t and |S'| ≤ k +1. This is in sharp contrast to the fact that, even a special case of our problem, namely, the PARTIAL VERTEX COVER problem (or MAX k-VC) is W[1]-hard, parameterized by k. Thus, we get the best possible parameterized approximation algorithm for the MAXIMUM COVERAGE problem on Kd,d-free bipartite graphs. * Pallavi Jain is supported by Seed Grant (IITJ/R&D/2022-23/07) and SERB-SUPRA Grant(SPR/2021/000860). Lawqueen Kanesh is supported by EPSRC Standard Research Grant (EP/V044621/1). Saket Saurabh is supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 819416); and he also acknowledges the support of Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

We initiate a systematic study of approximation schemes for fundamental optimization problems on disk graphs, a common generalization of both planar graphs and unit-disk graphs. Our main contribution is a general framework for designing efficient polynomial-time approximation schemes (EPTASes) for vertex- deletion problems on disk graphs, which results in EPTASes for many fundamental problems including VERTEX COVER, FEEDBACK VERTEX SET, SMALL CYCLE HITTING (in particular, TRIANGLE HITTING), Pk-VERTEX DELETION for k ∈ {3,4,5}, PATH DELETION, PATHWIDTH 1-DELETION, COMPONENT ORDER CONNECTIVITY, BOUNDED DEGREE DELETION, PSEUDOFOREST DELETION, FINITE-TYPE COMPONENT DELETION, etc. All EPTASes obtained using our framework are robust in the sense that they do not require a realization of the input disk graph (in fact, we allow the input to be any graph, and our algorithms either output a correct approximation solution for the problem or conclude that the input graph is not a disk graph). To the best of our knowledge, prior to this work, the only problems known to admit PTASes or EPTASes on disk graphs are MAXIMUM CLIQUE, INDEPENDENT SET, DOMINATING SET, and VERTEX COVER, among which the existing PTAS [Erlebach et al., SICOMP'05] and EPTAS [Leeuwen, SWAT'06] for VERTEX COVER require a realization of the input disk graph (while ours does not). The core of our framework is a reduction for a broad class of (approximation) vertex-deletion problems from (general) disk graphs to disk graphs of bounded local radius, which is a new invariant of disk graphs introduced in this work. Disk graphs of bounded local radius can be viewed as a “mild” generalization of planar graphs, which preserves certain nice properties of planar graphs. Specifically, we prove that disk graphs of bounded local radius admit the Excluded Grid Minor property and have locally bounded treewidth. This allows existing techniques for designing approximation schemes on planar graphs (e.g., bidimensionality and Baker's technique) to be directly applied to disk graphs of bounded local radius. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.02717

Abstract 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.

Clustering with outliers is one of the most fundamental problems in Computer Science. Given a set X of n points and two numbers k, m, the clustering with outliers aims to exclude m points from X and partition the remaining points into k clusters that minimizes a certain cost function. In this paper, we give a general approach for solving clustering with outliers, which results in a fixed-parameter tractable (FPT) algorithm in k and m—i.e., an algorithm with running time of the form f(k, m) · nO(1) for some function f—that almost matches the approximation ratio for its outlier-free counterpart. As a corollary, we obtain FPT approximation algorithms with optimal approximation ratios for k-Median and k-Means with outliers in general and Euclidean metrics. We also exhibit more applications of our approach to other variants of the problem that impose additional constraints on the clustering, such as fairness or matroid constraints.

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 distG(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 2O(k)⋅nO(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 In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that $$\mathcal {O}(f(k) \log ^{\mathcal {O}(1)} n)$$ 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 $$\Omega (n)$$ Ω ( 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 $$\mathcal{F}$$ 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 $$\mathcal{F}$$ F -Subgraph Deletion and $$\mathcal{F}$$ F -Minor Deletion.

Abstract. For a positive integer [Formula: see text], a graph [Formula: see text] is said to be [Formula: see text]-closed if every pair of nonadjacent vertices in [Formula: see text] have at most [Formula: see text] neighbors in common. The closure of a graph [Formula: see text], denoted by [Formula: see text], is the least positive integer [Formula: see text] for which [Formula: see text] is [Formula: see text]-closed. The class of [Formula: see text]-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 [Formula: see text] 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 [Formula: see text] or by [Formula: see text] for each fixed value of [Formula: see text]. Here, [Formula: see text] is the solution size and [Formula: see text]. 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 [Formula: see text]-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 [Formula: see text], whereas Partial Dominating Set, parameterized by [Formula: see text] is [Formula: see text]-hard even when [Formula: see text]. We also show that for each fixed [Formula: see text], Perfect Code admits a polynomial kernel on the class of [Formula: see text]-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs unless NP [Formula: see text] co- NP /poly.

Given a graph G and an integer k , the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S ⊆ V ( G ) of size at most k such that G-S is an interval graph. This problem is known to be NP -complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10 k n O (1). The existence of a polynomial kernel for IVD remained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative.

Suppose we are given a pair of points $s, t$ and a set $S$ of $n$ geometric objects in the plane, called obstacles. We show that in polynomial time one can construct an auxiliary (multi-)graph $G$ with vertex set $S$ and every edge labeled from $\{0, 1\}$, such that a set $S_d \subseteq S$ of obstacles separates $s$ from $t$ if and only if $G[S_d]$ contains a cycle whose sum of labels is odd. Using this structural characterization of separating sets of obstacles we obtain the following algorithmic results. In the Obstacle-Removal problem the task is to find a curve in the plane connecting s to t intersecting at most q obstacles. We give a $2.3146^qn^{O(1)}$ algorithm for Obstacle-Removal, significantly improving upon the previously best known $q^{O(q^3)} n^{O(1)}$ algorithm of Eiben and Lokshtanov (SoCG'20). We also obtain an alternative proof of a constant factor approximation algorithm for Obstacle-Removal, substantially simplifying the arguments of Kumar et al. (SODA'21). In the Generalized Points-Separation problem, the input consists of the set S of obstacles, a point set A of k points and p pairs $(s_1, t_1),... (s_p, t_p)$ of points from A. The task is to find a minimum subset $S_r \subseteq S$ such that for every $i$, every curve from $s_i$ to $t_i$ intersects at least one obstacle in $S_r$. We obtain $2^{O(p)} n^{O(k)}$-time algorithm for Generalized Points-Separation problem. This resolves an open problem of Cabello and Giannopoulos (SoCG'13), who asked about the existence of such an algorithm for the special case where $(s_1, t_1), ... (s_p, t_p)$ contains all the pairs of points in A. Finally, we improve the running time of our algorithm to $f(p,k) n^{O(\sqrt{k})}$ when the obstacles are unit disks, where $f(p,k) = 2^O(p) k^{O(k)}$, and show that, assuming the Exponential Time Hypothesis (ETH), the running time dependence on $k$ of our algorithms is essentially optimal.

The Delaunay graph of a point set P ⊆ ℝ² is the plane graph with the vertex-set P and the edge-set that contains {p,p'} if there exists a disc whose intersection with P is exactly {p,p'}. Accordingly, a triangulated graph G is Delaunay realizable if there exists a triangulation of the Delaunay graph of some P ⊆ ℝ², called a Delaunay triangulation of P, that is isomorphic to G. The objective of Delaunay Realization is to compute a point set P ⊆ ℝ² that realizes a given graph G (if such a P exists). Known algorithms do not solve Delaunay Realization as they are non-constructive. Obtaining a constructive algorithm for Delaunay Realization was mentioned as an open problem by Hiroshima et al. [Hiroshima et al., 2000]. We design an n^𝒪(n)-time constructive algorithm for Delaunay Realization. In fact, our algorithm outputs sets of points with integer coordinates.

For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V(P) is connected. An s-t path P is non-disconnecting if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t.

The study of the Knot-Free Vertex Deletion problem emerges from its application in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph Q of a digraph D with at least two vertices is said to be a knot if there is no arc (u,v) of D with u ∈ V(Q) and v ∉ V(Q) (no-out neighbors of the vertices in Q). Given a directed graph D, the Knot-Free Vertex Deletion (KFVD) problem asks to compute a minimum-size subset S ⊂ V(D) such that D[V⧵S] contains no knots. There is no exact algorithm known for the KFVD problem in the literature that is faster than the trivial O^⋆(2ⁿ) brute-force algorithm. In this paper, we obtain the first non-trivial upper bound for KFVD by designing an exact algorithm running in time 𝒪^⋆(1.576ⁿ), where n is the size of the vertex set in D.

Vertex-deletion problems have been at the heart of parameterized complexity throughout its history. Here, the aim is to determine the minimum size (denoted by modℋ) of a modulator to a graph class ℋ, i.e., a set of vertices whose deletion results in a graph in ℋ. Recent years have seen the development of a research programme where the complexity of modulators is measured in ways other than size. For instance, for a graph class ℋ, the graph parameters elimination distance to ℋ (denoted by edℋ) [Bulian and Dawar, Algorithmica, 2016] and ℋ-treewidth (denoted by twℋ) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the “torso” of the graph induced on a modulator to the graph class ℋ. Here, the torso of a vertex set S in a graph G is the graph with vertex set S and an edge between two vertices u, v ∊ S if there is a path between u and v in G whose internal vertices all lie outside S. In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ℋ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ℋ satisfying mild additional conditions, with the exception of edℋ parameterized by twℋ, for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ℋ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing edℋ and twℋ. The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ℋ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a “strong irrelevant vertex rule”, then there exists a uniform FPT algorithm for edℋ. Using these sufficient conditions, we obtain uniform FPT algorithms for computing edℋ, when ℋ is defined by excluding a finite number of connected (a) minors, or (b) topological minors, or (c) induced subgraphs, or when ℋ is any of bipartite, chordal or interval graphs. For most of these problems, the existence of a uniform FPT algorithm has remained open in the literature. In fact, for some of them, even a non-uniform FPT algorithm was not known. For example, Jansen et al. [STOC 2021] ask for such an algorithm when ℋ is defined by excluding a finite number of connected topological minors. We resolve their question in the affirmative.

We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on H-minor free graphs. In particular, we obtain the following results (where k is the solution-size parameter). time algorithms for Edge Bipartization and Odd Cycle Transversal; a time algorithm for Edge Multiway Cut and a time algorithm for Vertex Multiway Cut (with undeletable terminals), where r is the number of terminals to be separated; a time algorithm for Edge Multicut and a time algorithm for Vertex Multicut (with undeletable terminals), where r is the number of terminal pairs to be separated; a time algorithm for Group Feedback Edge Set and a time algorithm for Group Feedback Vertex Set, where g is the size of the group. In addition, our approach also gives time algorithms for all above problems with the exception of time for Edge/Vertex Multicut and time for Group Feedback Edge/Vertex Set. All of our FPT algorithms (the first four items above) are randomized, as they use known randomized kernelization algorithms as sub-routines. We obtain our results by giving a new decomposition theorem on graphs of bounded genus, or more generally, an h-almost-embeddable graph for an arbitrary but fixed constant h. Our new decomposition theorem generalizes known Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010] and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. In particular we show the following. Let G be a graph of bounded genus, or more generally, an h-almost-embeddable graph for an arbitrary but fixed constant h. Then for every p ∊ ℕ, there exist disjoint sets Z1, …, Zp ⊆ V(G) such that for every i ∊ {1, …, p} and every Z′ ⊆ Zi, the treewidth of G/(Zi\Z′) is upper bounded by O(p + |Z′|), where the constant hidden in O(·) depends on h. Here G/(Zi\Z′) denotes the graph obtained from G by contracting every edge with both endpoints in Zi\Z′. When Z′ = , this corresponds to classical Contraction Decomposition Theorem.

One of the most celebrated results in Parameterized Complexity is the Bidimensionality theory of Demaine et al. [J. ACM, 2005], which has yielded, over the past two decades, numerous subexponential-time fixed-parameter tractable (FPT) algorithms for various problems on planar (and H-minor-free) graphs. At the heart of this theory is the proof of sublinear bounds in terms of solution size on the treewidth of a given graph. Inspired by this theory, in recent years, significant efforts have been devoted to design subexponential-time FPT algorithms for problems on geometric graph classes that utilize new treewidth bounds, in particular (but not only) for unit disk graphs [Fomin et al., SODA'12; Fomin et al., DCG'19; Panolan et al., SODA'19; Fomin et al. SoCG'20]. In this paper, we aim to attain such results on disk graphs, a broad class of graphs that generalizes both the classes of planar graphs and unit disk graphs, and thereby unify the aforementioned research frontiers for planar and unit disk graphs. Our main contribution is an approach to design subexponential-time FPT algorithms for problems on disk graphs, which we apply to several well-studied graph problems. At the heart of our approach lie two new combinatorial theorems concerning the treewidth of disk graphs having a realization of bounded ply (or maximum clique size) that are of independent interest. In particular, we prove a stronger version of the following treewidth bound: Let G be a disk graph that has some realization of ply p and no false twins, and M ⊆ V(G) such that G has no triangle with exactly one vertex from M, and G–M has treewidth w. Then, the treewidth of G is . Among our applications are the first subexponential-time FPT algorithms for several problems on disk graphs, including Triangle Hitting, Feedback Vertex Set and Odd Cycle Transversal (OCT). Previously, subexponential-time FPT algorithms for these problems were only known on planar graphs and unit disk graphs (excluding OCT, which was only known to admit such an algorithm on planar graphs). Our algorithms are robust, in particular, they do not require a geometric realization of the input graph (for all aforementioned problems), and they generalize to the weighted and counting versions of all aforementioned problems except for OCT.

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 (where dist_G(s,t) denotes the length of a shortest path from s to t). Bez\'akov\'a et al. proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2^{O (k)} n. Further, they left the parameterized complexity of the problem on directed graphs open. 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. Further, 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 (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path Above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path Above Diameter is NP-complete even for k=1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path Above Diameter is solvable in polynomial time for each k\in{1,\dots, 4} and is NP-complete for every k\geq 5. The parameterized complexity of Longest Path Above Diameter on general directed graphs remains an interesting open problem.

Finding large cliques or cliques missing a few edges is a fundamental algorithmic task in the study of real-world graphs, with applications in community detection, pattern recognition, and clustering. A number of effective backtracking-based heuristics for these problems have emerged from recent empirical work in social network analysis. Given the NP-hardness of variants of clique counting, these results raise a challenge for beyond worst-case analysis of these problems. Inspired by the triadic closure of real-world graphs, Fox et al. (SICOMP 2020) introduced the notion of $c$-closed graphs and proved that maximal clique enumeration is fixed-parameter tractable with respect to $c$. In practice, due to noise in data, one wishes to actually discover "near-cliques", which can be characterized as cliques with a sparse subgraph removed. In this work, we prove that many different kinds of maximal near-cliques can be enumerated in polynomial time (and FPT in $c$) for $c$-closed graphs. We study various established notions of such substructures, including $k$-plexes, complements of bounded-degeneracy and bounded-treewidth graphs. Interestingly, our algorithms follow relatively simple backtracking procedures, analogous to what is done in practice. Our results underscore the significance of the $c$-closed graph class for theoretical understanding of social network analysis.

We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph H as a minor can be solved by an algorithm working in time f(H)· nO(1), where f is some function. In other words, we show that these problems are fixed-parameter tractable when parameterized by the size of the excluded minor, with the caveat that the bound on the running time is not necessarily computable. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given H-minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable H-minor-free graphs, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth.

Abstract We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance between any two vertices in H is at most t times the distance between these vertices in G, that is, H keeps the distances in G up to the distortion (or stretch) factor t. An additive t-spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter t, that is, the distances in H and G differ by at most t. The task of Directed Multiplicative Spanner is, given a directed graph G with m arcs and positive integers t and k, decide whether G has a multiplicative t-spanner with at most $$m-k$$ m - k arcs. Similarly, Directed Additive Spanner asks whether G has an additive t-spanner with at most $$m-k$$ m - k arcs. We show that (i) Directed Multiplicative Spanner admits a polynomial kernel of size $$\mathcal {O}(k^4t^5)$$ O ( k 4 t 5 ) and can be solved in randomized $$(4t)^k\cdot n^{\mathcal {O}(1)}$$ ( 4 t ) k · n O ( 1 ) time, (ii) the weighted variant of Directed Multiplicative Spanner can be solved in $$k^{2k}\cdot n^{\mathcal {O}(1)}$$ k 2 k · n O ( 1 ) time on directed acyclic graphs, (iii) Directed Additive Spanner is $${{\,\mathrm{\mathsf{W}}\,}}[1]$$ W [ 1 ] -hard when parameterized by k for every fixed $$t\ge 1$$ t ≥ 1 even when the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is $${{\,\mathrm{\mathsf{FPT}}\,}}$$ FPT when parameterized by t and k.

Abstract. We prove the following theorem. Given a planar graph [Formula: see text] and an integer [Formula: see text], it is possible in polynomial time to randomly sample a subset [Formula: see text] of vertices of [Formula: see text] with the following properties: [Formula: see text] induces a subgraph of [Formula: see text] of treewidth [Formula: see text], and for every connected subgraph [Formula: see text] of [Formula: see text] on at most [Formula: see text] vertices, the probability that [Formula: see text] covers the whole vertex set of [Formula: see text] is at least [Formula: see text], where [Formula: see text] is the number of vertices of [Formula: see text]. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, usually with running time bound [Formula: see text]. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed [Formula: see text]-Path, Weighted [Formula: see text]-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems could be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [ Algorithmica, 75 (2016), pp. 363--382] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most $k$ to any minor-closed class of graphs is fixed-parameter tractable parameterized by $k$ [ Algorithmica, 79 (2017), pp. 139--158]. They showed that graph isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr, Siebertz, and Vigny [MFCS 2020, LIPIcs Leibniz Int. Proc. Inform. 170, Wadern Germany, 2020, 65] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to $K_5$-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.

Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization versions of this problem are the Sex-Equal Stable Marriage (SESMI), Balanced Stable Marriage (BSMI), max-Stable Marriage with Ties (max-SMTI), and min-Stable Marriage with Ties (min-SMTI) problems. In this paper, we analyze these problems from the viewpoint of parameterized complexity. We conduct the first study of these problems in particular, and of problems related to Stable Marriage in general, with respect to the parameter treewidth. The motivation behind the choice of treewidth is threefold. First, several problems in social choice theory have already been studied with respect to treewidth. The networks relevant to these problems (say, social networks) are clearly also relevant to Stable Marriage. Thus, the motivation underlying these studies directly extends to our study. Second, empirical studies of the treewidth of several types of networks relevant to Stable Marriage have also already been undertaken, identifying that some of these networks indeed have a treelike structure. Third, treewidth is the most well studied structural parameter in parameterized complexity. We design optimal parameterized algorithms for all four problems under the treewidth of both their primal graphs and rotation digraphs. First, we study the treewidth ${\mathtt{tw}}$ of the primal graph. We establish that all four problems are W[1]-hard. In particular, while it is easy to show that all four problems admit algorithms that run in time $n^{{\mathcal{O}}({\mathtt{tw}})}$, we prove that unless the exponential-time hypothesis is false, all of these algorithms are optimal. Next, we study the treewidth ${\mathtt{tw}}$ of the rotation digraph. In this context, max-SMTI and min-SMTI are not defined. For both SESMI and BSMI, we design (highly nontrivial) algorithms that run in time $2^{{\mathtt{tw}}}n^{{\mathcal{O}}(1)}$. Then, for both SESMI and BSMI, we prove that unless the strong exponential-time hypothesis is false, algorithms that run in time $(2-\epsilon)^{{\mathtt{tw}}}n^{{\mathcal{O}}(1)}$ do not exist for any fixed $\epsilon>0$. We thus present a comprehensive, complete picture of the behavior of Stable Marriage with respect to treewidth.

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.

De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexponential algorithms on geometric graphs with tight (up to ETH) running times. This framework is based on dynamic programming on graphs of weighted treewidth resulting in algorithms that use super-polynomial space. We introduce the notion of weighted treedepth and use it to refine the framework of de Berg et al. for obtaining polynomial space (with tight running times) on geometric graphs. As a result, we prove that for any fixed dimension $d \ge 2$ on intersection graphs of similarly-sized fat objects many well-known graph problems including Independent Set, $r$-Dominating Set for constant $r$, Cycle Cover, Hamiltonian Cycle, Hamiltonian Path, Steiner Tree, Connected Vertex Cover, Feedback Vertex Set, and (Connected) Odd Cycle Transversal are solvable in time $2^{O(n^{1-1/d})}$ and within polynomial space.

In the Multi-Team Formation problem, we are given a ground set C of n candidates, each of which is characterized by a d-dimensional attribute vector in ℝ^d, and two positive integers α and β satisfying α β ≤ n. The goal is to form α disjoint teams T₁,...,T_α ⊆ C, each of which consists of β candidates in C, such that the total score of the teams is maximized, where the score of a team T is the sum of the h_j maximum values of the j-th attributes of the candidates in T, for all j ∈ {1,...,d}. Our main result is an 2^{2^O(d)} n^O(1)-time algorithm for Multi-Team Formation. This bound is ETH-tight since a 2^{2^{d/c}} n^O(1)-time algorithm for any constant c > 12 can be shown to violate the Exponential Time Hypothesis (ETH). Our algorithm runs in polynomial time for all dimensions up to d = clog log n for a sufficiently small constant c > 0. Prior to our work, the existence of a polynomial time algorithm was an open problem even for d = 3.

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 committee of size k, based on these given voter preferences. In this paper we consider several utilitarian and egailitarian OWA (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, 2013], which gave a O(n^n) algorithm for computing winner under the Chamberlin Courant rule (CC), 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.

For a family of graphs F, given a graph G and an integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in the family F. The F-Deletion problems for all non-trivial families F that satisfy the hereditary property on induced subgraphs are known to be NP-hard by a result of Yannakakis (STOC'78). Ptolemaic graphs are the graphs that satisfy the Ptolemy inequality, and they are the intersection of chordal graphs and distance-hereditary graphs. Equivalently, they form the set of graphs that do not contain any chordless cycles or a gem as an induced subgraph. (A gem is the graph on 5 vertices, where four vertices form an induced path, and the fifth vertex is adjacent to all the vertices of this induced path.) The Ptolemaic Deletion problem is the F-Deletion problem, where F is the family of Ptolemaic graphs. In this paper we study Ptolemaic Deletion from the viewpoint of Kernelization Complexity, and obtain a kernel with 𝒪(k⁶) vertices for the problem.

Augmenting an undirected or a directed graph (digraph) by adding new edges or arcs, to increase its connectivity to a target value, is a fundamental problem in combinatorial optimization and graph theory. In this paper we study the basic problem of augmenting an input digraph to make it strongly connected, which is known as the Strong Connectivity Augmentation problem. Here, the input is a digraph D = (V, A), a set of links L ⊆ V × V, and a positive integer k. The objective is to decide if there exists a subset F ⊆ L, of size at most k, such that D′ = (V, A ∪ F) is strongly connected. We consider the general version of this problem where, additionally, there is a weight function w : L → ℝ+ on the links, and the goal is to find a minimum weight subset F ⊆ L of cardinality at most k, such that D′ = (V, A ∪ F) is strongly connected. We design an algorithm for this problem that runs in time 2(k log k) n(1), thereby showing that it is fixed parameter tractable (FPT). Here, n = |V|. This also resolves an open problem stated by Guo and Uhlmann more than a decade ago [Networks 56(2): 131–142 (2010)].

Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and well-studied problem arising naturally in computational geometry, graph theory (under the names Min-Color Path and Minimum Label Path), wireless sensor networks (Barrier Resilience) and motion planning (Minimum Constraint Removal). It remains NP-hard even for very simple-shaped obstacles such as unit-length line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al., CGTA, 2020]. We also obtain a constant factor approximation for the Minimum Color Prize Collecting Steiner Forest where the goal is to connect multiple request pairs (s1, t1), …, (sk, tk) while minimizing the number of obstacles touched by any (si, ti) path plus a fixed cost of wi for each pair (si, ti) left disconnected. This generalizes the classic Steiner Forest and Prize-Collecting Steiner Forest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for Min-Color Path even on planar graphs since the problem is known to be APX-hard [Eiben and Kanj, TALG, 2020]. Additionally, we show that generalizations of the problem to disconnected obstacles in the plane or connected obstacles in higher dimensions are strongly inapproximable assuming some well-known hardness conjectures.

Over the past decade, many results have focused on the design of parameterized approximation algorithms for W[1]-hard problems. However, there are fundamental problems within the class FPT for which the best known algorithms have seen no progress over the course of the decade; some of them have even been proved not to admit algorithms that run in time 2(k) n(1) under the Exponential Time Hypothesis (ETH) or (c – ∊)k n(1) under the Strong ETH (SETH). In this paper, we expand the study of FPT-approximation and initiate a systematic study of FPT-approximation for problems that are FPT. We design FPT-approximation algorithms for problems that are FPT, with running times that are significantly faster than the corresponding best known FPT-algorithm, and while achieving approximation ratios that are significantly better than what is possible in polynomial time. We present a general scheme to design 2(k) n(1)-time 2-approximation algorithms for cut problems. In particular, we exemplify it for Directed Feedback Vertex Set, Directed Subset Feedback Vertex Set, Directed Odd Cycle Transversal and Undirected Multicut. Further, we extend our scheme to obtain FPT-time (1)-approximation algorithms for weighted cut problems, where the objective is to obtain a solution of size at most k and of minimum weight. Here, we present two approaches. The first approach achieves 2(k) n(1)-time constant-factor approximation, which we exemplify for all problems mentioned in the first bullet. The other leads to an FPT-approximation Scheme (FPT-AS) for Weighted Directed Feedback Vertex Set. Additionally, we present a combinatorial lemma that yields a partition of the vertex set of a graph to roughly equal sized sets so that the removal of each set reduces its treewidth substantially, which may be of independent interest. For several graph problems, use this lemma to design cwn(1)-time (1 + ∊)-approximation algorithms that are faster than known SETH lower bounds, where w is the treewidth of the input graph. Examples of such problems include Vertex Cover, Component Order Connectivity, Bounded-Degree Vertex Deletion and ℱ-Packing for any family ℱ of bounded sized graphs. Lastly, we present a general reduction of problems parameterized by treewidth to their versions parameterized by solution size. Combined with our first scheme, we exemplify it to obtain cwn(1)-time bicriteria approximation algorithms for all problems mentioned in the first bullet.

In this paper we prove an analogue of the classic Bollobás lemma for approximate counting. In fact, we match an analogous result of Fomin et al. [JACM 2016] for decision. This immediately yields, for a number of fundamental problems, parameterized approximate counting algorithms with the same running times as what is obtained for the decision variant using the representative family technique of Fomin et al. [JACM 2016]. For example, we devise an algorithm for approximately counting (a factor (1 ± ∊) approximation algorithm) k-paths in an n-vertex directed graph (#k-Path) running in time (n + m)). This improves over an earlier algorithm of Brand et al. [STOC 2018] that runs in time . Additionally, we obtain an approximate counting analogue of the efficient computation of representative families for product families of Fomin et al. [TALG 2017], again essentially matching the running time for decision. This results in an algorithm with running time for computing a (1 + ∊) approximation of the sum of the coefficients of the multilinear monomials in a degree-k homogeneous n-variate polynomial encoded by a monotone circuit (#Multilinear Monomial Detection). When restricted to monotone circuits (rather than polynomials of non-negative coefficients), this improves upon an earlier algorithm of Pratt [FOCS 2019] that runs in time .

In the literature on parameterized graph problems, there has been an increased effort in recent years aimed at exploring novel notions of graph edit-distance that are more powerful than the size of a modulator to a specific graph class. In this line of research, Bulian and Dawar [Algorithmica, 2016] introduced the notion of elimination distance and showed that deciding whether a given graph has elimination distance at most k to any minor-closed class of graphs is fixed-parameter tractable parameterized by k [Algorithmica, 2017]. They showed that Graph Isomorphism parameterized by the elimination distance to bounded degree graphs is fixed-parameter tractable and asked whether determining the elimination distance to the class of bounded degree graphs is fixed-parameter tractable. Recently, Lindermayr et al. [MFCS 2020] obtained a fixed-parameter algorithm for this problem in the special case where the input is restricted to K₅-minor free graphs. In this paper, we answer the question of Bulian and Dawar in the affirmative for general graphs. In fact, we give a more general result capturing elimination distance to any graph class characterized by a finite set of graphs as forbidden induced subgraphs.

We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse Bases problem consists of a matroid M, a weight function ω:E(M)→N, and integers k ≥ 1, d ≥ 0. 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. This is a diverse variant of the classical matroid base packing problem. The input to the Weighted Diverse Common Independent Sets problem consists of two matroids M₁,M₂ defined on the same ground set E, a weight function ω:E→N, and integers k ≥ 1, d ≥ 0. The task is to decide if there is a collection of k common independent sets I_1, ..., I_k of M₁ and M₂ such that the weight of the symmetric difference of any pair of these sets is at least d. This is motivated by the classical weighted matroid intersection problem. The input to the Diverse Perfect Matchings problem consists of a graph G and integers k ≥ 1, d ≥ 0. 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. The underlying problem of finding one solution (basis, common independent set, or perfect matching) is known to be doable in polynomial time for each of these problems, and Diverse Perfect Matchings is known to be NP-hard for k = 2. We show that Weighted Diverse Bases and Weighted Diverse Common Independent Sets are both NP-hard. We show also that Diverse Perfect Matchings cannot be solved in polynomial time (unless P=NP) even for the case d = 1. We derive fixed-parameter tractable (FPT) algorithms for all three problems with (k,d) as the parameter. The above results on matroids are derived under the assumption that the input matroids are given as independence oracles. For Weighted Diverse Bases we present a polynomial-time algorithm that takes a representation of the input matroid over a finite field and computes a poly(k,d)-sized kernel for the problem.

Over the past few decades, the study of dense structures from the perspective of approximation algorithms has become a wide area of research. However, from the viewpoint of parameterized algorithm, this area is largely unexplored. In particular, properties of random samples have been successfully deployed to design approximation schemes for a number of fundamental problems on dense structures [Arora et al. FOCS 1995, Goldreich et al. FOCS 1996, Giotis and Guruswami SODA 2006, Karpinksi and Schudy STOC 2009]. In this paper, we fill this gap, and harness the power of random samples as well as structure theory to design kernelization as well as parameterized algorithms on dense structures. In particular, we obtain linear vertex kernels for Edge-Disjoint Paths, Edge Odd Cycle Transversal, Minimum Bisection, d-Way Cut, Multiway Cut and Multicut on everywhere dense graphs. In fact, these kernels are obtained by designing a polynomial-time algorithm when the corresponding parameter is at most Ω(n). Additionally, we obtain a cubic kernel for Vertex-Disjoint Paths on everywhere dense graphs. In addition to kernelization results, we obtain randomized subexponential-time parameterized algorithms for Edge Odd Cycle Transversal, Minimum Bisection, and d-Way Cut. Finally, we show how all of our results (as well as EPASes for these problems) can be de-randomized.

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\text {-}\textsc {Hitting Set}{}$$ that runs in time $$n^{{{\,\mathrm{O}\,}}{(d^2 + (d / \epsilon ))}}$$ , uses $${{\,\mathrm{O}\,}}{((d^2 + (d / \epsilon ))\log {n})}$$ bits of space, and achieves an approximation ratio of $${{\,\mathrm{O}\,}}{((d / \epsilon ) n^{\epsilon })}$$ for any positive $$\epsilon \le 1$$ and any $$d \in {\mathbb {N}}$$ . In particular, this yields a factor- $${{\,\mathrm{O}\,}}{(\log {n})}$$ approximation algorithm which runs in time $$n^{{{\,\mathrm{O}\,}}{(\log {n})}}$$ and uses $${{\,\mathrm{O}\,}}{(\log ^2{n})}$$ bits of space (for constant d). As a corollary, we obtain similar bounds for $$\textsc {Vertex Cover}{}$$ and several graph deletion problems. For bounded-multiplicity problem instances, one can do better. We devise a factor-2 approximation algorithm for $$\textsc {Vertex Cover}{}$$ on graphs with maximum degree $$\varDelta$$ , and an algorithm for computing maximal independent sets, both of which run in time $$n^{{{\,\mathrm{O}\,}}{(\varDelta )}}$$ and use $${{\,\mathrm{O}\,}}{(\varDelta \log {n})}$$ bits of space. For the more general $$d\text {-}\textsc {Hitting Set}{}$$ problem, we devise a factor-d approximation algorithm which runs in time $$n^{{{\,\mathrm{O}\,}}{(d{\delta }^2)}}$$ and uses $${{\,\mathrm{O}\,}}{(d {\delta }^2 \log {n})}$$ bits of space on set families where each element appears in at most $$\delta$$ sets. For $$\textsc {Independent Set}{}$$ restricted to graphs with average degree d, we give a factor-(2d) approximation algorithm which runs in polynomial time and uses $${{\,\mathrm{O}\,}}{(\log {n})}$$ bits of space. We also devise a factor- $${{\,\mathrm{O}\,}}{(d^2)}$$ approximation algorithm for $$\textsc {Dominating Set}{}$$ on d-degenerate graphs which runs in time $$n^{{{\,\mathrm{O}\,}}{(\log {n})}}$$ and uses $${{\,\mathrm{O}\,}}{(\log ^2{n})}$$ bits of space. For d-regular graphs, we show how a known randomized factor- $${{\,\mathrm{O}\,}}{(\log {d})}$$ approximation algorithm can be derandomized to run in time $$n^{{{\,\mathrm{O}\,}}{(1)}}$$ and use $${{\,\mathrm{O}\,}}{(\log n)}$$ bits of space. Our results use a combination of ideas from the theory of kernelization, distributed algorithms and randomized algorithms.

We show an algorithm that, given an n -vertex graph G and a parameter k , in time 2 O ( k log k ) n O (1) finds a tree decomposition of G with the following properties: — every adhesion of the tree decomposition is of size at most k , and — every bag of the tree decomposition is ( i , i )-unbreakable in G for every 1 ⩽ i ⩽ k . Here, a set X ⊆ V ( G ) is ( a , b )-unbreakable in G if for every separation ( A , B ) of order at most b in G , we have | A \cap X | ⩽ a or | B ∩ X | ⩽ a . The resulting tree decomposition has arguably best possible adhesion size bounds and unbreakability guarantees. Furthermore, the parametric factor in the running time bound is significantly smaller than in previous similar constructions. These improvements allow us to present parameterized algorithms for M INIMUM B ISECTION , S TEINER C UT , and S TEINER M ULTICUT with improved parameteric factor in the running time bound. The main technical insight is to adapt the notion of lean decompositions of Thomas and the subsequent construction algorithm of Bellenbaum and Diestel to the parameterized setting.

Recently, Brand et al. [STOC 2018] gave a randomized mathcal O(4 k m ε -2 -time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ε based on exterior algebra. Prior to our work, this has been the state-of-the-art. In this article, we revisit the algorithm by Alon and Gutner [IWPEC 2009, TALG 2010], and obtain the following results: • We present a deterministic 4 k + O (√ k (log k +log 2 ε -1 )) m -time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. • Additionally, we present a randomized 4 k +mathcal O(log k (log k +logε -1 )) m -time polynomial-space algorithm. Our algorithm is simple—we only make elementary use of the probabilistic method. Here, n and m are the number of vertices and the number of edges, respectively. Additionally, our approach extends to approximate counting of other patterns of small size (such as q -dimensional p -matchings).

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T − S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is a tournament T and a weight function w : V ( T ) → N, and the task is to find a feedback vertex set S in T minimizing w ( S ) = ∑ v∈S w ( v ). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this article, we give the first polynomial time factor 2-approximation algorithm for this problem. Assuming the Unique Games Conjecture, this is the best possible approximation ratio achievable in polynomial time.

The Art Gallery 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 Art Gallery, 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 Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsen et al., SoCG'17]. 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 ∃ℝ-complete [Abrahamsen et al., STOC'18]. 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 Center Workshop, 2016]: Is Art Gallery 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 Art Gallery, this case can also be viewed as the classic Dominating Set problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-Vertex Art Gallery is solvable in time r^O(r²)n^O(1). Furthermore, our approach extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.

We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2^{𝒪(√k)}(n+m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs cannot be solved in time 2^{o(√k)}(n+m)^𝒪(1) [de Berg et al., STOC 2018], hence our algorithm is optimal. Besides the 2^{𝒪(√k)}(n+m)^𝒪(1)-time algorithm for the (arguably) much simpler Vertex Cover problem by de Berg et al. [STOC 2018] (which easily follows from the existence of a 2k-vertex kernel for the problem), this is the only known ETH-optimal fixed-parameter tractable algorithm on UDGs. Previously, Long Path and Long Cycle on unit disk graphs were only known to be solvable in time 2^{𝒪(√klog k)}(n+m). This algorithm involved the introduction of a new type of a tree decomposition, entailing the design of a very tedious dynamic programming procedure. Our algorithm is substantially simpler: we completely avoid the use of this new type of tree decomposition. Instead, we use a marking procedure to reduce the problem to (a weighted version of) itself on a standard tree decomposition of width 𝒪(√k).

In the Min k-cut problem, input is an edge weighted graph G and an integer k, and the task is to partition the vertex set into k non-empty sets, such that the total weight of the edges with endpoints in different parts is minimized. When k is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta et al. [SODA 2018] initiated the study of FPT-approximation for the Min k-Cut problem and gave an 1.9997-approximation algorithm running in time 2O(k6)nO(1). Later, the same set of authors [FOCS 2018] designed an ( 1+ε)-approximation algorithm that runs in time (k/ε)O(k)nk+O(1), and a 1.81-approximation algorithm running in time 2O(k2)nO(1). More, recently, Kawarabayashi and Lin [SODA 2020] gave a (5/3+ε)-approximation for Min k-Cut running in time 2O(k2logk)nO(1). In this paper we give a parameterized approximation algorithm with best possible approximation guarantee, and best possible running time dependence on said guarantee (up to Exponential Time Hypothesis (ETH) and constants in the exponent). In particular, for every , the algorithm obtains a ( 1+ε)-approximate solution in time (k/ε)O(k)nO(1). The main ingredients of our algorithm are: a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time sO(k)nO(1)on unweighted (multi-) graphs. Here, s denotes the number of edges in a minimum k-cut. The latter two are of independent interest.

A feedback vertex set in a hypergraph H is a set of vertices S such that deleting S from H results in an acyclic hypergraph. Here, deleting a vertex means removing the vertex and all incident hyperedges, and a hypergraph is acyclic if its vertex-edge incidence graph is acyclic. We study the (parameterized complexity of) the Hypergraph Feedback Vertex Set (HFVS) problem: given as input a hypergraph H and an integer k, determine whether H has a feedback vertex set of size at most k. It is easy to see that this problem generalizes the classic Feedback Vertex Set (FVS) problem on graphs. Remarkably, despite the central role of FVS in parameterized algorithms and complexity, the parameterized complexity of a generalization of FVS to hypergraphs has not been studied previously. In this paper, we fill this void. Our main results are as follows - HFVS is W[2]-hard (as opposed to FVS, which is fixed parameter tractable). - If the input hypergraph is restricted to a linear hypergraph (no two hyperedges intersect in more than one vertex), HFVS admits a randomized algorithm with running time 2^{𝒪(k³log k)}n^{𝒪(1)}. - If the input hypergraph is restricted to a d-hypergraph (hyperedges have cardinality at most d), then HFVS admits a deterministic algorithm with running time d^{𝒪(k)}n^{𝒪(1)}. The algorithm for linear hypergraphs combines ideas from the randomized algorithm for FVS by Becker et al. [J. Artif. Intell. Res., 2000] with the branching algorithm for Point Line Cover by Langerman and Morin [Discrete & Computational Geometry, 2005].

In the Stable Marriage problem, when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are incomplete. In most real-life situations, where agents participate in the matching market voluntarily and submit their preferences, it is natural to assume that each agent wants to be matched to someone in his/her preference list as opposed to being unmatched. In light of the Rural Hospital Theorem, we have to relax the "no blocking pair" condition for stable matchings in order to match more agents. In this paper, we study the question of matching more agents with fewest possible blocking edges. In particular, the goal is to find a matching whose size exceeds that of a stable matching in the graph by at least t and has at most k blocking edges. We study this question in the realm of parameterized complexity with respect to several natural parameters, k,t,d, where d is the maximum length of a preference list. Unfortunately, the problem remains intractable even for the combined parameter k+t+d. Thus, we extend our study to the local search variant of this problem, in which we search for a matching that not only fulfills each of the above conditions but is "closest", in terms of its symmetric difference to the given stable matching, and obtain an FPT algorithm.

We prove that the Hadwiger number of an $n$-vertex graph $G$ (the maximum size of a clique minor in $G$) cannot be computed in time $n^{o(n)}$, unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Hadwiger number problem has a wider applicability. We use it to rule out the existence of $n^{o(n)}$-time algorithms (up to ETH) for a large class of computational problems concerning edge contractions in graphs.

In the Split Vertex Deletion (SVD) problem, the input is an n-vertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that G-S is a split graph (i.e., there is bipartition of V(G-S) = C ⊎ I such that C is a clique and I is an independent set in G-S). This problem is a special case of 5-Hitting Set and consequently, there is a simple factor 5-approximation algorithm for this. On the negative side, it is easy to show that the problem does not admit a polynomial time (2-δ)-approximation algorithm, for any fixed δ > 0, unless the Unique Games Conjecture fails. We start by giving a simple quasipolynomial time (n^O(log n)) factor 2-approximation algorithm for SVD using the notion of clique-independent set separating collection. Thus, on the one hand SVD admits a factor 2-approximation in quasipolynomial time, and on the other hand this approximation factor cannot be improved assuming UGC. It naturally leads to the following question: Can SVD be 2-approximated in polynomial time? In this work we almost close this gap and prove that for any ε > 0, there is a n^O(log 1/(ε))-time 2(1+ε)-approximation algorithm.

In the standard model of committee selection, we are given a set of ordinal votes over a set of candidates and a desired committee size, and the task is to select a committee that relates to the given votes. Motivated by possible interactions and dependencies between candidates, we study a generalization of committee selection in which the candidates are connected via a network and the task is to select a committee that relates to the given votes while also satisfy certain properties with respect to this candidate network. To accommodate certain correspondences to the voter preferences, we consider three standard voting rules (in particular, $k$-Borda, Chamberlin-Courant, and Gehrlein stability); to model different aspects of interactions and dependencies between candidates, we consider two graph properties (in particular, Independent Set and Connectivity). We study the parameterized complexity of the corresponding combinatorial problems and discuss certain implications of our algorithmic results.

Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (at most) k+g(I). Here, g(I) is usually a lower bound (resp. upper bound) on the maximum (resp. minimum) size of a solution. Since its introduction in 1999 for Max SAT and Max Cut (with g(I) being half the number of clauses and half the number of edges, respectively, in the input), analysis of parameterization above a guarantee has become a very active and fruitful topic of research. We highlight a multiplicative form of parameterization above a guarantee: Given an instance (I,k) of some (parameterized) problem Π with a guarantee g(I), decide whether I admits a solution of size at least (resp. at most) k ⋅ g(I). In particular, we study the Long Cycle problem with a multiplicative parameterization above the girth g(I) of the input graph, and provide a parameterized algorithm for this problem. Apart from being of independent interest, this exemplifies how parameterization above a multiplicative guarantee can arise naturally. We also show that, for any fixed constant ε>0, multiplicative parameterization above g(I)^(1+ε) of Long Cycle yields para-NP-hardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of algorithms for other problems parameterized multiplicatively above girth.

In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as fewest arcs/vertices as possible such that, after the failure of any set F of at most k ≥ 1 arcs, testing whether D-F has a certain property P is equivalent to testing whether H-F has that property. Here, reachability (or, more generally, distance preservation) is the most basic requirement to maintain to ensure that the network functions properly. Given a vertex s ∈ V(D), Baswana et al. [STOC'16] presented a construction of H with O(2^kn) arcs in time O(2^{k}nm) where n=|V(D)| and m= |E(D)| such that for any vertex v ∈ V(D): if there exists a path from s to v in D-F, then there also exists a path from s to v in H-F. Additionally, they gave a tight matching lower bound. While the question of the improvement of the dependency on k arises for special classes of digraphs, an arguably more basic research direction concerns the dependency on n (for reachability between a pair of vertices s,t ∈ V(D)) - which are the largest classes of digraphs where the dependency on n can be made sublinear, logarithmic or even constant? Already for the simple classes of directed paths and tournaments, Ω(n) arcs are mandatory. Nevertheless, we prove that "almost acyclicity" suffices to eliminate the dependency on n entirely for a broad class of dense digraphs called bounded independence digraphs. Also, the dependence in k is only a polynomial factor for this class of digraphs. In fact, our sparsification procedure extends to preserve parity-based reachability. Additionally, it finds notable applications in Kernelization: we prove that the classic Directed Feedback Arc Set (DFAS) problem as well as Directed Edge Odd Cycle Transversal (DEOCT) (which, in sharp contrast to DFAS, is W[1]-hard on general digraphs) admit polynomial kernels on bounded independence digraphs. In fact, for any p ∈ N, we can design a polynomial kernel for the problem of hitting all cycles of length ℓ where (ℓ mod p = 1). As a complementary result, we prove that DEOCT is NP-hard on tournaments by establishing a combinatorial identity between the minimum size of a feedback arc set and the minimum size of an edge odd cycle transversal. In passing, we also improve upon the running time of the sub-exponential FPT algorithm for DFAS in digraphs of bounded independence number given by Misra et at. [FSTTCS 2018], and give the first sub-exponential FPT algorithm for DEOCT in digraphs of bounded independence number.

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\subseteq V(G)$ of size at most $k$ such that $G-S$ is a forest. After a long line of improvement, recently, Li and Nederlof [SODA, 2020] designed a randomized algorithm for the problem running in time $\mathcal{O}^{\star}(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,\ell \in \mathbb{N}$, and the objective is to test whether there exists a vertex subset $S$ of size at most $k$, such that $G-S$ is $\ell$ edges away from a forest. In this paper, using the methodology of Li and Nederlof [SODA, 2020], we obtain the current fastest algorithms for all these problems. In particular we obtain following randomized algorithms. 1) Independent Feedback Vertex Set can be solved in time $\mathcal{O}^{\star}(2.7^k)$. 2) Pseudo Forest Deletion can be solved in time $\mathcal{O}^{\star}(2.85^k)$. 3) Almost Forest Deletion can be solved in $\mathcal{O}^{\star}(\min\{2.85^k \cdot 8.54^\ell,2.7^k \cdot 36.61^\ell,3^k \cdot 1.78^\ell\})$.

In the Maximum Degree Contraction problem, 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^𝒪(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)^(2k) ⋅ n^𝒪(1) = 2^𝒪(k log (k+d)) ⋅ n^𝒪(1), and remains NP-hard for every constant d ≥ 2 (Acta Informatica (2014)). We present a different FPT algorithm that runs in time 2^𝒪(dk) ⋅ n^𝒪(1). In particular, our algorithm runs in time 2^𝒪(k) ⋅ n^𝒪(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/poly.

For a fixed graph $H$, the $H$-free-editing problem asks whether we can modify a given graph $G$ by adding or deleting at most $k$ edges such that the resulting graph does not contain $H$ as an induced subgraph. The problem is known to be NP-complete for all fixed $H$ with at least $3$ vertices and it admits a $2^{O(k)}n^{O(1)}$ algorithm. Cai and Cai showed that the $H$-free-editing problem does not admit a polynomial kernel whenever $H$ or its complement is a path or a cycle with at least $4$ edges or a $3$-connected graph with at least $1$ edge missing. Their results suggest that if $H$ is not independent set or a clique, then $H$-free-editing admits polynomial kernels only for few small graphs $H$, unless $\textsf{coNP} \in \textsf{NP/poly}$. Therefore, resolving the kernelization of $H$-free-editing for small graphs $H$ plays a crucial role in obtaining a complete dichotomy for this problem. In this paper, we positively answer the question of compressibility for one of the last two unresolved graphs $H$ on $4$ vertices. Namely, we give the first polynomial kernel for paw-free editing with $O(k^{6})$vertices.

We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance between any two vertices in H is at most t times the distance between these vertices in G, that is, H keeps the distances in G up to the distortion (or stretch) factor t. An additive t-spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter t, that is, the distances in H and G differ by at most t. The task of Directed Multiplicative Spanner is, given a directed graph G with m arcs and positive integers t and k, decide whether G has a multiplicative t-spanner with at most m-k arcs. Similarly, Directed Additive Spanner asks whether G has an additive t-spanner with at most m-k arcs. We show that - Directed Multiplicative Spanner admits a polynomial kernel of size 𝒪(k⁴t⁵) and can be solved in randomized (4t)^k⋅ n^𝒪(1) time, - Directed Additive Spanner is W[1]-hard when parameterized by k even if t = 1 and the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is FPT when parameterized by t and k.

In this paper we study two classical cut problems, namely Multicut and Multiway Cut on chordal graphs and split graphs. In the Multicut problem, the input is a graph G, a collection of 𝓁 vertex pairs (s_i, t_i), i ∈ [𝓁], and a positive integer k and the goal is to decide if there exists a vertex subset S ⊆ V(G)⧵ {s_i,t_i : i ∈ [𝓁]} of size at most k such that for every vertex pair (s_i,t_i), s_i and t_i are in two different connected components of G-S. In Unrestricted Multicut, the solution S can possibly pick the vertices in the vertex pairs {(s_i,t_i): i ∈ [𝓁]}. An important special case of the Multicut problem is the Multiway Cut problem, where instead of vertex pairs, we are given a set T of terminal vertices, and the goal is to separate every pair of distinct vertices in T× T. The fixed parameter tractability (FPT) of these problems was a long-standing open problem and has been resolved fairly recently. Multicut and Multiway Cut now admit algorithms with running times 2^{{𝒪}(k³)}n^{{𝒪}(1)} and 2^k n^{{𝒪}(1)}, respectively. However, the kernelization complexity of both these problems is not fully resolved: while Multicut cannot admit a polynomial kernel under reasonable complexity assumptions, it is a well known open problem to construct a polynomial kernel for Multiway Cut. Towards designing faster FPT algorithms and polynomial kernels for the above mentioned problems, we study them on chordal and split graphs. In particular we obtain the following results. 1) Multicut on chordal graphs admits a polynomial kernel with {𝒪}(k³ 𝓁⁷) vertices. Multiway Cut on chordal graphs admits a polynomial kernel with {𝒪}(k^{13}) vertices. 2) Multicut on chordal graphs can be solved in time min {𝒪(2^{k} ⋅ (k³+𝓁) ⋅ (n+m)), 2^{𝒪(𝓁 log k)} ⋅ (n+m) + 𝓁 (n+m)}. Hence Multicut on chordal graphs parameterized by the number of terminals is in XP. 3) Multicut on split graphs can be solved in time min {𝒪(1.2738^k + kn+𝓁(n+m), 𝒪(2^{𝓁} ⋅ 𝓁 ⋅ (n+m))}. Unrestricted Multicut on split graphs can be solved in time 𝒪(4^{𝓁}⋅ 𝓁 ⋅ (n+m)).

Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the ℋ-SCC Deletion problem. Here, one is given a digraph D, an integer k and the objective is to decide whether there is a vertex set of size at most k whose deletion leaves a digraph where every strong component excludes graphs in the fixed finite family ℋ as (not necessarily induced) subgraphs. When ℋ comprises only the digraph with a single arc, then this problem is precisely DFVS. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if ℋ only contains rooted graphs or if ℋ contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the recent results of Göke et al. [CIAC 2019] for the 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion problems. Moreover, we design algorithms for the two above mentioned problems, whose running times are better and match with the best bounds for DFVS, without using the heavy machinery of shadow removal as is done by Göke et al. [CIAC 2019].

In this paper, we prove a new scaling lemma for vertex weighted minor free graphs that allows for a smooth trade-off between the weight of a vertex set S and the treewidth of G — S. More precisely, we show the following. There exists an algorithm that given an H-minor free graph G, a weight function w: V(G) → ℚ+ and integers t and s, runs in polynomial time, and outputs a subset S ⊆ V(G) of weight at most d log n · opt(G, w, t)/s such that the treewidth of G – S is at most c·st. Here, d and c are fixed constants that depend only on H, and opt(G, w, t) is the (unknown) minimum weight of a subset U ⊆ V(G) such that the treewidth of G – U is at most t. This lemma immediately yields the first polynomial-time approximation schemes (PTASes) for WEIGHTED Treewidth-η Vertex Deletion, for η > 2, on graphs of bounded genus and the first PTAS for Weighted Feedback vertex Set on H-minor free graphs. These results effortlessly generalize to include weighted edge deletion problems, to all Weighted Connected Planar -Deletion problems, and finally to quasi polynomial time approximation schemes (QPTASes) for all of these problems on H-minor free graphs. For most of these problems even constant factor approximation algorithms, even on planar graphs, were not previously known. Additionally, using the scaling lemma we subsume, simplify and extend the recent framework of Cohen-Addad et al. [STOC 2016] for turning constant factor approximation algorithms for “ubiquitous” problems into PTASes for the same problems on graphs of bounded genus. Specifically, we obtain PTASes for ubiquitous problems without the requirement of having a constant factor approximation. While the statement of the scaling lemma is inspired by an analogous lemma by Cohen-Addad et al. [STOC 2016] for edge contractions on weighted graphs of bounded genus, as well as a scaling lemma by Fomin et al. [SODA 2011] for unweighted graphs, the proof is entirely different. The proof detours via three different linear programming relaxations for the Weighted Treewidth-η Vertex Deletion problems and a strengthening of a recent rounding procedure of Bansal et al. [SODA 2017] enhanced by the classic Klein-Plotkin-Rao Theorem [STOC 1993].

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T – S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here the input is a tournament T and a weight function w: V(T) → ℕ and the task is to find a feedback vertex set S in T minimizing w(S) = ΣvϵSw(v). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this paper we give the first polynomial time factor 2 approximation algorithm for this problem. Assuming the Unique Games conjecture, this is the best possible approximation ratio achievable in polynomial time.

A directed odd cycle transversal of a directed graph (digraph) D is a vertex set S that intersects every odd directed cycle of D. In the Directed Odd Cycle Transversal (DOCT) problem, the input consists of a digraph D and an integer k. The objective is to determine whether there exists a directed odd cycle transversal of D of size at most k. In this paper, we settle the parameterized complexity of DOCT when parameterized by the solution size k by showing that DOCT does not admit an algorithm with running time unless FPT = W[1]. On the positive side, we give a factor 2 fixed-parameter approximation (FPT approximation) algorithm for the problem. More precisely, our algorithm takes as input D and k, runs in time , and either concludes that D does not have a directed odd cycle transversal of size at most k, or produces a solution of size at most 2k. Finally, assuming gap-ETH, we show that there exists an ϵ > 0 such that DOCT does not admit a factor (1 + ϵ) FPT-approximation algorithm.

In the Topological Minor Deletion (TM-Deletion) problem, the input consists of an undirected graph G, a family of undirected graphs F and an integer k. The task is to determine whether G contains a set of vertices S of size at most k, such that the graph G∖ S obtained from G by removing the vertices of S, contains no graph from F as a topological minor. We give an algorithm forTM-Deletion with running time f(h ⋆,k)· |V(G)|4. Here h ⋆ is the maximum size of a graph in F and f is a computable function of h ⋆ and k. This is the first fixed parameter tractable algorithm (FPT) for the problem. In fact, even for the restricted case of planar inputs the first FPT algorithm was found only recently by Golovach et al. [SODA 2020]. For this case we improve upon the algorithm of Golovach et al. [SODA 2020] by designing an FPT algorithm with explicit dependence on k and h ⋆.

In the Disjoint Paths problem, the input is an undirected graph G on n vertices and a set of k vertex pairs, {s i ,t i } i=1 k , and the task is to find k pairwise vertex-disjoint paths such that the i’th path connects s i to t i . In this paper, we give a parameterized algorithm with running time 2 O(k 2) n O(1) for Planar Disjoint Paths, the variant of the problem where the input graph is required to be planar. Our algorithm is based on the unique linkage/treewidth reduction theorem for planar graphs by Adler et al. [JCTB 2017], the algebraic co-homology based technique developed by Schrijver [SICOMP 1994] for Disjoint Paths on directed planar graphs, and one of the key combinatorial insights developed by Cygan et al. [FOCS 2013] in their algorithm for Disjoint Paths on directed planar graphs. To the best of our knowledge our algorithm is the first parameterized algorithm to exploit that the treewidth of the input graph is small in a way completely different from the use of dynamic programming.

An input to a conflict-free variant of a classical problem $$\Gamma $$ , called Conflict-Free $$\Gamma $$ , consists of an instance I of $$\Gamma $$ coupled with a graph H, called the conflict graph. A solution to Conflict-Free $$\Gamma $$ in (I, H) is a solution to I in $$\Gamma $$ , which is also an independent set in H. In this paper, we study conflict-free variants of Maximum Matching and Shortest Path, which we call Conflict-Free Maximum Matching (CF-MM) and Conflict-Free Shortest Path (CF-SP), respectively. We show that both CF-MM and CF-SP are W[1]-hard, when parameterized by the solution size. Moreover, W[1]-hardness for CF-MM holds even when the input graph where we want to find a matching is itself a matching, and W[1]-hardness for CF-SP holds for conflict graph being a unit-interval graph. Next, we study these problems with restriction on the conflict graphs. We give FPT algorithms for CF-MM when the conflict graph is chordal. Also, we give FPT algorithms for both CF-MM and CF-SP, when the conflict graph is d-degenerate. Finally, we design FPT algorithms for variants of CF-MM and CF-SP, where the conflicting conditions are given by a (representable) matroid.

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.

A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq E(G)$, such that $G/X$ is isomorphic to $H$. Here, $G/X$ is the graph obtained from $G$ by contracting all the edges in $X$. For a family of graphs $\cal F$, the $\mathcal{F}$-Contraction problem takes as input a graph $G$ on $n$ vertices, and the objective is to output the largest integer $t$, such that $G$ is contractible to a graph $H \in {\cal F}$, where $|V(H)|=t$. When $\cal F$ is the family of paths, then the corresponding $\mathcal{F}$-Contraction problem is called Path Contraction. The problem Path Contraction admits a simple algorithm running in time $2^{n}\cdot n^{{\mathcal{O}}(1)}$. In spite of the deceptive simplicity of the problem, beating the $2^{n}\cdot n^{{\mathcal{O}}(1)}$ bound for Path Contraction seems quite challenging. In this paper, we design an exact exponential time algorithm for Path Contraction that runs in time ${{1.99987}^n}\cdot n^{{\mathcal O}(1)}$. We also define a problem called 3-Disjoint Connected Subgraphs and design an algorithm for it that runs in time $1.88^n\cdot n^{{\mathcal O}(1)}$. The above algorithm is used as a subroutine in our algorithm for Path Contraction.

An undirected graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy $d>1$ contains a cycle of length at least $d+1$. The proof of Erdös and Gallai is constructive and can be turned into a polynomial time algorithm constructing a cycle of length at least $d+1$. But can we decide in polynomial time whether a graph contains a cycle of length at least $d+2$? An easy reduction from Hamiltonian Cycle provides a negative answer to this question: Deciding whether a graph has a cycle of length at least $d+2$ is NP-complete. Surprisingly, the complexity of the problem changes drastically when the input graph is 2-connected. In this case we prove that deciding whether $G$ contains a cycle of length at least $d+k$ can be done in time $2^{\mathcal{O}(k)}\cdot|V(G)|^{\mathcal{O}(1)}$. In other words, deciding whether a 2-connected $n$-vertex $G$ contains a cycle of length at least $d+\log{n}$ can be done in polynomial time. Similar algorithmic results hold for long paths in graphs. We observe that deciding whether a graph has a path of length at least $d+1$ is NP-complete. However, we prove that if graph $G$ is connected, then deciding whether $G$ contains a path of length at least $d+k$ can be done in time $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$. We complement these results by showing that the choice of degeneracy as the “above guarantee parameterization” is optimal in the following sense: For any $\varepsilon>0$ it is NP-complete to decide whether a connected (2-connected) graph of degeneracy $d$ has a path (cycle) of length at least $(1+\varepsilon)d$.

For a family of graphs ℱ, the W eighted ℱ V ertex D eletion problem, is defined as follows: given an n -vertex undirected graph G and a weight function w : V ( G )࢐ ℝ, find a minimum weight subset S ⊆ V ( G ) such that G - S belongs to ℱ. We devise a recursive scheme to obtain O(log O(1) n )-approximation algorithms for such problems, building upon the classical technique of finding balanced separators . We obtain the first O(log O(1) n )-approximation algorithms for the following problems. • Let F be a finite set of graphs containing a planar graph, and ℱ= G ( F ) be the maximal family of graphs such that every graph H ∈ G ( F ) excludes all graphs in F as minors. The vertex deletion problem corresponding to ℱ= G ( F ) is the W eighted P lanar F -M inor -F ree D eletion (WP F -MFD) problem. We give a randomized and a deterministic approximation algorithms for WP F -MFD with ratios O(log 1.5 n ) and O(log 2 n ), respectively. Prior to our work, a randomized constant factor approximation algorithm for the unweighted version was known [FOCS 2012]. After our work, a deterministic constant factor approximation algorithm for the unweighted version was also obtained [SODA 2019]. • We give an O(log 2 n )-factor approximation algorithm for W eighted C hordal V ertex D eletion , the vertex deletion problem to the family of chordal graphs. On the way to this algorithm, we also obtain a constant factor approximation algorithm for M ulticut on chordal graphs. • We give an O(log 3 n )-factor approximation algorithm for W eighted D istance H ereditary V ertex D eletion . We believe that our recursive scheme can be applied to obtain O(log O(1) n )-approximation algorithms for many other problems as well.

We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constraints. The new constrained clustering problem generalizes a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are L ow GF(2)-R ank A pproximation , L ow B oolean -R ank A pproximation , and various versions of B inary C lustering . For example, for L ow GF(2)-R ank A pproximation problem, where for an m × n binary matrix A and integer r > 0, we seek for a binary matrix B of GF(2) rank at most r such that the ℓ 0 -norm of matrix A−B is minimum, our algorithm, for any ϵ > 0 in time f ( r ,ϵ)⋅ n ⋅ m , where f is some computable function, outputs a (1+ϵ)-approximate solution with probability at least (1−1\ e ). This is the first linear time approximation scheme for these problems. We also give (deterministic) PTASes for these problems running in time n f ( r )1\ϵ 2 log 1\ϵ , where f is some function depending on the problem. Our algorithm for the constrained clustering problem is based on a novel sampling lemma, which is interesting on its own.

A rectilinear Steiner tree for a set K of points in the plane is a tree that connects k using horizontal and vertical lines. In the R ectilinear S teiner T ree problem, the input is a set K ={ z 1 , z 2 ,…, z n } of n points in the Euclidean plane (R 2 ), and the goal is to find a rectilinear Steiner tree for k of smallest possible total length. A rectilinear Steiner arborescence for a set k of points and a root r ∈ K is a rectilinear Steiner tree T for K such that the path in T from r to any point z ∈ K is a shortest path. In the R ectilinear S teiner A rborescence problem, the input is a set K of n points in R 2 , and a root r ∈ K , and the task is to find a rectilinear Steiner arborescence for K , rooted at r of smallest possible total length. In this article, we design deterministic algorithms for these problems that run in 2 O (√ n log n ) time.

We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection L subseteq Lines(P)={l: l is a line segment with both endpoints in P}, and a non-negative integer k, decide if there is a subcollection L'subseteq L such that the graph G=(P,L') is isomorphic to a graph in F and L' has at most k crossings. By G=(P,L'), we refer to the graph on vertex set P, where two vertices are adjacent if and only if there is a line segment that connects them in L'. Intuitively, in Crossing Minimization, we have a set of locations of interest, and we want to build/draw/exhibit connections between them (where L indicates where it is feasible to have these connections) so that we obtain a structure in F. Natural choices for F are the collections of perfect matchings, Hamiltonian paths, and graphs that contain an (s,t)-path (a path whose endpoints are labeled). While the objective of seeking a solution with few crossings is of interest from a theoretical point of view, it is also well motivated by a wide range of practical considerations. For example, links/roads (such as highways) may be cheaper to build and faster to traverse, and signals/moving objects would collide/interrupt each other less often. Further, graphs with fewer crossings are preferred for graphic user interfaces. As a starting point for a systematic study, we consider a special case of Crossing Minimization. Already for this case, we obtain NP-hardness and W[1]-hardness results, and ETH-based lower bounds. Specifically, suppose that the input also contains a collection D of d non-crossing line segments such that each point in P belongs to exactly one line in D, and L does not contain line segments between points on the same line in D. Clearly, Crossing Minimization is the case where d=n - then, P is in general position. The case of d=2 is of interest not only because it is the most restricted non-trivial case, but also since it corresponds to a class of graphs that has been well studied - specifically, it is Crossing Minimization where G=(P,L) is a (bipartite) graph with a so called two-layer drawing. For d=2, we consider three basic choices of F. For perfect matchings, we show (i) NP-hardness with an ETH-based lower bound, (ii) solvability in subexponential parameterized time, and (iii) existence of an O(k^2)-vertex kernel. Second, for Hamiltonian paths, we show (i) solvability in subexponential parameterized time, and (ii) existence of an O(k^2)-vertex kernel. Lastly, for graphs that contain an (s,t)-path, we show (i) NP-hardness and W[1]-hardness, and (ii) membership in XP.

In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately. Motivated by the definitions of the directed variants of the classical Cutwidth and Pathwidth problems, we define Digraph Bandwidth as follows. Given a digraph D and an ordering sigma of its vertices, the digraph bandwidth of sigma with respect to D is equal to the maximum value of sigma(v)-sigma(u) over all arcs (u,v) of D going forward along sigma (that is, when sigma(u) < sigma (v)). The Digraph Bandwidth problem takes as input a digraph D and asks to output an ordering with the minimum digraph bandwidth. The undirected Bandwidth easily reduces to Digraph Bandwidth and thus, it immediately implies that Directed Bandwidth is {NP-hard}. While an O^*(n!) time algorithm for the problem is trivial, the goal of this paper is to design algorithms for Digraph Bandwidth which have running times of the form 2^O(n). In particular, we obtain the following results. Here, n and m denote the number of vertices and arcs of the input digraph D, respectively. - Digraph Bandwidth can be solved in O^*(3^n * 2^m) time. This result implies a 2^O(n) time algorithm on sparse graphs, such as graphs of bounded average degree. - Let G be the underlying undirected graph of the input digraph. If the treewidth of G is at most t, then Digraph Bandwidth can be solved in time O^*(2^(n + (t+2) log n)). This result implies a 2^(n+O(sqrt(n) log n)) algorithm for directed planar graphs and, in general, for the class of digraphs whose underlying undirected graph excludes some fixed graph H as a minor. - Digraph Bandwidth can be solved in min{O^*(4^n * b^n), O^*(4^n * 2^(b log b log n))} time, where b denotes the optimal digraph bandwidth of D. This allow us to deduce a 2^O(n) algorithm in many cases, for example when b <= n/(log^2n). - Finally, we give a (Single) Exponential Time Approximation Scheme for Digraph Bandwidth. In particular, we show that for any fixed real epsilon > 0, we can find an ordering whose digraph bandwidth is at most (1+epsilon) times the optimal digraph bandwidth, in time O^*(4^n * (ceil[4/epsilon])^n).

In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p).

A graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the F-Contraction problem takes as input a graph G on n vertices, and the objective is to output the largest integer t, such that G is contractible to a graph H in F, where |V(H)|=t. When F is the family of paths, then the corresponding F-Contraction problem is called Path Contraction. The problem Path Contraction admits a simple algorithm running in time 2^n * n^{O(1)}. In spite of the deceptive simplicity of the problem, beating the 2^n * n^{O(1)} bound for Path Contraction seems quite challenging. In this paper, we design an exact exponential time algorithm for Path Contraction that runs in time 1.99987^n * n^{O(1)}. We also define a problem called 3-Disjoint Connected Subgraphs, and design an algorithm for it that runs in time 1.88^n * n^{O(1)}. The above algorithm is used as a sub-routine in our algorithm for Path Contraction.

A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)^km epsilon^{-2})-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 +/- epsilon. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space algorithm with running time (2e)^{k+O(log^3k)}m log n whenever epsilon^{-1}=k^{O(1)}. Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4^km epsilon^{-2})-time exponential-space algorithm. In this article, we revisit the algorithm by Alon and Gutner. We modify the foundation of their work, and with a novel twist, obtain the following results. - We present a deterministic 4^{k+O(sqrt{k}(log^2k+log^2 epsilon^{-1}))}m log n-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. - Additionally, we present a randomized 4^{k+O(log k(log k + log epsilon^{-1}))}m log n-time polynomial-space algorithm. While Brand et al. make non-trivial use of exterior algebra, our algorithm is very simple; we only make elementary use of the probabilistic method. Thus, the algorithm by Brand et al. runs in time 4^{k+o(k)}m whenever epsilon^{-1}=2^{o(k)}, while our deterministic and randomized algorithms run in time 4^{k+o(k)}m log n whenever epsilon^{-1}=2^{o(k^{1/4})} and epsilon^{-1}=2^{o(k/(log k))}, respectively. Prior to our work, no 2^{O(k)}n^{O(1)}-time polynomial-space algorithm was known. Additionally, our approach is embeddable in the classic framework of divide-and-color, hence it immediately extends to approximate counting of graphs of bounded treewidth; in comparison, Brand et al. note that their approach is limited to graphs of bounded pathwidth.

Bidimensionality is the most common technique to design subexponential-time parameterized algorithms on special classes of graphs, particularly planar graphs. The core engine behind it is a combinatorial lemma of Robertson, Seymour and Thomas that states that every planar graph either has a $\sqrt{k}\times \sqrt{k}$-grid as a minor, or its treewidth is $O(\sqrt{k})$. However, bidimensionality theory cannot be extended directly to several well-known classes of geometric graphs. Nevertheless, a relaxation of this lemma has been proven useful for unit disk graphs. Inspired by this, we prove a new decomposition lemma for map graphs. Informally, our lemma states the following. For any map graph $G$, there exists a collection $(U_1,\ldots,U_t)$ of cliques of $G$ with the following property: $G$ either contains a $\sqrt{k}\times \sqrt{k}$-grid as a minor, or it admits a tree decomposition where every bag is the union of $O(\sqrt{k})$ of the cliques in the above collection. The new lemma appears to be a handy tool in the design of subexponential parameterized algorithms on map graphs. We demonstrate its usability by designing algorithms on map graphs with running time $2^{O({\sqrt{k}\log{k}})} \cdot n^{O(1)}$ for the Connected Planar $\cal F$-Deletion problem (that encompasses problems such as Feedback Vertex Set and Vertex Cover). Obtaining subexponential algorithms for Longest Cycle/Path and Cycle Packing is more challenging. We have to construct tree decompositions with more powerful properties and to prove sublinear bounds on the number of ways an optimum solution could "cross" bags in these decompositions. For Longest Cycle/Path, these are the first subexponential-time parameterized algorithms on map graphs. For Feedback Vertex Set and Cycle Packing, we improve upon known $2^{O({k^{0.75}\log{k}})} \cdot n^{O(1)}$-time algorithms on map graphs.

Single-elimination tournaments are a popular format in competitive environments. The Tournament Fixing Problem (TFP), which is the problem of finding a seeding of the players such that a certain player wins the resulting tournament, is known to be NP-hard in general and fixed-parameter tractable when parameterized by the feedback arc set number of the input tournament (an oriented complete graph) of expected wins/loses. However, the existence of polynomial kernelizations (efficient preprocessing) for TFP has remained open. In this paper, we present the first polynomial kernelization for TFP parameterized by the feedback arc set number of the input tournament. We achieve this by providing a polynomial-time routine that computes a SAT encoding where the number of clauses is bounded polynomially in the feedback arc set number.

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the linear programming dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT and ATT are fixed-parameter tractable, they can be solved in 2^{O(k log k)} n^{O(1)} time and 2^{O(k)} n^{O(1)} time respectively. Moreover, they both admit a kernel with O(k) vertices. We also prove that ACT and ATT cannot be solved in 2^{o(sqrt{k})} n^{O(1)} time under the Exponential-Time Hypothesis.

Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S ⊆ V(G) of size at most k such that G–S is an interval graph. This problem is known to be NP-complete [Yannakakis, STOC’78]. Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10knO(1) [Cao and Marx, SODA’14]. The existence of a polynomial kernel for IVD remained a well-known open problem in Parameterized Complexity. In this paper, we settle this problem in the affirmative. We also introduce a “bounded intersection” variant of the classical Two Families theorem of Bollobás. We believe this result will find further applications in combinatorics and algorithm design.

An input to the Popular Matching problem, in the roommates setting, consists of a graph G where each vertex ranks its neighbors in strict order, known as its preference. In the Popular Matching problem the objective is to test whether there exists a matching M* such that there is no matching M where more people (vertices) are happier (in terms of the preferences) with M than with M*. In this paper we settle the computational complexity of the Popular Matching problem in the roommates setting by showing that the problem is NP-complete. Thus, we resolve an open question that has been repeatedly and explicitly asked over the last decade.

We give a new decomposition theorem in unit disk graphs (UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits a Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010] and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi (www.youtube.com/watch?v=2Bq2gy1N01w) regarding the existence of contraction decompositions for classes of graphs beyond H-minor free graphs. Second, we present a “parameteric version” of our new decomposition theorem. We prove that there is an algorithm that given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of O(k) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into O(k) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece which is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or slightly superexponential) algorithms for well-studied problems such as Min Bisection, Steiner Cut, s-Way Cut, and Edge Multiway Cut-Uncut on UDGs; these algorithms are substantially faster than the best known algorithms for these problems on general graphs.

We give algorithms with running time $$2^{\mathcal {O}({\sqrt{k}\log {k}})} \cdot n^{\mathcal {O}(1)}$$ for the following problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time $$2^{\mathcal {O}(k^{0.75}\log {k})} \cdot n^{\mathcal {O}(1)}$$ . Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to $$k^{\mathcal {O}(1)}$$ and there exists a solution that crosses every separator at most $$\mathcal {O}(\sqrt{k})$$ times. The running times of our algorithms are optimal up to the $$\log {k}$$ factor in the exponent, assuming the exponential time hypothesis.

In the classic Minimum Bisection problem we are given as input an undirected graph $G$ and an integer $k$. The task is to determine whether there is a partition of $V(G)$ into two parts $A$ and $B$ such that $||A|-|B|| \leq 1$ and there are at most $k$ edges with one endpoint in $A$ and the other in $B$. In this paper we give an algorithm for Minimum Bisection with running time $2^{\mathcal{O}(k^3)}n^3 \log^3 n$. This is the first fixed parameter tractable algorithm for Minimum Bisection parameterized by $k$. At the core of our algorithm lies a new decomposition theorem that states that every graph $G$ can be decomposed by small separators into parts where each part is “highly connected” in the following sense: any separator of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek a bisection of minimum weight among solutions that contain at most $k$ edges.

In the Edge Editing to Connected $f$-Degree Graph problem we are given a graph $G$, an integer $k$, and a function $f$ assigning integers to vertices of $G$. The task is to decide whether there is a connected graph $F$ on the same vertex set as $G$, such that for every vertex $v$, its degree in $F$ is $f(v)$, and the number of edges in $E(G)\triangle E(F)$, the symmetric difference of $E(G)$ and $E(F)$, is at most $k$. We show that Edge Editing to Connected $f$-Degree Graph is fixed-parameter tractable (FPT) by providing an algorithm solving the problem on an $n$-vertex graph in time $2^{\mathcal O(k)}n^{\mathcal O(1)}$. We complement this result by showing that the weighted version of the problem with costs $1$ and $0$ is W[1]-hard when parameterized by $k$ and the maximum value of $f$ even when the input graph is a tree. Our FPT algorithm is based on a nontrivial combination of color-coding and fast computations of representative families over the direct sum matroid of $\ell$-elongation of the co-graphic matroid associated with $G$ and a uniform matroid over the set of nonedges of $G$. We believe that this combination could be useful in designing parameterized algorithms for other edge editing and connectivity problems.

In the Steiner Tree problem, we are given as input a connected $n$-vertex graph with edge weights in $\{1,2,\ldots,W\}$, and a set of $k$ terminal vertices. Our task is to compute a minimum-weight tree that contains all of the terminals. The main result of the paper is an algorithm solving Steiner Tree in time $\mathcal{O}(7.97^k\cdot n^4\cdot \log{W})$ and using $\mathcal{O}(n^3\cdot \log{nW} \cdot \log k)$ space. This is the first single-exponential time, polynomial space FPT algorithm for the weighted Steiner Tree problem. Whereas our main result seeks to optimize the polynomial dependency in $n$ for both the running time and space usage, it is possible to trade between polynomial dependence in $n$ and the single-exponential dependence in $k$ to obtain faster running time as a function of $k$, but at the cost of increased running time and space usage as a function of $n$. In particular, we show that there exists a polynomial space algorithm for Steiner Tree running in $\mathcal{O}(6.751^kn^{O(1)}\log W)$ time. Finally, by pushing such a trade-off between a polynomial in $n$ and an exponential in $k$ dependencies, we show that for any $\epsilon>0$ there is an $n^{\mathcal{O}(f(\epsilon))}\log W$ space $4^{(1+\epsilon)k}n^{\mathcal{O}(f(\epsilon))}\log W$ time algorithm for Steiner Tree, where $f$ is a computable function depending only on $\epsilon$.

The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particular, 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 $2^{\mathcal{O}(k^2)}\cdot |V|$ using exponential space. In the case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a $2^{\mathcal{O}(k\log^2k)}\cdot |V|$-time (deterministic) algorithm using exponential space, which is a consequence of the Erdös--Pósa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time $2^{o(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, beating the bound $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, has been found. In light of this, it seems natural to ask whetherthe $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a $2^{\mathcal{O}(\frac{k\log^2k}{\log\log k})}\cdot |V|$-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 $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, our algorithm runs in time linear in $|V|$, and its space complexity is polynomial in the input size.

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).

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 Wahlström 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$.

Given a graph G and a parameter k , the C hordal V ertex D eletion (CVD) problem asks whether there exists a subset U ⊆ V ( G ) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size O ( k 161 log 58 k ) and asked whether one can design a kernel of size O ( k 10 ) [Jansen an Pilipczuk, SODA 2017]. While we do not completely resolve this question, we design a significantly smaller kernel of size O ( k 12 log 10 k ), inspired by the O ( k 2 ) -size kernel for F eedback V ertex S et [Thomassé, TALG 2010]. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution.

We consider the fundamental Matroid Theory problem of finding a circuit in a matroid containing a set T of given terminal elements. For graphic matroids, this corresponds to the problem of finding a simple cycle passing through a set of given terminal edges in a graph. The algorithmic study of the problem on regular matroids, a superclass of graphic matroids, was initiated by Gavenčiak, Král’, and Oum [ICALP’12], who proved that the case of the problem with ∣T∣ = 2 is fixed-parameter tractable (FPT) when parameterized by the length of the circuit. We extend the result of Gavenčiak, Král’, and Oum by showing that for regular matroids • the M inimum S panning C ircuit problem, deciding whether there is a circuit with at most ℓ elements containing T , is FPT parameterized by k = ℓ − ∣T∣ • the S panning C ircuit problem, deciding whether there is a circuit containing ∣T∣, is FPT parameterized by ∣T∣. We note that extending our algorithmic findings to binary matroids, a superclass of regular matroids, is highly unlikely: M inimum S panning C ircuit parameterized by ℓ is W[1]-hard on binary matroids even when ∣T∣ = 1. We also show a limit to how far our results can be strengthened by considering a smaller parameter. More precisely, we prove that M inimum S panning C ircuit parameterized by ∣T∣ is W[1]-hard even on cographic matroids, a proper subclass of regular matroids.

M AX -C UT , E DGE D OMINATING S ET , G RAPH C OLORING , and H AMILTONIAN C YCLE on graphs of bounded clique-width have received significant attention as they can be formulated in MSO 2 (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle’s theorem), but cannot be formulated in MSO 1 (which would have yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g ( k ) n f ( k ) on graphs of clique-width k . Fomin et al. (2010) showed that the running times cannot be improved to g ( k ) n O (1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f ( k ) in the running times. In a follow-up paper, Fomin et al. (2014) improved the running times for E DGE D OMINATING S ET and M AX -C UT to n O ( k ) , and proved that these problems cannot be solved in time g ( k ) n o ( k ) unless ETH fails. Thus, prior to this work, E DGE D OMINATING S ET and M AX -C UT were known to have tight n Θ ( k ) algorithmic upper and lower bounds. In this article, we provide lower bounds for H AMILTONIAN C YCLE and G RAPH C OLORING . For H AMILTONIAN C YCLE , our lower bound g ( k ) n o ( k ) matches asymptotically the recent upper bound n O ( k ) due to Bergougnoux, Kanté, and Kwon (2017). As opposed to the asymptotically tight n Θ( k ) bounds for E DGE D OMINATING S ET , M AX -C UT , and H AMILTONIAN C YCLE , the G RAPH C OLORING problem has an upper bound of n O (2 k ) and a lower bound of merely n o (√ [4] k ) (implicit from the W[1]-hardness proof). In this article, we close the gap for G RAPH C OLORING by proving a lower bound of n 2 o ( k ) . This shows that G RAPH C OLORING behaves qualitatively different from the other three problems. To the best of our knowledge, G RAPH C OLORING is the first natural problem known to require exponential dependence on the parameter in the exponent of n .

We consider four well-studied NP-complete packing/covering problems on graphs: F eedback V ertex S et in T ournaments (FVST), C luster V ertex D eletion (CVD), T riangle P acking in T ournaments (TPT) and I nduced P 3 -P acking . For these four problems, kernels with O ( k 2 ) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of k pairwise disjoint sets of size 3 (3-S et P acking ) or a hitting set of size at most k for a family of sets of size at most 3 (3-H itting S et ). In this article, we give the first kernels for FVST, CVD, TPT, and I nduced P 3 -P acking with a subquadratic number of vertices. Specifically, we obtain the following results. • FVST admits a kernel with O ( k 3/2 ) vertices. • CVD admits a kernel with O ( k 5/3 ) vertices. • TPT admits a kernel with O ( k 3/2 ) vertices. • I nduced P 3 -P acking admits a kernel with O ( k 5/3 ) vertices. Our results resolve an open problem from WorKer 2010 on the existence of kernels with O( k 2−ϵ ) vertices for FVST and CVD. All of our results are based on novel uses of old and new “expansion lemmas” and a weak form of crown decomposition where (i) almost all of the head is used by the solution (as opposed to all ), (ii) almost none of the crown is used by the solution (as opposed to none ), and (iii) if H is removed from G , then there is almost no interaction between the head and the rest (as opposed to no interaction at all).

For a family of graphs $\cal F$, the canonical Weighted $\cal F$ Vertex Deletion problem is defined as follows: given an $n$-vertex undirected graph $G$ and a weight function $w: V(G)\rightarrow\mathbb{R}$, find a minimum weight subset $S\subseteq V(G)$ such that $G-S$ belongs to $\cal F$. We devise a recursive scheme to obtain $O(\log^{O(1)}n)$-approximation algorithms for such problems, building upon the classic technique of finding balanced separators in a graph. Roughly speaking, our scheme applies to problems where an optimum solution $S$, together with a well-structured set $X$, form a balanced separator of $G$. We obtain the first $O(\log^{O(1)}n)$-approximation algorithms for the following problems. * We give an $O(\log^2n)$-factor approximation algorithm for Weighted Chordal Vertex Deletion (WCVD), the vertex deletion problem to the family of chordal graphs. On the way, we also obtain a constant factor approximation algorithm for Multicut on chordal graphs. * We give an $O(\log^3n)$-factor approximation algorithm for Weighted Distance Hereditary Vertex Deletion (WDHVD). This is the vertex deletion problem to the family of distance hereditary graphs, or equivalently, the family of graphs of rankwidth 1. Our methods also allow us to obtain in a clean fashion a $O(\log^{1.5}n)$-approximation algorithm for the Weighted $\cal F$ Vertex Deletion problem when $\cal F$ is a minor closed family excluding at least one planar graph. For the unweighted version of the problem constant factor approximation algorithms are were known~[Fomin et al., FOCS~2012], while for the weighted version considered here an $O(\log n \log\log n)$-approximation algorithm follows from~[Bansal et al., SODA~2017]. We believe that our recursive scheme can be applied to obtain $O(\log^{O(1)}n)$-approximation algorithms for many other problems as well.

We study the problem of finding a minimum-distortion embedding of the shortest path metric of an unweighted graph into a "simpler" metric X. Computing such an embedding (exactly or approximately) is a non-trivial task even when X is the metric induced by a path, or, equivalently, the real line. In this paper we give approximation and fixed-parameter tractable (FPT) algorithms for minimum-distortion embeddings into the metric of a subdivision of some fixed graph H, or, equivalently, into any fixed 1-dimensional simplicial complex. More precisely, we study the following problem: For given graphs G, H and integer c, is it possible to embed G with distortion c into a graph homeomorphic to H? Then embedding into the line is the special case H=K_2, and embedding into the cycle is the case H=K_3, where K_k denotes the complete graph on k vertices. For this problem we give - an approximation algorithm, which in time f(H)* poly (n), for some function f, either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion poly(c); - an exact algorithm, which in time f'(H, c)* poly (n), for some function f', either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion c. Prior to our work, poly(OPT)-approximation or FPT algorithms were known only for embedding into paths and trees of bounded degrees.

In the classic Integer Programming (IP) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b=(b_1,..., b_m), there is a non-negative integer n-vector x such that Ax=b. Solving (IP) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IP) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ArXiv 2018]. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal. We also show that when the matrix A is assumed to be non-negative, a component of Papadimitriou's original algorithm is already nearly optimal under ETH. This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IP) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IP) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IP) when the path-width of the corresponding column-matroid is a constant.

Fradkin and Seymour [Journal of Combinatorial Graph Theory, Series B, 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 [ESA, 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 that the yes-instances of the problems above have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, an inductive argument and structural properties of the digraphs.

In the Directed Feedback Vertex Set (DFVS) problem, we are given as input a directed graph D and an integer k, and the objective is to check whether there exists a set S of at most k vertices such that F=D-S is a directed acyclic graph (DAG). Determining whether DFVS admits a polynomial kernel (parameterized by the solution size) is one of the most important open problems in parameterized complexity. In this article, we give a polynomial kernel for DFVS parameterized by the solution size plus the size of any treewidth-eta modulator, for any positive integer eta. We also give a polynomial kernel for the problem, which we call Vertex Deletion to treewidth-eta DAG, where given as input a directed graph D and a positive integer k, the objective is to decide whether there exists a set of at most k vertices, say S, such that D-S is a DAG and the treewidth of D-S is at most eta.

Given a Counting Monadic Second Order (CMSO) sentence $ψ$, the CMSO$[ψ]$ problem is defined as follows. The input to CMSO$[ψ]$ is a graph $G$, and the objective is to determine whether $G\models ψ$. Our main theorem states that for every CMSO sentence $ψ$, if CMSO$[ψ]$ is solvable in polynomial time on "globally highly connected graphs", then CMSO$[ψ]$ is solvable in polynomial time (on general graphs). We demonstrate the utility of our theorem in the design of parameterized algorithms. Specifically we show that technical problem-specific ingredients of a powerful method for designing parameterized algorithms, recursive understanding, can be replaced by a black-box invocation of our main theorem. We also show that our theorem can be easily deployed to show fixed parameterized tractability of a wide range of problems, where the input is a graph $G$ and the task is to find a connected induced subgraph of $G$ such that "few" vertices in this subgraph have neighbors outside the subgraph, and additionally the subgraph has a CMSO-definable property.

A knockout tournament is a standard format of competition, ubiquitous in sports, elections and decision making. Such a competition consists of several rounds. In each round, all players that have not yet been eliminated are paired up into matches. Losers are eliminated, and winners are raised to the next round, until only one winner exists. Given that we can correctly predict the outcome of each potential match (modelled by a tournament D), a seeding of the tournament deterministically determines its winner. Having a favorite player v in mind, the Tournament Fixing Problem (TFP) asks whether there exists a seeding that makes v the winner. Aziz et al. [AAAI’14] showed that TFP is NP-hard. They initiated the study of the parameterized complexity of TFP with respect to the feedback arc set number k of D, and gave an XP-algorithm (which is highly inefficient). Recently, Ramanujan and Szeider [AAAI’17] showed that TFP admits an FPT algorithm, running in time 2^{ O(k^2 log k)} n ^{O(1)}. At the heart of this algorithm is a translation of TFP into an algebraic system of equations, solved in a black box fashion (by an ILP solver). We present a fresh, purely combinatorial greedy solution. We rely on new insights into TFP itself, which also results in the better running time bound of 2^{ O(k log k)} n^{ O(1)} . While our analysis is intricate, the algorithm itself is surprisingly simple.

In a tournament, $n$ players enter the competition. In each round, they are paired-up to compete against each other. Losers are thrown, while winners proceed to the next round, until only one player (the winner) is left. Given a prediction of the outcome, for every pair of players, of a match between them (modeled by a digraph $D$), the competitive nature of a tournament makes it attractive for manipulators. In the Tournament Fixing (TF) problem, the goal is to decide if we can conduct the competition (by controlling how players are paired-up) so that our favorite player $w$ wins. A common form of manipulation is to bribe players to alter the outcome of matches. Kim and Williams [IJCAI 2015] integrated such deceit into TF, and showed that the resulting problem is NP-hard when $\ell<(1-\epsilon)\log n$ alterations are possible (for any fixed $\epsilon>0$). For this problem, our contribution is fourfold. First, we present two operations that ``obfuscate deceit'': given one solution, they produce another solution. Second, we present a combinatorial result, stating that there is always a solution with all reversals incident to $w$ and ``elite players''. Third, we give a closed formula for the case where $D$ is a DAG. Finally, we present exact exponential-time and parameterized algorithms for the general case.

Deterministic polynomial-time computation of a representation of a transversal matroid is a longstanding open problem. We present a deterministic computation of a so-called union representation of a transversal matroid in time quasipolynomial in the rank of the matroid. More precisely, we output a collection of linear matroids such that a set is independent in the transversal matroid if and only if it is independent in at least one of them. Our proof directly implies that if one is interested in preserving independent sets of size at most r, for a given r\in\mathbb{N}, but does not care whether larger independent sets are preserved, then a union representation can be computed deterministically in time quasipolynomial in r. This consequence is of independent interest, and sheds light on the power of union~representation. Our main result also has applications in Parameterized Complexity. First, it yields a fast computation of representative sets, and due to our relaxation in the context of r, this computation also extends to (standard) truncations. In turn, this computation enables to efficiently solve various problems, such as subcases of subgraph isomorphism, motif search and packing problems, in the presence of color lists. Such problems have been studied to model scenarios where pairs of elements to be matched may not be identical but only similar, and color lists aim to describe the set of compatible elements associated with each element.

In this paper, we study the query complexity of parameterized decision and optimization versions of Hitting-Set. We also investigate the query complexity of Packing. In doing so, we use generalizations to hypergraphs of an earlier query model, known as BIS introduced by Beame et al. in ITCS'18. The query models considered are the GPIS and GPISE oracles. The GPIS and GPISE oracles are used for the decision and optimization versions of the problems, respectively. We use color coding and queries to the oracles to generate subsamples from the hypergraph, that retain some structural properties of the original hypergraph. We use the stability of the sunflowers in a non-trivial way to do so.

Hubs are high-degree nodes within a network. The examination of the emergence and centrality of hubs lies at the heart of many studies of complex networks such as telecommunication networks, biological networks, social networks and semantic networks. Furthermore, identifying and allocating hubs are routine tasks in applications. In this paper, we do not seek a hub that is a single node, but a hub that consists of k nodes. Formally, given a graph G=(V,E), we a seek a set A subseteq 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), can also be viewed as 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 the first parameterized algorithm that shows that MNH is FPT with respect to the parameter p. Despite recent breakthrough advances for cut-problems like Multicut and Minimum Bisection, MNH is still very challenging. Not only does a connectivity constraint has to be handled on top of the involved machinery developed for these problems, but also the fact that MNH is a maximization problem seems to prevent the applicability of this machinery in the first place. To deal with the latter issue, we give non-trivial reduction rules that show how MNH can be preprocessed into a problem where it is necessary to delete a bounded-in-parameter number of vertices. Then, to handle the connectivity constraint, we use a novel application of the form of tree decomposition introduced by Cygan et al. [STOC 2014] to solve Minimum Bisection, where we demonstrate how connectivity constraints can be replaced by simpler size constraints. Our approach may be relevant to the design of algorithms for other cut-problems of this nature.

A generalization of classical cycle hitting problems, called conflict version of the problem, is defined as follows. An input is undirected graphs G and H on the same vertex set, and a positive integer k, and the objective is to decide whether there exists a vertex subset X subseteq V(G) such that it intersects all desired "cycles" (all cycles or all odd cycles or all even cycles) and X is an independent set in H. In this paper we study the conflict version of classical Feedback Vertex Set, and Odd Cycle Transversal problems, from the view point of kernelization complexity. In particular, we obtain the following results, when the conflict graph H belongs to the family of d-degenerate graphs. 1) CF-FVS admits a O(k^{O(d)}) kernel. 2) CF-OCT does not admit polynomial kernel (even when H is 1-degenerate), unless NP subseteq coNP/poly. For our kernelization algorithm we exploit ideas developed for designing polynomial kernels for the classical Feedback Vertex Set problem, as well as, devise new reduction rules that exploit degeneracy crucially. Our main conceptual contribution here is the notion of "k-independence preserver". Informally, it is a set of "important" vertices for a given subset X subseteq V(H), that is enough to capture the independent set property in H. We show that for d-degenerate graph independence preserver of size k^{O(d)} exists, and can be used in designing polynomial kernel.

In the embedded planar diameter improvement problem (EPDI) we are given a graph G embedded in the plane and a positive integer d. The goal is to determine whether one can add edges to the planar embedding of G in such a way that planarity is preserved and in such a way that the resulting graph has diameter at most d. Using non-constructive techniques derived from Robertson and Seymour's graph minor theory, together with the effectivization by self-reduction technique introduced by Fellows and Langston, one can show that EPDI can be solved in time f(d)* |V(G)|^{O(1)} for some function f(d). The caveat is that this algorithm is not strongly uniform in the sense that the function f(d) is not known to be computable. On the other hand, even the problem of determining whether EPDI can be solved in time f_1(d)* |V(G)|^{f_2(d)} for computable functions f_1 and f_2 has been open for more than two decades [Cohen at. al. Journal of Computer and System Sciences, 2017]. In this work we settle this later problem by showing that EPDI can be solved in time f(d)* |V(G)|^{O(d)} for some computable function f. Our techniques can also be used to show that the embedded k-outerplanar diameter improvement problem (k-EOPDI), a variant of EPDI where the resulting graph is required to be k-outerplanar instead of planar, can be solved in time f(d)* |V(G)|^{O(k)} for some computable function f. This shows that for each fixed k, the problem k-EOPDI is strongly uniformly fixed parameter tractable with respect to the diameter parameter d.

In this paper we study recently introduced conflict version of the classical Feedback Vertex Set (FVS) problem. For a family of graphs F, we consider the problem F-CF-Feedback Vertex Set (F-CF-FVS, for short). The F-CF-FVS problem takes as an input a graph G, a graph H in F (where V(G)=V(H)), and an integer k, and the objective is to decide if there is a set S subseteq V(G) of size at most k such that G-S is a forest and S is an independent set in H. Observe that if we instantiate F to be the family of edgeless graphs then we get the classical FVS problem. Jain, Kanesh, and Misra [CSR 2018] showed that in contrast to FVS, F-CF-FVS is W[1]-hard on general graphs and admits an FPT algorithm if F is the family of d-degenerate graphs. In this paper, we relate F-CF-FVS to the Independent Set problem on special classes of graphs, and obtain a complete dichotomy result on the Parameterized Complexity of the problem F-CF-FVS, when F is a hereditary graph family. In particular, we show that F-CF-FVS is FPT parameterized by the solution size if and only if F+Cluster IS is FPT parameterized by the solution size. Here, F+Cluster IS is the Independent Set problem in the (edge) union of a graph G in F and a cluster graph H (G and H are explicitly given). Next, we exploit this characterization to obtain new FPT results as well as intractability results for F-CF-FVS. In particular, we give an FPT algorithm for F+Cluster IS when F is the family of K_{i,j}-free graphs. We show that for the family of bipartite graph B, B-CF-FVS is W[1]-hard, when parameterized by the solution size. Finally, we consider, for each 0< epsilon<1, the family of graphs F_epsilon, which comprise of graphs G such that |E(G)| <= |V(G)|^(2-epsilon), and show that F_epsilon-CF-FVS is W[1]-hard, when parameterized by the solution size, for every 0<epsilon<1.

In the Survivable Network Design Problem (SNDP), the input is an edge-weighted (di)graph G and an integer ruυ for every pair of vertices u, υ ∊ V(G). The objective is to construct a subgraph H of minimum weight which contains ruυ edge-disjoint (or node-disjoint) u-υ paths. This is a fundamental problem in combinatorial optimization that captures numerous well-studied problems in graph theory and graph algorithms. Consequently, there is a long line of research into exact-polynomial time algorithms as well as approximation algorithms for various restrictions of this problem. An important restriction of this problem is one where the connectivity demands are the same for every pair of vertices. In this paper, we first consider the edge-connectivity version of this problem which we call λ-Edge Connected Subgraph (λ-ECS). In this problem, the input is a λ-edge connected (di)graph G and an integer k and the objective is to check whether G contains a spanning subgraph H that is also λ-edge connected and H excludes at least k edges of G. In other words, we are asked to compute a maximum subset of edges, of cardinality at least k, which may be safely deleted from G without affecting its connectivity. If we replace λ-edge connectivity with λ-vertex connectivity we get the λ-Vertex Connected Subgraph (λ-VCS) problem. We show that λ-ECS is fixed-parameter tractable (FPT) for both graphs and digraphs even if the (di)graph has nonnegative real weights on the edges and the objective is to exclude from H, some edges of G whose total weight exceeds a prescribed value. In particular, we design an algorithm for the weighted variant of the problem with running time 2O(k log k) |V(G)|O(1). We follow up on this result and obtain a polynomial compression for λ-ECS on unweighted graphs. As a direct consequence of our results, we obtain the first FPT algorithm for the parameterized version of the classical Minimum Equivalent Graph (MEG) problem. We also show that λ-Ves is FPT on digraphs; however the problem on undirected graphs remains open. Finally, we complement our algorithmic findings by showing that SNDP is W[1]-hard for both arc and vertex connectivity versions on digraphs. The core of our algorithms is composed of new combinatorial results on connectivity in digraphs and undirected graphs.

Max-Cut (MC), Edge Dominating Set (EDS), Graph Coloring (GC) and Hamiltonian Path (HP) on graphs of bounded cliquewidth have received significant attention as they can be formulated in MSO2 (and therefore have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle's theorem), but cannot be formulated in MSO1 (which would have yielded linear-time algorithms on bounded cliquewidth graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g(k)nf(k) on graphs of cliquewidth k. Fomin et al. [Intractability of Clique-Width Parameterizations. SIAM J. Comput. 39(5): 1941–1956 (2010)] showed that the running times cannot be improved to g(k)nO(1) assuming W[1]≠FPT. However, this does not rule out nontrivial improvements to the exponent f(k) in the running times. In a follow-up paper, Fomin et al. [Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. SIAM J. Comput. 43(5): 1541–1563 (2014)] improved the running times for EDS and MC to nO(k), and proved g(k)no(k) lower bounds for EDS, MC and HP assuming the ETH. Recently, Bergougnoux, Kante and Kwon [WADS 2017] gave an nO(k)-time algorithm for HP. Thus, prior to this work, EDS, MC and HP were known to have tight nΘ(k) algorithmic upper and lower bounds. In contrast, GC has an upper bound of nO(2k) and a lower bound of merely (implicit from the W[1]-hardness proof). In this paper, we close the gap for GC by proving a lower bound of n2o(k) This shows that GC behaves qualitatively different from the other three problems. To the best of our knowledge, GC is the first natural problem known to require exponential dependence on the parameter in the exponent of n.

We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For these four problems kernels with O(k2) vertices have been known for a long time. In fact, such kernels can be obtained by interpreting these problems as finding either a packing of k pairwise disjoint sets of size 3 (3-Set Packing) or a hitting set of size at most k for a family of sets of size at most 3 (3-Hitting Set). In this paper, we give the first kernels for FVST, CVD, TPT and Induced P3-Packing with a subquadratic number of vertices. Specifically, we obtain the following results. • FVST admits a kernel with vertices. • CVD admits a kernel with vertices. • TPT admits a kernel with vertices. • Induced P3-Packing admits a kernel with vertices. Our results resolve an open problem from WorKer 2010 on the existence of kernels with

We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a d-degenerate graph G and an integer k, outputs an independent set Y, such that for every independent set X in G of size at most k, the probability that X is a subset of Y is at least . The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph G, a set T = {{s1, t1}, {s2, t2}, …, {sℓ, tℓ}} of terminal pairs and an integer k, returns an induced subgraph G* of G that maintains all the inclusion minimal multicuts of G of size at most k, and does not contain any (k + 2)-vertex connected set of size 2O(k). In particular, G* excludes a clique of size 2O(k) as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for Stable s-t Separator, Stable Odd Cycle Transversal and Stable Multicut on general graphs, and for Stable Directed Feedback Vertex Set on d-degenerate graphs, resolving two problems left open by Marx et al. [ACM Transactions on Algorithms, 2013]. All of our algorithms can be derandomized at the cost of a small overhead in the running time.

Planarity, bipartiteness and (directed) acyclicity are basic graph properties with classic linear time recognition algorithms. However, the problems of testing whether a given (di)graph has k vertices whose deletion makes it planar, bipartite or a directed acyclic graph (DAG) are all fundamental NP-complete problems when k is part of the input. As a result, a significant amount of research has been devoted to understanding whether, for every fixed k, these problems admit a polynomial time algorithm (where the exponent in the polynomial is independent of k) and in particular, whether they admit linear time algorithms. While we now know that for any fixed k, we can test in linear time whether a graph is k vertices away from being planar [FOCS 2009, SODA 2014] or bipartite [SODA 2014, SICOMP 2016], the best known algorithms in the case of directed acyclicity are the algorithm of Garey and Tarjan [IPL 78] which runs in time O(nk–1m) and the algorithm of Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008] which runs in time O(k!4kk4nm). In other words, it has remained open whether it is possible to recognize in linear time, a graph which is 2 vertices away from being acyclic! In this paper, we settle this question by giving an algorithm that decides whether a given graph is k vertices away from being acyclic, in time O(k!4kk5(n + m)). That is, for every fixed k, our algorithm runs in time O(m + n), thus mirroring the case for planarity and bipartiteness. Our algorithm is designed via a general methodology that shaves off a factor of n from some algorithms that use the powerful technique of iterative compression. The two main features of our methodology are: (i) This is the first generic technique for designing linear time algorithms for directed cut-problems and (ii) it can be used in combination with future improvements in algorithms for the compression version of other well-studied cut-problems such as Multicut and Directed Subset Feedback Vertex Set.

A classical result by Erdos and Posa states that there is a function $f: {\mathbb N} \rightarrow {\mathbb N}$ such that for every $k$, every graph $G$ contains $k$ pairwise vertex disjoint cycles or a set $T$ of at most $f(k)$ vertices such that $G-T$ is acyclic. The generalisation of this result to directed graphs is known as Younger's conjecture and was proved by Reed, Robertson, Seymour and Thomas in 1996. This so-called Erdos-Posa-property can naturally be generalised to arbitrary graphs and digraphs. Robertson and Seymour proved that a graph $H$ has the Erdos-Posa-property if, and only if, $H$ is planar. In this paper we study the corresponding problem for digraphs. We obtain a complete characterisation of the class of strongly connected digraphs which have the Erdos-Posa-property (both for topological and butterfly minors). We also generalise this result to classes of digraphs which are not strongly connected. In particular, we study the class of vertex-cyclic digraphs (digraphs without trivial strong components). For this natural class of digraphs we obtain a nearly complete characterisation of the digraphs within this class with the Erdos-Posa-property. In particular we give positive and algorithmic examples of digraphs with the Erdos-Posa-property by using directed tree decompositions in a novel way.

Two of the most widely used approaches to obtain polynomial-time approximation schemes (PTASs) on planar graphs are the Lipton-Tarjan separator-based approach and Baker’s approach. In 2005, Demaine and Hajiaghayi strengthened both approaches using bidimensionality and obtained efficient polynomial-time approximation schemes (EPTASs) for several problems, including C onnected D ominating S et and F eedback V ertex S et . In this work, we unify the two strengthened approaches to combine the best of both worlds. We develop a framework allowing the design of EPTAS on classes of graphs with the subquadratic grid minor (SQGM) property. Roughly speaking, a class of graphs has the SQGM property if, for every graph G from the class, the fact that G contains no t × t grid as a minor guarantees that the treewidth of G is subquadratic in t . For example, the class of planar graphs and, more generally, classes of graphs excluding some fixed graph as a minor, have the SQGM property. At the heart of our framework is a decomposition lemma stating that for “most” bidimensional problems on a graph class G with the SQGM property, there is a polynomial-time algorithm that, given a graph G ϵ G as input and an ϵ > 0, outputs a vertex set X of size ϵ ċ OPT such that the treewidth of G - X is f (ϵ). Here, OPT is the objective function value of the problem in question and f is a function depending only on ϵ. This allows us to obtain EPTASs on (apex)-minor-free graphs for all problems covered by the previous framework as well as for a wide range of packing problems, partial covering problems and problems that are neither closed under taking minors nor contractions. To the best of our knowledge, for many of these problems—including C ycle P acking , F -P acking , F -D eletion , M ax L eaf S panning T ree , or P artial r -D ominating S et —no EPTASs, even on planar graphs, were previously known. We also prove novel excluded grid theorems in unit disk and map graphs without large cliques. Using these theorems, we show that these classes of graphs have the SQGM property. Based on the developed framework, we design EPTASs and subexponential time parameterized algorithms for various classes of problems on unit disk and map graphs.

A central problem in parameterized algorithms is to obtain algorithms with running time $f(k)\cdot n^{O(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, $c^k$ 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 $k^{O(k)}=2^{O(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 $s_1$, $\dots$, $s_t$ over an alphabet $\Sigma$ of length $L$ each, and an integer $d$, the question is whether there exists a string $s$ over $\Sigma$ of length $L$, such that its hamming distance from each of the strings $s_i$, $1\leq i \leq t$, is at most $d$. The pattern matching problem Closest String is known to be solvable in times $2^{O(d\log d)}\cdot n^{O(1)}$ and $2^{O(d\log |\Sigma|)}\cdot n^{O(1)}$. We show that there are no $2^{o(d\log d)}\cdot n^{O(1)}$ or $2^{o(d\log |\Sigma|)}\cdot n^{O(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 $2^{O(d\log d)}\cdot n^{O(1)}$. We show that there is no $2^{o(d\log d)}\cdot n^{O(1)}$ time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time $2^{O(w\log w)}\cdot n^{O(1)}$ on graphs of treewidth at most $w$. We show that there is no $2^{o(w\log w)}\cdot n^{O(1)}$ time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time $2^{O(w\log w)}\cdot n^{O(1)}$ on graphs of treewidth at most $w$. We show that there is no $2^{o(w\log w)}\cdot n^{O(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.

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e., finding $k$ vertex disjoint cycles in a given graph $G$, admits no polynomial kernel unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of constraints that separate kernelizable from nonkernelizable variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a global relaxation parameter $t$. That is, given a graph $G$ and integers $k$ and $t$, the goal is to find at least $k$ distinct cycles such that every vertex of $G$ appears in at most $t$ of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a local relaxation parameter, and we seek at least $k$ distinct cycles such that every two cycles intersect in at most $t$ vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all $t \geq 1$, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for $t = \frac{k}{c}$, where $c$ could be a function of $k$, we obtain a kernel of size $\mathcal{O}(2^{c^2}k^{7 + c}\log^3 k)$ whenever $c\in o(\sqrt k)$. Thus the kernel size varies from being subexponential when $c\in o(\sqrt k)$, to quasi-polynomial when $c\in o(\log^{\ell} k)$, $\ell \in \mathbb{R}_+$, and polynomial when $c\in \mathcal{O}(1)$. We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever $t \in \mathcal{O}(k^{\epsilon})$ for any $0 \leq \epsilon < 1$, unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$.

Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For a hypergraph $H=(U, \mathcal{F})$, a conflict-free coloring of $H$ refers to a vertex coloring where every hyperedge has a vertex with a unique color, distinct from all other vertices in the hyperedge. In this paper, we initiate a study of a natural maximization version of this problem, namely, Max-CFC: For a given hypergraph $H$ and a fixed $r\geq 2$, color the vertices of $U$ using $r$ colors so that the number of hyperedges that are conflict-free colored is maximized. By previously known hardness results for conflict-free coloring, this maximization version is NP-hard. We study this problem in the context of both exact and parameterized algorithms. In the parameterized setting, we study this problem with respect to a natural parameter---the solution size. In particular, the question we study is the following: p-CFC: For a given hypergraph, can we conflict-free color at least $k$ hyperedges with at most $r$ colors, the parameter being the solution size $k$. We show that this problem is fixed parameter tractable by designing an algorithm with running time $2^{\mathcal{O}(k \log \log k + k \log r)}(n+m)^{\mathcal{O}(1)}$ using a novel connection to the Unique Coverage problem and applying the method of color coding in a nontrivial manner. For the special case for hypergraphs induced by graph neighborhoods we give a polynomial kernel. Finally, we give an exact algorithm for Max-CFC running in $\mathcal{O}(2^{n+m})$ time. All our algorithms, with minor modifications, work for a stronger version of conflict-free coloring, Unique Maximum Coloring.

Seymour's decomposition theorem for regular matroids is a fundamental result with a number of combinatorial and algorithmic applications. In this work we demonstrate how this theorem can be used in the design of parameterized algorithms on regular matroids. We consider the problem of covering a set of vectors of a given finite dimensional linear space (vector space) by a subspace generated by a set of vectors of minimum size. Specifically, in the Space Cover problem, we are given a matrix $M$ and a subset of its columns $T$; the task is to find a minimum set $F$ of columns of $M$ disjoint with $T$ such that the linear span of $F$ contains all vectors of $T$. For graphic matroids this problem is essentially Steiner Forest and for cographic matroids this is a generalization of Multiway Cut. Our main result is the algorithm with running time $2^{\mathcal{O}h(k)}\cdot ||M|| ^{\mathcal{O}h(1)}$ solving Space Cover in the case when $M$ is a totally unimodular matrix over rationals, where $k$ is the size of $F$. In other words, we show that on regular matroids the problem is fixed-parameter tractable parameterized by the rank of the covering subspace.

For a target rank $r$, the rigidity of a matrix $A$ over a field $\mathbb{F}$ is the minimum Hamming distance between $A$ and a matrix of rank at most $r$. Rigidity is a classical concept in computational complexity theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of parameterized complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of parameterized complexity. Naturally, given parameters $r$ and $k$, the Matrix Rigidity problem asks whether the rigidity of $A$ for the target rank $r$ is at most $k$. We show that in the case $\mathbb{F}=\mathbb{R}$ or $\mathbb{F}$ is any finite field, this problem is fixed-parameter tractable with respect to $k+r$. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in real algebraic geometry, which are not well known in parameterized complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a \sf W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.

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 $\mathcal{O}(2^{(1-\epsilon)n})$ minimal connected dominating sets. For the same $\epsilon$ we also give an algorithm with running time $2^{(1-\epsilon)n}\cdot n^{\mathcal{O}(1)}$ to enumerate all minimal connected dominating sets in an input graph $G$.

Feedback Vertex Set (FVS) is one of the most well-studied problems in the realm of parameterized complexity. In this problem we are given a graph $G$ and a positive integer $k$ and the objective is to test whether there exists $S\subseteq V(G)$ of size at most $k$ such that $G-S$ is a forest. Thus, FVS is about deleting as few vertices as possible to get a forest. The main goal of this paper is to study the following interesting problem: How can we generalize the family of forests such that the nice structural properties of forests and the interesting algorithmic properties of FVS can be extended to problems on this class? Toward this we define a graph class, ${\cal F}_l$, that contains all graphs where each connected component can be transformed into a forest by deleting at most $l$ edges. A graph in the class ${\cal F}_1$ is known as pseudoforest in the literature and we call a graph in ${\cal F}_l$ an $l$-pseudoforest. We study the problem of deleting $k$ vertices to get into ${\cal F}_l$, l-pseudoforest Deletion, in the realm of parameterized complexity. We show that l-pseudoforest Deletion admits an algorithm with running time $c_l^k n^{\mathcal{O}(1)}$ and admits a kernel of size $f(l)k^2$. Thus, for every fixed $l$ we have a kernel of size $\mathcal{O}(k^2)$. That is, we get a uniform polynomial kernel for l-pseudoforest Deletion. Our algorithms and uniform kernels involve the use of the expansion lemma and protrusion machinery.

Given a 1.5-dimensional terrain T , also known as an x -monotone polygonal chain, the T errain G uarding problem seeks a set of points of minimum size on T that guards all of the points on T . Here, we say that a point p guards a point q if no point of the line segment pq is strictly below T . The T errain G uarding problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm (SODA 2005). However, only in 2010 King and Krohn (SODA 2010) finally showed that T errain G uarding is NP-hard. In spite of the remarkable developments in approximation algorithms for T errain G uarding , next to nothing is known about its parameterized complexity. In particular, the most intriguing open questions in this direction ask whether, if parameterized by the size k of a solution guard set, it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this article, we answer the first question affirmatively by developing an n O (√ k ) -time algorithm for both D iscrete T errain G uarding and C ontinuous T errain G uarding . We also make non-trivial progress with respect to the second question: we show that D iscrete O rthogonal T errain G uarding , a well-studied special case of T errain G uarding , is fixed-parameter tractable.

No abstract available.

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial time; however, the exponent of the polynomial is large. Therefore, our main goal is to construct algorithms with running time of the form poly( k )⋅ n or poly( k )⋅ n log n , where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O ( n 1/ c ) for a constant c . Our results include the following: — an algorithm for computing the determinant and the rank of an n × n matrix using O ( k 3 ⋅ n ) time and arithmetic operations; —an algorithm for solving a system of linear equations using O ( k 3 ⋅ n ) time and arithmetic operations; —an O ( k 3 ⋅ n log n )-time randomized algorithm for finding the cardinality of a maximum matching in a graph; —an O ( k 4 ⋅ n log 2 n )-time randomized algorithm for constructing a maximum matching in a graph; —an O ( k 2 ⋅ n log n )-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we give an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph G and integer k , runs in time O ( k 7 ⋅ n log n ) and either correctly reports that the treewidth of G is larger than k , or constructs a tree decomposition of G of width O ( k 2 ). The above results stand in contrast with the recent work of Abboud et al. (SODA 2016), which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth.

We give the first linear kernels for the D ominating S et and C onnected D ominating S et problems on graphs excluding a fixed graph H as a topological minor. In other words, we prove the existence of polynomial time algorithms that, for a given H -topological-minor-free graph G and a positive integer k , output an H -topological-minor-free graph G ′ on O ( k ) vertices such that G has a (connected) dominating set of size k if and only if G ′ has one. Our results extend the known classes of graphs on which the D ominating S et and C onnected D ominating S et problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. Moreover, for D ominating S et , a kernel of size k c ( H ) , where c ( H ) is a constant depending on the size of H , follows from a more general result on the kernelization of D ominating S et on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for D ominating S et on H -minor-free graphs. We answer this question in the affirmative and in fact prove a more general result. For C onnected D ominating S et no polynomial kernel even on H -minor-free graphs was known prior to our work. On the negative side, it is known that C onnected D ominating S et on 2-degenerated graphs does not admit a polynomial kernel unless coNP ⊆ NP/poly. Our kernelization algorithm is based on a non-trivial combination of the following ingredients • The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph H as a topological minor; • A novel notion of protrusions, different than the one defined in [FOCS 2009]; • Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is H -minor-free) of the problem, with treewidth O (√ k ). The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels. A protrusion in a graph [FOCS 2009] is a subgraph of constant treewidth which is separated from the rest of the graph by at most a constant number of vertices. In our variant of protrusions, instead of stipulating that the subgraph be of constant treewidth , we ask that it contains a constant number of vertices from a solution . We believe that this new take on protrusions would be useful for other graph problems and in different algorithmic settings.

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that n -variable m -clause SAT cannot be solved in time (2-ϵ) n m O (1) , we show that for any ϵ > 0: • I ndependent S et cannot be solved in time (2-ϵ) tw( G ) | V ( G )| O (1) , • D ominating S et cannot be solved in time (3-ϵ) tw( G ) | V ( G )| O (1) , • M ax C ut cannot be solved in time (2-ϵ) tw( G ) | V ( G )| O (1) , • O dd C ycle T ransversal cannot be solved in time (3-ϵ) tw( G ) | V ( G )| O (1) , • For any fixed q ≥ 3, q -C oloring cannot be solved in time ( q -ϵ) tw ( G ) | V ( G )| O (1) , • P artition I nto T riangles cannot be solved in time (2-ϵ) tw ( G ) | V ( G )| O (1) . Our lower bounds match the running times for the best known algorithms for the problems, up to the ϵ in the base.

In the S ubset F eedback V ertex S et (S ubset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T , referred to as terminals, and an integer k . The objective is to determine whether there exists a set of at most k vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the F eedback V ertex S et problem has received significant attention over the past few years. In fact, the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable. Using tools from graph minors,, Kawarabayashi and Kobayashi obtained an algorithm for S ubset FVS running in time O ( f ( k )ċ n 2 m ) [SODA 2012, JCTB 2012]. Independently, Cygan et al. [ICALP 2011, SIDMA 2013] designed an algorithm for S ubset FVS running in time 2 O ( k log k ) ċ n O (1) . More recently, Wahlström obtained the first single exponential time algorithm for S ubset FVS, running in time 4 k ċ n O (1) [SODA 2014]. While the 2 O ( k ) dependence on the parameter k is optimal under the Exponential Time Hypothesis, the dependence of this algorithm as well as those preceding it, on the input size is at least quadratic. In this article, we design the first linear time parameterized algorithms for S ubset FVS. More precisely, we obtain the following new algorithms for S ubset FVS. — A randomized algorithm for S ubset FVS running in time O (25.6 k ċ ( n + m )). — A deterministic algorithm for S ubset FVS running in time 2 O ( k log k ) ċ ( n + m ). Since it is known that assuming the Exponential Time Hypothesis, S ubset FVS cannot have an algorithm running in time 2 o ( k ) n O (1) , our first algorithm obtains the best possible asymptotic dependence on both the parameter as well as the input size. Both of our algorithms are based on “cut centrality,” in the sense that solution vertices are likely to show up in minimum size cuts between vertices sampled from carefully chosen distributions.

Given a 1.5-dimensional terrain T, also known as an x-monotone polygonal chain, the Terrain Guarding problem seeks a set of points of minimum size on T that guards all of the points on T. Here, we say that a point p guards a point q if no point of the line segment pq is strictly below T. The Terrain Guarding problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm [SODA 2005]. However, only in 2010 King and Krohn [SODA 2010] finally showed that Terrain Guarding is NP-hard. In spite of the remarkable developments in approximation algorithms for Terrain Guarding, next to nothing is known about its parameterized complexity. In particular, the most intriguing open questions in this direction ask whether it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this paper, we answer the first question affirmatively by developing an n^O(sqrt{k})-time algorithm for both Discrete Terrain Guarding and Continuous Terrain Guarding. We also make non-trivial progress with respect to the second question: we show that Discrete Orthogonal Terrain Guarding, a well-studied special case of Terrain Guarding, is fixed-parameter tractable.

The optimization version of the Unique Label Cover problem is at the heart of the Unique Games Conjecture which has played an important role in the proof of several tight inapproximability results. In recent years, this problem has been also studied extensively from the point of view of parameterized complexity. Cygan et al. [FOCS 2012] proved that this problem is fixed-parameter tractable (FPT) and Wahlström [SODA 2014] gave an FPT algorithm with an improved parameter dependence. Subsequently, Iwata, Wahlström and Yoshida [2014] proved that the edge version of Unique Label Cover can be solved in linear FPT-time. That is, there is an FPT algorithm whose dependence on the input-size is linear. However, such an algorithm for the node version of the problem was left as an open problem. In this paper, we resolve this question by presenting the first linear-time FPT algorithm for Node Unique Label Cover.

The family of judicious partitioning problems, introduced by Bollob\'as 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 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\'as 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 FPT (which also proves that JB is FPT).

The Cycle Packing problem asks whether a given undirected graph G=(V,E) contains k vertex-disjoint cycles. Since the publication of the classic Erdos-Posa theorem in 1965, this problem received significant scientific attention in the fields of Graph Theory and Algorithm Design. In particular, this problem is one of the first problems studied in the framework of Parameterized Complexity. The non-uniform 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 2^{O(k^2)}|V| using exponential space. In case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2^{O(k\log^2 k)}|V|-time (deterministic) algorithm using exponential space, which is a consequence of the Erdos-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 2^{o(k\log^2k)}|V|^{O(1)}, beating the bound 2^{O(k\log^2k)}\cdot |V|^{O(1)}, has been found. In light of this, it seems natural to ask whether the 2^{O(k\log^2k)}|V|^{O(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a 2^{O(k\log^2k/log log k})} |V|-time (deterministic) algorithm for Cycle Packing. In case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the known bound, our algorithm runs in time linear in |V|, and its space complexity is polynomial in the input size.

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 \subseteq 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 \cal 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_\ell be the family of graphs such that each graph in T_\ell can be made into a tree by deleting at most \ell edges. Thus, the problem we study is T_\ell-Contraction. We design an FPT algorithm for T_\ell-Contraction running in time O((\ncol)^{O(k + \ell)} * 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_\ell-Contraction of size O([k(k + 2\ell)] ^{(\lceil {\frac{\alpha}{\alpha-1}\rceil + 1)}}).

Given a graph G and a pair (\mathcal{F}_1,\mathcal{F}_2) of graph families, the function {\sf GDISJ}_{G,{\cal F}_1,{\cal F}_2} takes as input, two induced subgraphs G_1 and G_2 of G, such that G_1 \in \mathcal{F}_1 and G_2 \in \mathcal{F}_2 and returns 1 if V(G_1)\cap V(G_2)=\emptyset and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs of hereditary graph families. We show that the communication complexity of this function, when the two graph families are hereditary, is sublinear if and only if there are finitely many graphs in the intersection of these two families. Then, using concepts from parameterized complexity, we obtain nuanced upper bounds on the communication complexity of GDISJ_G,\cal F_1,\cal F_2. A concept related to communication protocols is that of a (\mathcal{F}_1,\mathcal{F}_2)-separating family of a graph G. A collection \mathcal{F} of subsets of V(G) is called a (\mathcal{F}_1,\mathcal{F}_2)-separating family} for G, if for any two vertex disjoint induced subgraphs G_1\in \mathcal{F}_1,G_2\in \mathcal{F}_2, there is a set F \in \mathcal{F} with V(G_1) \subseteq F and V(G_2) \cap F = \emptyset. Given a graph G on n vertices, for any pair (\mathcal{F}_1,\mathcal{F}_2) of hereditary graph families with sublinear communication complexity for GDISJ_G,\cal F_1,\cal F_2, we give an enumeration algorithm that finds a subexponential sized (\mathcal{F}_1,\mathcal{F}_2)-separating family. In fact, we give an enumeration algorithm that finds a 2^{o(k)}n^{\Oh(1)} sized (\mathcal{F}_1,\mathcal{F}_2)-separating family; where k denotes the size of a minimum sized set S of vertices such that V(G)\setminus S has a bipartition (V_1,V_2) with G[V_1] \in {\cal F}_1 and G[V_2]\in {\cal F}_2. We exhibit a wide range of applications for these separating families, to obtain combinatorial bounds, enumeration algorithms as well as exact and FPT algorithms for several problems.

Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset U ⊆ V (G) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size O(k161 log58 k), and asked whether one can design a kernel of size O(k10). While we do not completely resolve this question, we design a significantly smaller kernel of size O(k25 log14 k), inspired by the O(k2)-size kernel for Feedback Vertex Set. To obtain this result, we first design an O(opt-log2 n)-factor approximation algorithm for CVD, which is central to our kernelization procedure. Thus, we improve upon both the kernelization algorithm and the approximation algorithm of Jansen and Pilipczuk. Next, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution. We believe that this notion could be useful in designing kernels for other problems.

We consider the fundamental Matroid Theory problem of finding a circuit in a matroid spanning a set t of given terminal elements. For graphic matroids this corresponds to the problem of finding a simple cycle passing through a set of given terminal edges in a graph. The algorithmic study of the problem on regular matroids, a superclass of graphic matroids, was initiated by Gavenčiak, Král', and Oum [ICALP'12], who proved that the case of the problem with |T| = 2 is fixed-parameter tractable (FPT) when parameterized by the length of the circuit. We extend the result of Gavenciak, Král', and Oum by showing that for regular matroids the Minimum Spanning Circuit problem, deciding whether there is a circuit with at most ℓ elements containing T, is FPT parameterized by k = ℓ — |T|; the Spanning Circuit problem, deciding whether there is a circuit containing T, is FPT parameterized by |T|. We note that extending our algorithmic findings to binary matroids, a superclass of regular matroids, is highly unlikely: Minimum Spanning Circuit parameterized by ℓ is W[1]- hard on binary matroids even when |T| = 1. We also show a limit to how far our results can be strengthened by considering a smaller parameter. More precisely, we prove that Minimum Spanning Circuit parameterized by |T| is W[1]-hard even on cographic matroids, a proper subclass of regular matroids.

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial, but far from linear, time. Thus, our goal is to construct algorithms with running time of the form poly(k) · n or poly(k) · n log n, where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O(n1/c) for some small constant c. Our results include: an algorithm for computing the determinant and the rank of an n × n matrix using O(k3 · n) time and arithmetic operations;an algorithm for solving a system of linear equations using O(k3 · n) time and arithmetic operations;an O(k3 · n log n)-time randomized algorithm for finding the cardinality of a maximum matching in a graph;an O(k4 · nlog2 n)-time randomized algorithm for constructing a maximum matching in a graph;an O(k2 · n log n)-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we provide an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph G and integer k, runs in time O(k2 · n log n) and either correctly reports that the treewidth of G is larger than k, or constructs a tree decomposition of G of width O(k2). The above results stand in contrast with the recent work of Abboud et al. [SODA 2016], which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth.

The edit operation that contracts edges, which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of Parameterized Complexity. In this paper, we examine an important family of graphs, namely the family of split graphs, which in the context of edge contractions, is proven to be significantly less obedient than one might expect. Formally, given a graph G and an integer k, the Split Contraction problem asks whether there exists a subset X of edges of G such that G/X is a split graph and X has at most k elements. Here, G/X is the graph obtained from G by contracting edges in X. It was previously claimed that the Split Contraction problem is fixed-parameter tractable. However, we show that, despite its deceptive simplicity, it is W[1]-hard. Our main result establishes the following conditional lower bound: under the Exponential Time Hypothesis, the Split Contraction problem cannot be solved in time 2^(o(l^2)) * poly(n) where l is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the first tight lower bound of the form 2^(o(l^2)) * poly(n) for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest.

The rigidity of a matrix A for a target rank r over a field F is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in Computational Complexity Theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of Parameterized Complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of Parameterized Complexity. Naturally, given parameters r and k, the Matrix Rigidity problem asks whether the rigidity of A for the target rank r is at most k. We show that in case F equals the reals or F is any finite field, this problem is fixed-parameter tractable with respect to k+r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in Real Algebraic Geometry, which are not well known in Parameterized Complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of Matrix Rigidity, highlighting the different flavors of this problem.

In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions com- bine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size α-approximate kernel. Loosely speaking, a polynomial size α-approximate kernel is a polynomial time pre-processing algorithm that takes as input an instance (I, k) to a parameterized problem, and outputs another instance (I′,k′) to the same problem, such that |I′| + k′ ≤ kO(1). Additionally, for every c ≥ 1, a c-approximate solution s′ to the pre-processed instance (I′, k′) can be turned in polynomial time into a (c · α)-approximate solution s to the original instance (I,k).

We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$ or determines whether $G_1$ and $G_2$ are isomorphic. The running time of the algorithm on an $n$-vertex graph is $2^{\mathcal{O}(k^5\log k)}\cdot n^5$, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in $2^{\mathcal{O}(k^5\log k)}\cdot n^5$ time that, for a given graph $G$ on $n$ vertices, either concludes that the treewidth of $G$ is at least $k$ or (i) finds in an isomorphic-invariant way a graph $\mathfrak{c}(G)$ that is isomorphic to $G$; (ii) finds an isomorphism-invariant construction term---an algebraic expression that encodes $G$ together with a tree decomposition of $G$ of width less than $k$. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for $G_1$ and $G_2$ are equal.

We study the parameterized complexity of the directed variant of the classical Steiner Tree problem on various classes of directed sparse graphs. While the parameterized complexity of Steiner Tree parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of nonterminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs and hence unlikely to be fixed parameter tractable (FPT). The undirected Steiner Tree problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for Directed Steiner Tree (DST) on sparse graphs parameterized by the number of nonterminals in the solution tree. Specifically, we show that the problem is FPT on graphs excluding a topological minor but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is acyclic, then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible asymptotic running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for Dominating Set on sparse undirected graphs. These algorithms are asymptotically optimal. (An erratum is attached.)

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph $G$, a subset of vertices $T$ and a positive integer $k$ and the objective is to determine whether there exists a $k$-sized vertex subset that intersects every odd cycle containing a vertex from $T$. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a $k$-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [ Proceedings of SODA, 2012, pp. 1726--1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time $f(k)mn^3$ using the theory of graph minors, where $f$ is some function, and $n$ and $m$ denote the number of vertices and edges in the graph. However, the dependence of this function on $k$ is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on $k$ is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time $2^{\mathcal{O}(k^3\log k)}mn^2\log^2 n$, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of “generalized” important separators to reduce the subset version of this problem to the standard version of the problem.

A subfamily F′ of a set family F is said to q - represent F if for every A ∈ F and B of size q such that A ∩ B = ∅ there exists a set A′ ∈ F′ such that A′ ∩ B = ∅. Recently, we provided an algorithm that, for a given family F of sets of size p together with an integer q , efficiently computes a q -representative family F′ of F of size approximately (p+q p). In this article, we consider the efficient computation of q -representative families for product families F . A family F is a product family if there exist families A and B such that F = { A , ∪, B : A ∈ A , B ∈ B , A , ∩, B = ∅}. Our main technical contribution is an algorithm that, given A , B and q , computes a q -representative family F′ of F . The running time of our algorithm is sublinear in | F | for many choices of A , B , and q that occur naturally in several dynamic programming algorithms. We also give an algorithm for the computation of q -representative families for product families F in the more general setting where q -representation also involves independence in a matroid in addition to disjointness. This algorithm considerably outperforms the naive approach where one first computes F from A and B and then computes the q -representative family F′ from F . We give two applications of our new algorithms for computing q -representative families for product families. The first is a 3.8408 k n O (1) deterministic algorithm for the M ultilinear M onomial D etection ( k -M l D) problem. The second is a significant improvement of deterministic dynamic programming algorithms for “connectivity problems” on graphs of bounded treewidth.

The F -M inor -F ree D eletion problem asks, for a fixed set F and an input consisting of a graph G and integer k , whether k vertices can be removed from G such that the resulting graph does not contain any member of F as a minor. At FOCS 2012, Fomin et al. showed that the special case when F contains at least one planar graph has a kernel of size f ( F ) ċ k g ( F ) for some functions f and g . They left open whether this P lanar F -M inor -F ree D eletion problem has kernels whose size is uniformly polynomial, of the form f ( F ) ċ k c for some universal constant c . We prove that some P lanar F -M inor -F ree D eletion problems do not have uniformly polynomial kernels (unless NP ⊆ coNP/poly), not even when parameterized by the vertex cover number. On the positive side, we consider the problem of determining whether k vertices can be removed to obtain a graph of treedepth at most η. We prove that this problem admits uniformly polynomial kernels with O ( k 6 ) vertices for every fixed η.

A skew-symmetric graph ( D =( V , A ),σ) is a directed graph D with an involution σ on the set of vertices and arcs. Flows on skew-symmetric graphs have been used to generalize maximum flow and maximum matching problems on graphs, initially by Tutte and later by Goldberg and Karzanov. In this article, we introduce a separation problem, d -S kew -S ymmetric M ulticut , where we are given a skew-symmetric graph D , a family τ of d -size subsets of vertices, and an integer k . The objective is to decide whether there is a set X ⊑ A of k arcs such that every set J in the family has a vertex υ such that υ and σ(υ) are in different strongly connected components of D ′=( V ,A \ ( X ∪ σ( X )). In this work, we give an algorithm for d -S kew -S ymmetric M ulticut that runs in time O ((4 d ) k ( m + n +ℓ)), where m is the number of arcs in the graph, n is the number of vertices, and ℓ is the length of the family given in the input. This problem, apart from being independently interesting, also captures the main combinatorial difficulty of numerous classical problems. Our algorithm for d -S kew -S ymmetric M ulticut paves the way for the first linear-time parameterized algorithms for several problems. We demonstrate its utility by obtaining the following linear-time parameterized algorithms: — We show that A lmost 2-SAT is a special case of 1-S kew -S ymmetric M ulticut , resulting in an algorithm for A lmost 2-SAT that runs in time O (4 k k 4 ℓ), where k is the size of the solution and ℓ is the length of the input formula. Then, using linear-time parameter-preserving reductions to A lmost 2-SAT, we obtain algorithms for O dd C ycle T ransversal and E dge B ipartization that run in time O (4 k k 4 ( m + n )) and O (4 k k 5 ( m + n )), respectively, where k is the size of the solution, and m and n are the number of edges and vertices respectively. This resolves an open problem posed by Reed et al. and improves on the earlier almost-linear-time algorithm of Kawarabayashi and Reed. — We show that D eletion q-Horn B ackdoor S et D etection is a special case of 3-S kew -S ymmetric M ulticut , giving us an algorithm for D eletion q-Horn B ackdoor S et D etection that runs in time O (12 k k 5 ℓ), where k is the size of the solution and ℓ is the length of the input formula. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a work by Narayanaswamy et al. Using this result, we get an algorithm for S atisfiability that runs in time O (12 k k 5 ℓ), where k is the size of the smallest q-Horn deletion backdoor set, with ℓ being the length of the input formula.

A rectilinear Steiner tree for a set T of points in the plane is a tree which connects T using horizontal and vertical lines. In the Rectilinear Steiner Tree problem, input is a set T of n points in the Euclidean plane (R^2) and the goal is to find an rectilinear Steiner tree for T of smallest possible total length. A rectilinear Steiner arborecence for a set T of points and root r in T is a rectilinear Steiner tree S for T such that the path in S from r to any point t in T is a shortest path. In the Rectilinear Steiner Arborescense problem the input is a set T of n points in R^2, and a root r in T, the task is to find an rectilinear Steiner arborescence for T, rooted at r of smallest possible total length. In this paper, we give the first subexponential time algorithms for both problems. Our algorithms are deterministic and run in 2^{O(sqrt{n}log n)} time.

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: 1) A induces a subgraph of G of treewidth O(√(k log k)), and 2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2O(√k log2 k)· nO(1))-1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√(k log2k))nO(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include DIRECTED k-Path, WEIGHTED k-Path, VERTEX COVER LOCAL SEARCH, and SUBGRAPH ISOMORPHISM, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e. finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP subseteq coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of "constraints" that separate "kernelizable" from "non-kernelizable" variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a "global" relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a "local" relaxation parameter and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all t >= 1, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2^{c^{2}}*k^{7+c}*log^3(k)) whenever c in o(sqrt(k))). Thus the kernel size varies from being sub-exponential when c in o(sqrt(k)), to quasipolynomial when c in o(log^l(k)), l in R_+, and polynomial when c in O(1). We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever t in O(k^{epsilon}), for any 0 <= epsilon < 1.

In this paper we consider Simultaneous Feedback Edge Set (Sim-FES) problem. In this problem, the input is an $n$-vertex graph $G$, an integer $k$ and a coloring function ${\sf col}: E(G) \rightarrow 2^{[α]}$ and the objective is to check whether there is an edge subset $S$ of cardinality at most $k$ in $G$ such that for all $i \in [α]$, $G_i - S$ is acyclic. Here, $G_i=(V(G), \{e\in E(G) \mid i \in {\sf col}(e)\})$ and $[α]=\{1,\ldots,α\}$. When $α=1$, the problem is polynomial time solvable. We show that for $α=3$ Sim-FES is NP-hard by giving a reduction from Vertex Cover on cubic graphs. The same reduction shows that the problem does not admit an algorithm of running time $O(2^{o(k)}n^{O(1)})$ unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time $O(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 the problem Maximum Simultaneous Acyclic Subgraph. Here, the input is a graph $G$, an integer $q$ and, a coloring function ${\sf col}: E(G) \rightarrow 2^{[α]}$. The question is whether there is a edge subset $F$ of cardinality at least $q$ in $G$ such that for all $i\in [α]$, $G[F_i]$ is acyclic. Here, $F_i=\{e \in F \mid i \in \textsf{col}(e)\}$. We give an FPT algorithm for running in time $O(2^{ωq α}n^{O(1)})$.

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 of size at most k such that F = D - S is a directed acyclic digraph. In a recent paper, 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 some light on the kernelization complexity of the DFVS problem, a well known open problem in the area of Parameterized Complexity. In this article, 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.

In this paper we study the "independent" version of the classic Feedback Vertex Set problem in the realm of parameterized algorithms and moderately exponential time algorithms. More precisely, we study the Independent Feedback Vertex Set problem, where we are given an undirected graph G on n vertices and a positive integer k, and the objective is to check if there is an independent feedback vertex set of size at most k. A set S subseteq V(G) is called an independent feedback vertex set (ifvs) if S is an independent set and G\S is a forest. In this paper we design two deterministic exact algorithms for Independent Feedback Vertex Set with running times O*(4.1481^k) and O*(1.5981^n). In fact, the algorithm with O*(1.5981^n) running time finds the smallest sized ifvs, if an ifvs exists. Both the algorithms are based on interesting measures and improve the best known algorithms for the problem in their respective domains. In particular, the algorithm with running time O*(4.1481^k) is an improvement over the previous algorithm that ran in time O*(5^k). On the other hand, the algorithm with running time O*(1.5981^n) is the first moderately exponential time algorithm that improves over the naive algorithm that enumerates all the subsets of V(G). Additionally, we show that the number of minimal ifvses in any graph on n vertices is upper bounded by 1.7485^n.

For fixed integers r,l >= 0, a graph G is called an (r,l)-graph if the vertex set V(G) can be partitioned into r independent sets and l cliques. Such a graph is also said to have cochromatic number r+l. The class of (r,l) graphs generalizes r-colourable graphs (when l=0) and hence not surprisingly, determining whether a given graph is an (r,l)-graph is NP-hard even when r >= 3 or l >= 3 in general graphs. When r and ell are part of the input, then the recognition problem is NP-hard even if the input graph is a perfect graph (where the Chromatic Number problem is solvable in polynomial time). It is also known to be fixed-parameter tractable (FPT) on perfect graphs when parameterized by r and l. I.e. there is an f(r+l) n^O(1) algorithm on perfect graphs on n vertices where f is a function of r and l. Observe that such an algorithm is unlikely on general graphs as the problem is NP-hard even for constant r and l. In this paper, we consider the parameterized complexity of the following problem, which we call Vertex Partization. Given a perfect graph G and positive integers r,l,k decide whether there exists a set S subset or equal to V(G) of size at most k such that the deletion of S from G results in an (r,l)-graph. This problem generalizes well studied problems such as Vertex Cover (when r=1 and l=0), Odd Cycle Transversal (when r=2, l=0) and Split Vertex Deletion (when r=1=l). 1. Vertex Partization on perfect graphs is FPT when parameterized by k+r+l. 2. The problem, when parameterized by k+r+l, does not admit any polynomial sized kernel, under standard complexity theoretic assumptions. In other words, in polynomial time, the input graph cannot be compressed to an equivalent instance of size polynomial in k+r+l. In fact, our result holds even when k=0. 3. When r,ell are universal constants, then Vertex Partization on perfect graphs, parameterized by k, has a polynomial sized kernel.

For a family of graphs F, a graph G, and a positive integer k, the F-DELETION problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-DELETION generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A graph G = (V, cup_{i=1}^{alpha} E_{i}), where the edge set of G is partitioned into alpha color classes, is called an alpha-edge-colored graph. A natural extension of the F-DELETION problem to edge-colored graphs is the alpha-SIMULTANEOUS F-DELETION problem. In the latter problem, we are given an alpha-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph G_i\S, where G_i = (V, E_i) and 1 <= i <= alpha, is in F. In this work, we study alpha-SIMULTANEOUS F-DELETION for F being the family of forests. In other words, we focus on the alpha-SIMULTANEOUS FEEDBACK VERTEX SET (alpha-SIMFVS) problem. Algorithmically, we show that, like its classical counterpart, alpha-SIMFVS parameterized by k is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant alpha. In particular, we give an algorithm running in 2^{O(alpha * k)} * n^{O(1)} time and a kernel with O(alpha * k^{3(alpha + 1)}) vertices. The running time of our algorithm implies that alpha-SIMFVS is FPT even when alpha in o(log(n)). We complement this positive result by showing that for alpha in O(log(n)), where n is the number of vertices in the input graph, alpha-SIMFVS becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).

In the EDGE EDITING TO CONNECTED f-DEGREE GRAPH problem we are given a graph G, an integer k and a function f assigning integers to vertices of G. The task is to decide whether there is a connected graph F on the same vertex set as G, such that for every vertex v, its degree in F is f(v) and the number of edges inthe symmetric difference of E(G) and E(F), is at most k. We show that EDGE EDITING TO CONNECTED f-DEGREE GRAPH is fixed-parameter tractable (FPT) by providing an algorithm solving the problem on an n-vertex graph in time 2^{O(k)}n^{O(1)}. Our FPT algorithm is based on a non-trivial combination of color-coding and fast computations of representative families over direct sum matroid of l-elongation of co-graphic matroid associated with G and uniform matroid over the set of non-edges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing problems.

We give a new general approach for designing exact exponential-time algorithms for subset problems . In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is W EIGHTED d -SAT. Here, the input is a CNF-formula with clauses of size at most d , and an integer W . The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on “monotone local search,” where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem, we are also given as input a subset X of the universe and an integer k . The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c k n O(1) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O ((2−1/ c ) n ). In many cases, the extension problem can be reduced to simply finding a solution of size at most k . Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including d -H ITTING S ET , F EEDBACK V ERTEX S ET , N ODE U NIQUE L ABEL C OVER , and W EIGHTED d -SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential-time algorithms. We also show how to derandomize our algorithms at the cost of a subexponential multiplicative factor in the running time. Our derandomization is based on an efficient construction of a new pseudo-random object that might be of independent interest. Finally, we extend our methods to establish new combinatorial upper bounds and develop enumeration algorithms.

In a parameterized problem, every instance I comes with a positive integer k . The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k while preserving the answer. In this work, we give two meta-theorems on kernelization. The first theorem says that all problems expressible in counting monadic second-order logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.

Let M =( E , I ) be a matroid and let S ={ S 1 , ċ , S t } be a family of subsets of E of size p . A subfamily Ŝ ⊆ S is q - representative for S if for every set Y ⊆ E of size at most q , if there is a set X ∈ S disjoint from Y with X ∪ Y ∈ I , then there is a set Xˆ ∈ Ŝ disjoint from Y with Xˆ ∪ Y ∈ I . By the classic result of Bollobás, in a uniform matroid, every family of sets of size p has a q -representative family with at most ( p + q p ) sets. In his famous “two families theorem” from 1977, Lovász proved that the same bound also holds for any matroid representable over a field F. We give an efficient construction of a q -representative family of size at most ( p + q p ) in time bounded by a polynomial in ( p + q p ), t , and the time required for field operations. We demonstrate how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include the following: —In the L ong D irected C ycle problem, the input is a directed n -vertex graph G and the positive integer k . The task is to find a directed cycle of length at least k in G , if such a cycle exists. As a consequence of our 6.75 k + o ( k ) n O (1) time algorithm, we have that a directed cycle of length at least log n , if such a cycle exists, can be found in polynomial time. —In the M inimum E quivalent G raph (MEG) problem, we are seeking a spanning subdigraph D ′ of a given n -vertex digraph D with as few arcs as possible in which the reachability relation is the same as in the original digraph D . —We provide an alternative proof of the recent results for algorithms on graphs of bounded treewidth showing that many “connectivity” problems such as H amiltonian C ycle or S teiner T ree can be solved in time 2 O ( t ) n on n -vertex graphs of treewidth at most t . For the special case of uniform matroids on n elements, we give a faster algorithm to compute a representative family. We use this algorithm to provide the fastest known deterministic parameterized algorithms for k -P ath , k -T ree , and, more generally, k -S ubgraph I somorphism , where the k -vertex pattern graph is of constant treewidth.

An instance of the $(n-k)$-Set Cover or the $(n-k)$-Test Cover problems is of the form $(\mathcal{U},\mathcal{S},k)$, where $\mathcal{U}$ is a set with $n$ elements, $\mathcal{S}\subseteq 2^\mathcal{U}$ with $|\mathcal{S}|=m$, and $k$ is the parameter. The instance is a Yes-instance of $(n-k)$-Set Cover if and only if there exists $\mathcal{S}'\subseteq\mathcal{S}$ with $|\mathcal{S}'|\leq n-k$ such that every element of $\mathcal{U}$ is contained in some set in $\mathcal{S}'$. Similarly, it is a Yes-instance of $(n-k)$-Test Cover if and only if there exists $\mathcal{S}'\subseteq\mathcal{S}$ with $|\mathcal{S}'|\leq n-k$ such that for any pair of elements from $\mathcal{U}$, there exists a set in $\mathcal{S}'$ that contains one of them but not the other. It is known in the literature that both $(n-k)$-Set Cover and $(n-k)$-Test Cover do not admit polynomial kernels (under some well-known complexity theoretic assumptions). However, in this paper we show that they do admit “partially polynomial kernels”: we give polynomial time algorithms that take as input an instance $(\mathcal{U},\mathcal{S},k)$ of $(n-k)$-Set Cover (respectively, $(n-k)$-Test Cover) and return an equivalent instance $(\tilde{\mathcal{U}},\tilde{\mathcal{S}}, \tilde{k})$ of $(n-k)$-Set Cover (respectively, $(n-k)$-Test Cover) with $\tilde{k} \leq k$ and $| \tilde{\mathcal{U}}|= \mathcal{O}(k^2)$ (respectively, $|\tilde{\mathcal{U}}|=\mathcal{O}(k^7)$). These results allow us to generalize, improve, and unify several results known in the literature. For example, these immediately imply traditional kernels when input instances satisfy certain “sparsity properties.” Using a part of our partial kernelization algorithm for $(n-k)$-Set Cover, we also get an improved fixed-parameter tractable algorithm for this problem which runs in time $\mathcal{O}(4^kk^{\mathcal{O}(1)}(m+n)+mn)$ improving over the previous best of $\mathcal{O}(8^{k+o(k)}(m+n)^{\mathcal{O}(1)})$. On the other hand, the partially polynomial kernel for $(n-k)$-Test Cover gives an algorithm with running time $\mathcal{O}(2^{\mathcal{O}(k^2)}(m+n)^{\mathcal{O}(1)})$. We believe such an approach could also be useful for other covering problems.

We study a general class of problems called $\mathcal{F}$-Deletion problems. In an $\mathcal{F}$-Deletion problem, we are asked whether a subset of at most $k$ vertices can be deleted from a graph $G$ such that the resulting graph does not contain as a minor any graph from the family ${\cal F}$ of forbidden minors. We study the problem parameterized by $k$, using $p$-$\mathcal{F}$-Deletion to refer to the parameterized version of the problem. We obtain a number of algorithmic results on the $p$-$\mathcal{F}$-Deletion problem when $\mathcal{F}$ contains a planar graph. We give a linear vertex kernel on graphs excluding $t$-claw $K_{1,t}$, the star with $t$ leaves, as an induced subgraph, where $t$ is a fixed integer and an approximation algorithm achieving an approximation ratio of $O(\log^{3/2} OPT)$, where $OPT$ is the size of an optimal solution on general undirected graphs. Finally, we obtain polynomial kernels for the case when $\cal F$ only contains graph $\theta_c$ as a minor for a fixed integer $c$. The graph $\theta_c$ consists of two vertices connected by $c$ parallel edges. Even though this may appear to be a very restricted class of problems it already encompasses well-studied problems such as Vertex Cover, Feedback Vertex Set, and Diamond Hitting Set. The generic kernelization algorithm is based on a nontrivial application of protrusion techniques, previously used only for problems on topological graph classes.

In the Tree Deletion Set problem the input is a graph $G$ together with an integer $k$. The objective is to determine whether there exists a set $S$ of at most $k$ vertices such that $G\setminus S$ is a tree. The problem is \tt NP-complete and even \tt NP-hard to approximate within any factor of $\text{OPT}^c$ for any constant $c$. In this paper we give an $\mathcal{O}(k^5)$ size kernel for the Tree Deletion Set problem. An appealing feature of our kernelization algorithm is a new reduction rule, based on systems of linear equations, that we use to handle the instances on which Tree Deletion Set is hard to approximate.

The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial exponential time algorithms have been found for a myriad of problems, including G raph C oloring , H amiltonian P ath , D ominating S et , and 3-CNF-S at . In some instances, improving these algorithms further seems to be out of reach. The CNF-S at problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O (2 n ), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-S at that run in time o (2 n ), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵ < 1, there is a (large) integer k such that k -CNF-S at cannot be computed in time 2 ϵ n . In this article, we show that, for every ϵ < 1, the problems H itting S et , S et S plitting , and NAE-S at cannot be computed in time O (2 ϵ n ) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for S et C over and prove that, under this assumption, the fastest known algorithms for S teiner T ree , C onnected V ertex C over , S et P artitioning , and the pseudo-polynomial time algorithm for S ubset S um cannot be significantly improved. Finally, we justify our assumption about the hardness of S et C over by showing that the parity of the number of solutions to S et C over cannot be computed in time O (2 ϵ n ) for any ϵ < 1 unless SETH fails.

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [CSL-LICS'14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula φ, and determines whether φ holds on P in time f(φ, w) · n2.

Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on $n$ vertices and a positive integer parameter $k$, find if there exist $k$ edges (arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees---where the resulting graph is \emph{Eulerian}---the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al. [\emph{Algorithmica, 2014}] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time $2^{O(k \log k)}n^{O(1)}$. They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. In this paper we answer their question in the affirmative: using the technique of computing \emph{representative families of co-graphic matroids} we design algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.

Let $$M=(E,\mathcal{I})$$ be a matroid. A $$k$$ -truncation of $$M$$ is a matroid $$M'=(E,\mathcal{I}')$$ such that for any $$A\subseteq E$$ , $$A\in \mathcal{I}'$$ if and only if $$|A|\le k$$ and $$A\in \mathcal {I}$$ . Given a linear representation of $$M$$ we consider the problem of finding a linear representation of the $$k$$ -truncation of this matroid. This problem can be expressed as the following problem on matrices. Let $$M$$ be a $$n\times m$$ matrix over a field $$\mathbb {F}$$ . A rank $$k$$ -truncation of the matrix $$M$$ is a $$k\times m$$ matrix $$M_k$$ (over $${\mathbb F}$$ or a related field) such that for every subset $$I\subseteq \{1,\ldots ,m\}$$ of size at most $$k$$ , the set of columns corresponding to $$I$$ in $$M$$ has rank $$|I|$$ if and only if the corresponding set of columns in $$M_k$$ has rank $$|I|$$ . A common way to compute a rank $$k$$ -truncation of a $$n \times m$$ matrix is to multiply the matrix with a random $$k\times n$$ matrix (with the entries from a field of an exponential size), yielding a simple randomized algorithm. So a natural question is whether it possible to obtain a rank $$k$$ -truncation of a matrix, deterministically. In this paper we settle this question for matrices over any field in which the field operations can be done efficiently. This includes any finite field and the field of rationals ( $$\mathbb Q$$ ). Our algorithms are based on the properties of the classical Wronskian determinant, and the folded Wronskian determinant, which was recently introduced by Guruswami and Kopparty [ FOCS, 2013 ], and was implicitly present in the work of Forbes and Shpilka [ STOC, 2012 ]. These were used in the context of subspace designs, and reducing randomness for polynomial identity testing and other related problems. Our main conceptual contribution in this paper is to show that the Wronskian determinant can also be used to obtain a representation of the truncation of a linear matroid in deterministic polynomial time. Finally, we use our results to derandomize several parameterized algorithms, including an algorithm for computing $$\ell $$ -Matroid Parity, to which several problems like $$\ell $$ -Matroid Intersection can be reduced.

Let F be a family of graphs. Given an input graph G and a positive integer k, testing whether G has a k-sized subset of vertices S, such that G\S belongs to F, is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when F is either a family of cactus graphs or a family of odd-cactus graphs. A graph H is called a cactus graph if every pair of cycles in H intersect on at most one vertex. Furthermore, a cactus graph H is called an odd cactus, if every cycle of H is of odd length. Let us denote by C and C_{odd}, families of cactus and odd cactus, respectively. The vertex deletion problems corresponding to C and C_{odd} are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with running time 12^{k}*n^{O(1)} for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them.

Vertex Cover is one of the most well studied problems in the realm of parameterized algorithms and admits a kernel with O(l^2) edges and 2*l vertices. Here, l denotes the size of a vertex cover we are seeking for. A natural question is whether Vertex Cover admits a polynomial kernel (or a parameterized algorithm) 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(f^3), 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 sized kernel. The input to our problem consists of an undirected graph G, S \subseteq V(G) such that |S| = k and G[V(G)\S] has maximum degree at most 2 and a positive integer l. Given (G,S,l), in polynomial time we output an instance (G',S',l') such that |V(G')|<= O(k^5), |E(G')|<= O(k^6) and G has a vertex cover of size at most l if and only if G' has a vertex cover of size at most l'. When G[V(G)\S] has maximum degree at most 1, we improve the known kernel bound from O(k^3) vertices to O(k^2) vertices (and O(k^3) edges). In general, if G[V(G)\S] is simply a collection of cliques of size at most d, then we transform the graph in polynomial time to an equivalent hypergraph with O(k^d) vertices and show that, for d >= 3, a kernel with O(k^{d-epsilon}) vertices is unlikely to exist for any epsilon >0 unless NP is a subset of coNO/poly.

The b-chromatic number of a graph G, chi_b(G), is the largest integer k such that G has a k-vertex coloring with the property that each color class has a vertex which is adjacent to at least one vertex in each of the other color classes. In the B-Chromatic Number problem, the objective is to decide whether chi_b(G) >= k. Testing whether chi_b(G)=Delta(G)+1, where Delta(G) is the maximum degree of a graph, itself is NP-complete even for connected bipartite graphs (Kratochvil, Tuza and Voigt, WG 2002). In this paper we study B-Chromatic Number in the realm of parameterized complexity and exact exponential time algorithms. We show that B-Chromatic Number is W[1]-hard when parameterized by k, resolving the open question posed by Havet and Sampaio (Algorithmica 2013). When k=Delta(G)+1, we design an algorithm for B-Chromatic Number running in time 2^{O(k^2 * log(k))}*n^{O(1)}. Finally, we show that B-Chromatic Number for an n-vertex graph can be solved in time O(3^n * n^{4} * log(n)).

A backdoor set of a CNF formula is a set of variables such that fixing the truth values of the variables from this set moves the formula into a polynomial-time de-cidable class. In this work we obtain several algorithmic results for solving d-SAT, by exploiting backdoors to d-CNF formulas whose incidence graphs have small treewidth. For a CNF formula ϕ and integer t, a strong backdoor set to treewidth t is a set of variables such that each possible partial assignment τ to this set reduces ϕ to a formula whose incidence graph is of treewidth at most t. A weak backdoor set to treewidth t is a set of variables such that there is a partial assignment to this set that reduces ϕ to a satisfiable formula of treewidth at most t. Our main contribution is an algorithm that, given a d-CNF formula ϕ and an integer k, in time , either finds a satisfying assignment of ϕ, or reports correctly that ϕ is not satisfiable, or concludes correctly that ϕ has no weak or strong backdoor set to treewidth t of size at most k. As a consequence of the above, we show that d-SAT parameterized by the size of a smallest weak/strong backdoor set to formulas of treewidth t, is fixed-parameter tractable. Prior to our work, such results were know only for the very special case of t = 1 (Gaspers and Szeider, ICALP 2012). Our result not only extends the previous work, it also improves the running time substantially. The running time of our algorithm is linear in the input size for every fixed k. Moreover, the exponential dependence on the parameter k is asymptotically optimal under Exponential Time Hypothesis (ETH). One of our main technical contributions is a linear time “protrusion replacer” improving over a (n log2 n)-time procedure of Fomin et al. (FOCS 2012). The new deterministic linear time protrusion replacer has several applications in kernelization and parameterized algorithms.