We study a Stackelberg variant of the classical Most Vital Links problem, modeled as a one-round adversarial game between an attacker and a defender. The attacker strategically removes up to k edges from a flow network to maximally disrupt flow between a source s and a sink t, after which the defender optimally reroutes the remaining flow. To capture this attacker–defender interaction, we introduce a new mathematical model of discounted cuts, in which the cost of a cut is evaluated by excluding its k most expensive edges. This model generalizes the Most Vital Links problem and uncovers novel algorithmic and complexity-theoretic properties. We develop a unified algorithmic framework for analyzing various forms of discounted cut problems, including minimizing or maximizing the cost of a cut under discount mechanisms that exclude either the k most expensive or the k cheapest edges. While most variants are NP-complete on general graphs, our main result establishes polynomial-time solvability for all discounted cut problems in our framework when the input is restricted to bounded-genus graphs, a relevant class that includes many real-world networks such as transportation and infrastructure networks. With this work, we aim to open collaborative bridges between artificial intelligence, algorithmic game theory, and operations research.

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.

We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum s-t cuts C_1, …, C_k such that for any i,j ∈ [k], the number of edges in the symmetric difference C_i △ C_j is at least d. For d ∈ {1,2}, the problem corresponds to counting minimum s-t cuts in G, which is #P-complete [Provan and Ball, SICOMP 1983]. The problem is also known to be NP-complete already for k = 3 [de Berg, López Martínez, Spieksma, ISAAC 2024]. Our main result shows that the problem is fixed-parameter tractable (FPT) when parameterized by the combined parameter k + d. The main ingredients of our FPT algorithm build on novel structural properties of diverse minimum s-t cuts and a non-trivial application of the flow-augmentation technique of Kim, Kratsch, Pilipczuk, and Wahlström [JACM 2025].

Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational biology. Two fundamental aggregation tasks are the center and median problems, which minimize the maximum and the total distance to the input permutations, respectively. While these problems are well understood under Kendall’s tau and related distances, their parameterized complexity under the Ulam metric, an edit-distance-based metric on permutations, has remained largely unexplored. In this work, we initiate a systematic study of the parameterized complexity of rank aggregation under the Ulam metric. We consider both the center and median problems, as well as their generalizations to the k-center and k-median clustering settings, parameterized by the number of centers k and the distance budget d (corresponding to the maximum distance for center variants and the total distance for median variants). Both problems are known to be NP-hard already for k = 1. We show that the Ulam k-center problem remains NP-hard when d = 1, but is fixed-parameter tractable when parameterized by k + d. Our algorithm is based on a novel local-search framework tailored to the non-local nature of Ulam distances. We complement this by proving that no polynomial kernel exists for the k+d parameterization unless NP ⊆ coNP/poly. For the Ulam k-median problem parameterized by the total distance d, we establish W[1]-hardness and provide an XP algorithm. We also provide a polynomial kernel for the parameter k + d, which in turn yields a fixed-parameter tractable algorithm.

The induced matching width of a tree decomposition of a graph \(G\) is the cardinality of a largest induced matching \(M\) of \(G\), such that there exists a bag that intersects every edge in \(M\). The induced matching treewidth of \(G\), denoted by tree-\(\mu(G)\), is the minimum induced matching width of a tree decomposition of \(G\). The parameter tree-\(\mu\) was introduced by Yolov [SODA ’18], who showed that, for example, Maximum-Weight Independent Set can be solved in polynomial-time on graphs of bounded tree-\(\mu\). Lima, Milanič, Muršič, Okrasa, Rzążewski, and Šorgel [ESA ’24] conjectured that this algorithm can be generalized to a meta-problem called Maximum-Weight Induced Subgraph of Bounded Treewidth, where we are given a vertex-weighted graph \(G\), an integer \(w\), and a \(\mathsf{CMSO_2}\)-sentence \(\Phi\), and are asked to find a maximum-weight set \(X \subseteq V(G)\) so that \(G[X]\) has treewidth at most \(w\) and satisfies \(\Phi\). They proved the conjecture for some special cases, such as for the problem Maximum-Weight Induced Forest.

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

We introduce a series of graph decompositions based on the modulator/target scheme of modification problems that enable several algorithmic applications that parametrically extend the algorithmic potential of planarity. In the core of our approach is a polynomial time algorithm for computing planar \(\mathcal{H}\)-modulators. Given a graph class \(\mathcal{H}\), a planar \(\mathcal{H}\)-modulator of a graph \(G\) is a set \(X \subseteq V(G)\) such that the “torso” of \(X\) is planar and all connected components of \(G-X\) belong to \(\mathcal{H}\). Here, the torso of \(X\) is obtained from \(G[X]\) if, for every connected component of \(G-X\), we form a clique out of its neighborhood on \(G[X]\). We introduce \(\mathcal{H}\)-Planarity as the problem of deciding whether a graph \(G\) has a planar \(\mathcal{H}\)-modulator. We prove that, if \(\mathcal{H}\) is hereditary, CMS0-definable, and decidable in polynomial time, then \(\mathcal{H}\)-Planarity is solvable in polynomial time.

The question of "what can be computed locally?" lies at the heart of distributed computing in networks. As established in Naor and Stockmeyer's seminal paper (STOC 1993, Edsger W. Dijkstra Prize in Distributed Computing 2025), this question is undecidable, even for graph problems whose solutions can be checked locally. In this paper, we adopt a novel perspective on the question, by asking for which classes Π of problems, and for which classes G of graphs, all problems in Π can be solved efficiently in a distributed manner in all graphs of G. This paper focuses on two natural candidates for such an approach, namely the class of problems expressible in first-order logic (FO), because they possess an intrinsic form of locality thanks to Gaifman's theorem, and the class of graphs with bounded expansion, because they form a large class of graphs encompassing, e.g., planar, bounded-genus, bounded-treewidth, and bounded-degree graphs, as well as graphs excluding a fixed minor or topological minor, sparse Erdös--Rényi graphs (a.a.s.), and several network models such as stochastic block models for suitable parameter ranges.

The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth’s theorem on posets and Kőnig’s theorem on matchings in bipartite graphs. The theorem asserts that for every graph G, the vertex set of G can be partitioned into at most α(G) vertex-disjoint paths, where α(G) is the maximum size of an independent set in G. The proof of the Gallai-Milgram theorem is constructive and yields a polynomial-time algorithm that computes a covering of G by at most α(G) vertex-disjoint paths. While the Gallai-Milgram theorem is tight—there are graphs where one really needs α(G) paths, not fewer, to cover the vertex set of G—it was not known prior to our work whether deciding if a graph G could be covered by fewer than α(G) vertex-disjoint paths can be done in polynomial time. We resolve this question by proving the following algorithmic extension of the Gallai–Milgram theorem for undirected graphs: There is an algorithm that, for an n-vertex graph G and an integer parameter k ≥ 1, runs in time 22O(k4logk) · nO(1) and outputs a path cover P of G together with either a correct conclusion that P is a minimum-size path cover or an independent set of size |P| + k, certifying that P contains at most α(G) − k paths. Thus, for k ∈ O((loglogn)1/4−ε) our algorithm runs in polynomial time, and either computes a minimum-size path cover of G, or finds a path cover of size at most α(G) − k. We find the existence of such an algorithm quite surprising for the following reason. The problems of computing a path cover and a maximum independent set are both notoriously hard, yet our algorithm either solves one of them or provides meaningful information about the other. The proof of our algorithmic extension of the Gallai–Milgram theorem is non-trivial and builds on several novel algorithmic ideas. One of the key subroutines in our algorithm is an FPT algorithm, parameterized by α(G), for deciding whether G contains a Hamiltonian path. This result is of independent interest—prior to our work, no polynomial-time algorithm for deciding Hamiltonicity was known, even for graphs with independence number at most three. Moreover, the algorithmic techniques we develop apply to a wide array of problems in undirected graphs, including Hamiltonian Cycle, Path Cover, Largest Linkage, and Topological Minor Containment. We show that all these problems are FPT when parameterized by the independence number of the graph. Notably, the independence-number parameterization departs from the typical direction of research in parameterized complexity. First, α(G) measures a graph’s density, whereas most prior work in the area focuses on parameters describing sparsity, such as treewidth or vertex cover. Second, most structural parameters studied in parameterized complexity can be computed exactly or well-approximated in polynomial or even FPT time, whereas computing α(G) is notoriously difficult from almost any computational perspective. The fact that it can nevertheless serve as the basis for efficient parameterization is particularly striking.

Abstract We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the model. To our knowledge, this marks the first meta-theorem regarding distributed model checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph G has a clique of size k , whether it admits a coloring with k colors, whether it contains a graph H as a subgraph or minor, or whether terminal vertices in G could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. (in: 41st ACM Symposium on Principles of Distributed Computing (PODC), 2022), which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.

Abstract We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths . In this problem, the input is an edge-weighted (directed or undirected) n -vertex graph G along with k terminal pairs $$(s_1,t_1),(s_2,t_2),\ldots ,(s_k,t_k)$$ ( s 1 , t 1 ) , ( s 2 , t 2 ) , … , ( s k , t k ) . The task is to connect as many terminal pairs as possible by pairwise vertex-disjoint paths such that each path is a shortest path between the respective terminals. Our work is anchored in the recent breakthrough by Lochet [SODA ’21], which demonstrates the polynomial-time solvability of the problem for a fixed value of k . Lochet’s result implies the existence of a polynomial-time ck -approximation for Maximum Vertex-Disjoint Shortest Paths , where $$c \le 1$$ c ≤ 1 is a constant. (One can guess 1/ c terminal pairs to connect in $$k^{O({1}/{c})}$$ k O ( 1 / c ) time and then utilize Lochet’s algorithm to compute the solution in $$n^{f({1}/{c})}$$ n f ( 1 / c ) time.) Our first result suggests that this approximation algorithm is, in a sense, the best we can hope for. More precisely, assuming the gap-ETH, we exclude the existence of an o ( k )-approximation within $$f(k){{\,\textrm{poly}\,}}(n)$$ f ( k ) poly ( n ) time for any function f that only depends on k . Our second result demonstrates the infeasibility of achieving an approximation ratio of $$m^{{1}/{2}-\varepsilon }$$ m 1 / 2 - ε in polynomial time, unless P $$=$$ = NP. We also show that this bound is tight by providing a simple $$\sqrt{\ell }$$ ℓ -approximation algorithm, where $$\ell $$ ℓ

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.

The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP -hard graph problems, like maximum-weight independent set, can be solved in time \(n^{\mathcal{O}(k)}\) if the input \( n \) -vertex graph is given together with a tree decomposition of independence number \( k \) . Yolov, in SODA 2018, gave an algorithm that, given an \( n \) -vertex graph \( G \) and an integer \( k \) , in time \(n^{\mathcal{O}(k^{3})}\) either constructs a tree decomposition of \( G \) whose independence number is \(\mathcal{O}(k^{3})\) or correctly reports that the tree-independence number of \( G \) is larger than \( k \) . In this article, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time \(2^{\mathcal{O}(k^{2})}n^{\mathcal{O}(k)}\) and either outputs a tree decomposition of \( G \) with independence number at most \(8k\) or determines that the tree-independence number of \( G \) is larger than \( k \) . This implies \(2^{\mathcal{O}(k^{2})}n^{\mathcal{O}(k)}\) -time algorithms for various problems, like maximum-weight independent set, parameterized by the tree-independence number \( k \) without needing the decomposition as an input. Assuming Gap-ETH, an \(n^{\Omega(k)}\) factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP -hard: We show that for every constant \(k\geq 4\) it is NP -complete to decide whether a given graph has the tree-independence number at most \( k \) .

According to the classic Chvátal’s Lemma from 1977, a graph \( G \) of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvátal’s Lemma: For any \( n \) -vertex graph \( G \) , an integer \( k \) , and a tree \( T \) on at most \(\delta(G)+k\) vertices, deciding whether \( G \) contains a subgraph isomorphic to \( T \) can be done in time \(f(k)\cdot n^{\mathcal{O}(1)}\) for some function \( f \) of \( k \) only. The proof is based on an intricate interplay between extremal graph theory and parameterized algorithms.

In the problem Fault-Tolerant Path ( FTP ), we are given an edge-weighted directed graph G = ( V , E ) , a subset U ⊆ E of vulnerable edges, two vertices s, t ∈ V , and integers k and ℓ. The task is to decide whether there exists a subgraph H of G with total cost at most ℓ such that, after the removal of any k vulnerable edges, H still contains an s − t -path. We study whether Fault-Tolerant Path is fixed-parameter tractable (FPT) and whether it admits a polynomial kernel under various parameterizations. Our choices of parameters include: the number of vulnerable edges in the input graph, the number of safe (i.e, invulnerable) edges in the input graph, the budget ℓ, the minimum number of safe edges in any optimal solution, the minimum number of vulnerable edges in any optimal solution, the required redundancy k , and natural above- and below-guarantee parameterizations. We provide an almost complete description of the complexity landscape of FTP for these parameters.

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.

We investigate the problem of constructing fault-tolerant bases in matroids. Given a matroid M and a redundancy parameter k, a k-fault-tolerant basis is a minimum-size set of elements such that, even after the removal of any k elements, the remaining subset still spans the entire ground set. Since matroids generalize linear independence across structures such as vector spaces, graphs, and set systems, this problem unifies and extends several fault-tolerant concepts appearing in prior research. Our main contribution is a fixed-parameter tractable (FPT) algorithm for the k-fault-tolerant basis problem, parameterized by both k and the rank r of the matroid. This two-variable parameterization by k + r is shown to be tight in the following sense. On the one hand, the problem is already NP-hard for k=1. On the other hand, it is Para-NP-hard for r \geq 3 and polynomial-time solvable for r \leq 2.

Covering and partitioning the edges of a graph into cliques are classical problems at the intersection of combinatorial optimization and graph theory, having been studied through a range of algorithmic and complexity-theoretic lenses. Despite the well-known fixed-parameter tractability of these problems when parameterized by the total number of cliques, such a parameterization often fails to be meaningful for sparse graphs. In many real-world instances, on the other hand, the minimum number of cliques in an edge cover or partition can be very close to the size of a maximum independent set α(G). Motivated by this observation, we investigate above αparameterizations of the edge clique cover and partition problems. Concretely, we introduce and study Edge Clique Cover Above Independent Set (ECC/α) and Edge Clique Partition Above Independent Set (ECP/α), where the goal is to cover or partition all edges of a graph using at most α(G) + k cliques, and k is the parameter. Our main results reveal a distinct complexity landscape for the two variants. We show that ECP/αis fixed-parameter tractable, whereas ECC/αis NP-complete for all k \geq 2, yet can be solved in polynomial time for k \in {0,1}. These findings highlight intriguing differences between the two problems when viewed through the lens of parameterization above a natural lower bound. Finally, we demonstrate that ECC/αbecomes fixed-parameter tractable when parameterized by k + ω(G), where ω(G) is the size of a maximum clique of the graph G. This result is particularly relevant for sparse graphs, in which ωis typically small. For H-minor free graphs, we design a subexponential algorithm of running time f(H)^{\sqrt{k}}n^{O(1)}.

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.

We establish that for every first-order logic (FO) formula ϕ, which captures a vast number of computational problems on graphs, and every graph class G of bounded expansion, there exists a deterministic distributed algorithm that, for any n-node graph G ∈ G with diameter D, determines whether G ⊨ ϕ within O(D+log n) rounds in the standard CONGEST model. Graph classes of bounded expansion encompass many well-known families of sparse graphs, including planar graphs, bounded-genus graphs, bounded-treedepth graphs, bounded-treewidth graphs, bounded-degree graphs, graphs that exclude a fixed graph H as a minor or topological minor, random graphs with constant average degree (a.a.s.), and many network models (e.g., stochastic block models) for some ranges of parameters.

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.

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. A framework consists of an undirected graph [Formula: see text] and a matroid [Formula: see text] whose elements correspond to the vertices of [Formula: see text]. Recently, Fomin et al. [ Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2023, pp. 2214–2227] and Eiben, Koana, and Wahlström [ Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2024, pp. 377–423] developed parameterized algorithms for computing paths of rank [Formula: see text] in frameworks. More precisely, for vertices [Formula: see text] and [Formula: see text] of [Formula: see text], and an integer [Formula: see text], they gave FPT algorithms parameterized by [Formula: see text] deciding whether there is an [Formula: see text]-path in [Formula: see text] whose vertex set contains a subset of elements of [Formula: see text] of rank [Formula: see text]. These algorithms are based on the Schwartz–Zippel lemma for polynomial identity testing and thus are randomized, and therefore the existence of a deterministic FPT algorithm for this problem remains open. We present the first deterministic FPT algorithm that solves the problem in frameworks whose underlying graph [Formula: see text] is planar. While the running time of our algorithm is worse than the running times of the recent randomized algorithms, our algorithm works on more general classes of matroids. In particular, this is the first FPT algorithm for the case when matroid [Formula: see text] is represented over rationals. We complement this result by proving that if the input matroids are given by their independence oracles, then there is no algorithm solving the problem with [Formula: see text] oracle queries. Furthermore, this computational lower bound holds even if the input graphs are planar graphs of treewidth at most two.

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence , defining some property of the modified part of the graph, and the target sentence , defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic ( CMSO ) and have models of bounded treewidth, while target sentences express first-order logic ( FO ) properties. Our logic captures problems that are not definable in FO and, moreover, may have instances of unbounded treewidth. Our main result is that, for this compound logic, model-checking can be done in quadratic time on minor-free graphs. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique . It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle’s theorem and Gaifman’s theorem. Our algorithmic meta-theorem encompasses, unifies, and extends the known meta-algorithmic results for CMSO and FO on minor-closed graph classes.

Markov networks are probabilistic graphical models that employ undirected graphs to depict conditional independence relationships among variables. Our focus lies in constraint-based structure learning, which entails learning the undirected graph from data through the execution of conditional independence tests. We establish theoretical limits concerning two critical aspects of constraint-based learning of Markov networks: the number of tests and the sizes of the conditioning sets. These bounds uncover an exciting interplay between the structural properties of the graph and the amount of tests required to learn a Markov network. The starting point of our work is that the graph parameter maximum pairwise connectivity, $\kappa$, that is, the maximum number of vertex-disjoint paths connecting a pair of vertices in the graph, is responsible for the sizes of independence tests required to learn the graph. On one hand, we show that at least one test with the size of the conditioning set at least $\kappa$ is always necessary. On the other hand, we prove that any graph can be learned by performing tests of size at most $\kappa$. This completely resolves the question of the minimum size of conditioning sets required to learn the graph. When it comes to the number of tests, our upper bound on the sizes of conditioning sets implies that every $n$-vertex graph can be learned by at most $n^{\kappa}$ tests with conditioning sets of sizes at most $\kappa$. We show that for any upper bound q on the sizes of the conditioning sets, there exist graphs with $O(nq)$ vertices that require at least $n^{\Omega(\kappa)}$ tests to learn. This lower bound holds even when the treewidth and the maximum degree of the graph are at most $\kappa+2$. On the positive side, we prove that every graph of bounded treewidth can be learned by a polynomial number of tests with conditioning sets of sizes at most $2*\kappa$.

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.

The present bias is a well-documented behavioral trait that significantly influences human decision-making, with present-biased agents often prioritizing immediate rewards over long-term benefits, leading to suboptimal outcomes in various real-world scenarios. Kleinberg and Oren (2014) proposed a popular graph-theoretical model of inconsistent planning to capture the behavior of present-biased agents. In this model, a multi-step project is represented by a weighted directed acyclic task graph, where the agent traverses the graph based on present-biased preferences. We use the model of Kleinberg and Oren to address the principal-agent problem, where a principal, fully aware of the agent’s present bias, aims to modify an existing project by adding or deleting tasks. The challenge is to create a modified project that satisfies two somewhat contradictory conditions. On one hand, the present-biased agent should select specific tasks deemed important by the principal. On the other hand, if the anticipated costs in the modified project become too high for the agent, there is a risk of the agent abandoning the entire project, which is not in the principal’s interest. To tackle this issue, we leverage the tools of parameterized complexity to investigate whether the principal’s strategy can be efficiently identified. We provide algorithms and complexity bounds for this problem.

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 study the following Two-Sets Cut-Uncut problem on planar graphs. Therein, one is given an undirected planar graph $G$ and two sets of vertices $S$ and $T$. The question is, what is the minimum number of edges to remove from $G$, such that we separate all of $S$ from all of $T$, while maintaining that every vertex in $S$, and respectively in $T$, stays in the same connected component. We show that this problem can be solved in time $2^{|S|+|T|} n^{O(1)}$ with a one-sided error randomized algorithm. Our algorithm implies a polynomial-time algorithm for the network diversion problem on planar graphs, which resolves an open question from the literature. More generally, we show that Two-Sets Cut-Uncut remains fixed-parameter tractable even when parameterized by the number $r$ of faces in the plane graph covering the terminals $S \cup T$, by providing an algorithm of running time $4^{r + O(\sqrt r)} n^{O(1)}$.

The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition of it. Several NP-hard graph problems, like maximum weight independent set, can be solved in time n^{O(k)} if the input n-vertex graph is given together with a tree decomposition of independence number k. Yolov, in [SODA 2018], gave an algorithm that, given an n-vertex graph G and an integer k, in time n^{O(k^3)} either constructs a tree decomposition of G whose independence number is O(k^3) or correctly reports that the tree-independence number of G is larger than k. In this paper, we first give an algorithm for computing the tree-independence number with a better approximation ratio and running time and then prove that our algorithm is, in some sense, the best one can hope for. More precisely, our algorithm runs in time 2^{O(k^2)} n^{O(k)} and either outputs a tree decomposition of G with independence number at most $8k$, or determines that the tree-independence number of G is larger than k. This implies 2^{O(k^2)} n^{O(k)}-time algorithms for various problems, like maximum weight independent set, parameterized by the tree-independence number k without needing the decomposition as an input. Assuming Gap-ETH, an n^{Ω(k)} factor in the running time is unavoidable for any approximation algorithm for the tree-independence number. Our second result is that the exact computation of the tree-independence number is para-NP-hard: We show that for every constant k \ge 4 it is NP-hard to decide if a given graph has the tree-independence number at most k.

We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowledge, this marks the first meta-theorem regarding distributed model-checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph G has a clique of size k, whether it admits a coloring with k colors, whether it contains a graph H as a subgraph or minor, or whether terminal vertices in G could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. [PODC 2022], which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.

According to the classic Chvátal's Lemma from 1977, a graph of minimum degree δ(G) contains every tree on δ(G) + 1 vertices. Our main result is the following algorithmic “extension” of Chvátal's Lemma: For any n-vertex graph G, integer k, and a tree T on at most δ(G) + k vertices, deciding whether G contains a subgraph isomorphic to T, can be done in time f (k) · nO(1) for some function f of k only.

We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model. To our knowledge, this marks the first meta-theorem regarding distributed model-checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph $G$ has a clique of size $k$, whether it admits a coloring with $k$ colors, whether it contains a graph $H$ as a subgraph or minor, or whether terminal vertices in $G$ could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. [PODC 2022], which was focused on distributed certification of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.

Abstract We initiate the study of theDiverse Pair of (Maximum/ Perfect) Matchingsproblems which given a graphGand an integerk, ask whetherGhas two (maximum/perfect) matchings whose symmetric difference is at leastk.Diverse Pair of Matchings(asking for two not necessarily maximum or perfect matchings) is $$\textsf{NP}$$ NP -complete on general graphs ifkis part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show thatDiverse Pair of Maximum Matchingsis $$\textsf{FPT}$$ FPT parameterized byk. We round off the work by showing thatDiverse Pair of Matchingshas a kernel on $${\mathcal {O}}(k^2)$$ O(k2) vertices.

Abstract Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit “natural” guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than $$m/2 +k$$ m / 2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least $$n/2 +k$$ n / 2 + k for some $$k\ge 1$$ k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree $$\delta (G)\le n/2$$ δ ( G ) ≤ n / 2 , the length of a longest cycle L is at least $$2\delta (G)$$ 2 δ ( G ) . Thus the “essential” part in finding the longest cycle is in approximating the “offset” $$k = L - 2 \delta (G)$$ k = L - 2 δ ( G ) . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length $$2\delta (G)+\Omega (f(k))$$ 2 δ ( G ) + Ω ( f ( k ) ) .

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.

We study the α-Fixed Cardinality Graph Partitioning (α-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph G, two numbers k,p and 0≤α≤1, the question is whether there is a set S⊆V of size k with a specified coverage function covα(S) at least p (or at most p for the minimization version). The coverage function covα(⋅) counts edges with exactly one endpoint in S with weight α and edges with both endpoints in S with weight 1−α. α-FCGP generalizes a number of fundamental graph problems such as Densest k-Subgraph, Max k-Vertex Cover, and Max (k,n−k)-Cut. A natural question in the study of α-FCGP is whether the algorithmic results known for its special cases, like Max k-Vertex Cover, could be extended to more general settings. One of the simple but powerful methods for obtaining parameterized approximation [Manurangsi, SOSA 2019] and subexponential algorithms [Fomin et al. IPL 2011] for Max k-Vertex Cover is based on the greedy vertex degree orderings. The main insight of our work is that the idea of greedy vertex degree ordering could be used to design fixed-parameter approximation schemes (FPT-AS) for α>0 and subexponential-time algorithms for the problem on apex-minor free graphs for maximization with α>1/3 and minimization with α<1/3.4

Fair clustering is a constrained clustering problem where we need to partition a set of colored points. The fraction of points of each color in every cluster should be more or less equal to the fraction of points of this color in the dataset. The problem was recently introduced by Chierichetti et al. [NeurIPS 2017]. We propose a new construction of coresets for fair clustering for Euclidean and general metrics based on random sampling. For the Euclidean space Rd, we provide the first coreset whose size does not depend exponentially on the dimension d. The question of whether such constructions exist was asked by Schmidt, Schwiegelshohn, and Sohler [WAOA 2019] and Huang, Jiang, and Vishnoi [NeurIPS 2019]. For general metrics, our construction provides the first coreset for fair clustering. New coresets appear to be a handy tool for designing better approximation and streaming algorithms for fair and other constrained clustering variants.

Abstract. Branchwidth determines how graphs and, more generally, arbitrary connectivity (symmetric and submodular) functions can be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations can decrease the width of a branch decomposition or the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. The first is an algorithm that, for a given [Formula: see text]-vertex graph [Formula: see text] and integer [Formula: see text], in time [Formula: see text] either constructs a rank decomposition of [Formula: see text] of width at most [Formula: see text] or concludes that the rankwidth of [Formula: see text] is more than [Formula: see text]. It also yields a [Formula: see text]-approximation algorithm for cliquewidth within the same time complexity, which in turn improves to [Formula: see text] the running times of various algorithms on graphs of cliquewidth [Formula: see text]. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area. The second application is an algorithm that, for a given [Formula: see text]-vertex graph [Formula: see text] and integer [Formula: see text], in time [Formula: see text] either constructs a branch decomposition of [Formula: see text] of width at most [Formula: see text] or concludes that the branchwidth of [Formula: see text] is more than [Formula: see text]. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].

Abstract. In 1959, Erdős and Gallai proved that every graph [Formula: see text] with average vertex degree [Formula: see text] contains a cycle of length at least [Formula: see text]. We provide an algorithm that for [Formula: see text], in time [Formula: see text] decides whether a 2-connected [Formula: see text]-vertex graph [Formula: see text] contains a cycle of length at least [Formula: see text]. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G , we seek for a cycle C in G of minimum cost 𝖮𝖯𝖳 = f(C) . We give an algorithm that given an n -vertex graph G , parameter ɛ > 0, and the function f represented by an oracle, in time n 𝒪 (log 1/ɛ) finds a cycle C in G with f(C) ≤ (1+ɛ). 𝖮𝖯𝖳. This is in sharp contrast with the non-approximability of the closely related Monotone Submodular Shortest ( s,t -Path problem, which requires exponentially many queries to the oracle for finding an n 2/3-ɛ -approximation Goel et al. [ 7 ], FOCS 2009. We complement our algorithm with a matching lower bound. We show that for every ɛ > 0, obtaining a (1+ɛ)-approximation requires at least n Ω (log 1/ ɛ) queries to the oracle. When the function f is integer-valued, our algorithm yields that a cycle of cost 𝖮𝖯𝖳 can be found in time n 𝒪(log 𝖮𝖯𝖳) . In particular, for 𝖮𝖯𝖳 = n 𝒪(1) this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that n 𝒪(log n ) queries are required even when 𝖮𝖯𝖳= 𝒪( n ). We also consider special cases of monotone submodular functions, corresponding to the number of different color classes needed to cover a cycle in an edge-colored multigraph G . For special cases of the corresponding minimization problem, we obtain fixed-parameter tractable algorithms and polynomial-time algorithms, when restricted to certain classes of inputs.

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored \(n\) -vertex undirected graph, vertices \(s\) and \(t\) , and an integer \(k\) , finds an \((s,t)\) -path containing at least \(k\) different colors in time \(2^{k}n^{\mathcal{O}(1)}\) . This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman on finding a path through \(k\) specified vertices. It also implies the first \(2^{k}n^{\mathcal{O}(1)}\) time algorithm for finding an \((s,t)\) -path of length at least \(k\) . Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\) -vertex undirected graph \(G\) , a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\) , a positive integer weight function on the vertices of \(G\) , two sets of vertices \(S,T\subseteq V(G)\) , and integers \(p,k,w\) , and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\) , while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^{2}\log(q+k))}n^{\mathcal{O}(1)}w\) time randomized algorithm for this problem.

The task of the broadcast problem is, given a graph G and a source vertex s, to compute the minimum number of rounds required to disseminate a piece of information from s to all vertices in the graph. It is assumed that, at each round, an informed vertex can transmit the information to at most one of its neighbors. The broadcast problem is known to NP-hard. We show that the problem is FPT when parametrized by the size k of a feedback edge set, or by the size k of a vertex cover, or by k=n−t, where t is the input deadline for the broadcast protocol to complete.

Designing coresets - small-space sketches of the data preserving cost of the solutions within (1± ε)-approximate factor - is an important research direction in the study of center-based k-clustering problems, such as k-means or k-median. Feldman and Langberg [STOC'11] have shown that for k-clustering of n points in general metrics, it is possible to obtain coresets whose size depends logarithmically in n. Moreover, such a dependency in n is inevitable in general metrics. A significant amount of recent work in the area is devoted to obtaining coresests whose sizes are independent of n for special metrics, like d-dimensional Euclidean space [Huang, Vishnoi, STOC'20], doubling metrics [Huang, Jiang, Li, Wu, FOCS'18], metrics of graphs of bounded treewidth [Baker, Braverman, Huang, Jiang, Krauthgamer, Wu, ICML’20], or graphs excluding a fixed minor [Braverman, Jiang, Krauthgamer, Wu, SODA’21]. In this paper, we provide the first constructions of coresets whose size does not depend on n for k-clustering in the metrics induced by geometric intersection graphs. For example, we obtain (k log²k)/ε^𝒪(1) size coresets for k-clustering in Euclidean-weighted unit-disk graphs (UDGs) and unit-square graphs (USGs). These constructions follow from a general theorem that identifies two canonical properties of a graph metric sufficient for obtaining coresets whose size is independent of n. The proof of our theorem builds on the recent work of Cohen-Addad, Saulpic, and Schwiegelshohn [STOC '21], which ensures small-sized coresets conditioned on the existence of an interesting set of centers, called centroid set. The main technical contribution of our work is the proof of the existence of such a small-sized centroid set for graphs that satisfy the two canonical properties. Loosely speaking, the metrics of geometric intersection graphs are "similar" to the Euclidean metrics for points that are close, and to the shortest path metrics of planar graphs for points that are far apart. The main technical challenge in constructing centroid sets of small sizes is in combining these two very different metrics. The new coreset construction helps to design the first (1+ε)-approximation for center-based clustering problems in UDGs and USGs, that is fixed-parameter tractable in k and ε (FPT-AS).

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.

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m/2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n/2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ(G) ≤ n/2, the length of the longest cycle L is at least 2δ(G). Thus the "essential" part of finding the longest cycle is in approximating the "offset" k = L - 2δ(G). The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2δ(G)+Ω(f(k)).

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or $\mathcal{G}$-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle's theorem does not apply. The proof of our meta-theorem combines novel combinatorial results related to the Flat Wall theorem along with elements of the proof of Courcelle's theorem and Gaifman's theorem. We finally prove extensions where the target property is expressible in FOL+DP, i.e., the enhancement of FOL with disjoint-paths predicates.

A framework consists of an undirected graph $G$ and a matroid $M$ whose elements correspond to the vertices of $G$. Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023] developed parameterized algorithms for computing paths of rank $k$ in frameworks. More precisely, for vertices $s$ and $t$ of $G$, and an integer $k$, they gave FPT algorithms parameterized by $k$ deciding whether there is an $(s,t)$-path in $G$ whose vertex set contains a subset of elements of $M$ of rank $k$. These algorithms are based on Schwartz-Zippel lemma for polynomial identity testing and thus are randomized, and therefore the existence of a deterministic FPT algorithm for this problem remains open. We present the first deterministic FPT algorithm that solves the problem in frameworks whose underlying graph $G$ is planar. While the running time of our algorithm is worse than the running times of the recent randomized algorithms, our algorithm works on more general classes of matroids. In particular, this is the first FPT algorithm for the case when matroid $M$ is represented over rationals. Our main technical contribution is the nontrivial adaptation of the classic irrelevant vertex technique to frameworks to reduce the given instance to one of bounded treewidth. This allows us to employ the toolbox of representative sets to design a dynamic programming procedure solving the problem efficiently on instances of bounded treewidth.

We study the kernelization of exploration problems on temporal graphs. A temporal graph consists of a finite sequence of snapshot graphs $\mathcal{G}=(G_1, G_2, \dots, G_L)$ that share a common vertex set but might have different edge sets. The non-strict temporal exploration problem (NS-TEXP for short) introduced by Erlebach and Spooner, asks if a single agent can visit all vertices of a given temporal graph where the edges traversed by the agent are present in non-strict monotonous time steps, i.e., the agent can move along the edges of a snapshot graph with infinite speed. The exploration must at the latest be completed in the last snapshot graph. The optimization variant of this problem is the $k$-arb NS-TEXP problem, where the agent's task is to visit at least $k$ vertices of the temporal graph. We show that under standard computational complexity assumptions, neither of the problems NS-TEXP nor $k$-arb NS-TEXP allow for polynomial kernels in the standard parameters: number of vertices $n$, lifetime $L$, number of vertices to visit $k$, and maximal number of connected components per time step $γ$; as well as in the combined parameters $L+k$, $L + γ$, and $k+γ$. On the way to establishing these lower bounds, we answer a couple of questions left open by Erlebach and Spooner. We also initiate the study of structural kernelization by identifying a new parameter of a temporal graph $p(\mathcal{G}) = \sum_{i=1}^{L} (|E(G_i)|) - |V(G)| +1$. Informally, this parameter measures how dynamic the temporal graph is. Our main algorithmic result is the construction of a polynomial (in $p(\mathcal{G})$) kernel for the more general Weighted $k$-arb NS-TEXP problem, where weights are assigned to the vertices and the task is to find a temporal walk of weight at least $k$.

We introduce the following submodular generalization of the SHORTEST CYCLE problem. For a nonnegative monotone submodular cost function f defined on the edges (or the vertices) of an undirected graph G, we seek for a cycle C in G of minimum cost OPT = f(C). We give an algorithm that given an n-vertex graph G, parameter ε > 0, and the function f represented by an oracle, in time n

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is a randomized algorithm, that given a colored n-vertex undirected graph, vertices s and t, and an integer k, finds an (s,t)-path containing at least k different colors in time 2kn

k-means and k-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependencies on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable k-means and k-median clustering in ICML 2020. In this model, a decision tree with k leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the “best explanation” by using a decision tree with k leaves? (2) For a given set of points, how to find a decision tree with k leaves minimizing the k-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.

We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some vertices. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex. Divider aims to prevent the rendezvous of Facilitator's agents. We show that deciding whether Facilitator can win is PSPACE-hard and, when parameterized by k, co-W[2]-hard. Moreover, even deciding whether Facilitator can win within τ steps is co-NP-complete already for τ=2. On the other hand, for chordal and P5-free graphs, we prove that the problem is solvable in polynomial time. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph's neighborhood diversity and the number of steps τ.

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.

In the Categorical Clustering problem, we are given a set of vectors (matrix) A={a1,…,an} over Σm, where Σ is a finite alphabet, and integers k and B. The task is to partition A into k clusters such that the median objective of the clustering in the Hamming norm is at most B. Fomin, Golovach, and Panolan [ICALP 2018] proved that the problem is fixed-parameter tractable for the binary case Σ={0,1}. We extend this algorithmic result to a popular capacitated clustering model, where in addition the sizes of the clusters are lower and upper bounded by integer parameters p and q, respectively. Our main theorem is that the problem is solvable in time 2O(Blog⁡B)|Σ|B⋅(mn)O(1).

A k-core of a graph G is the maximal induced subgraph in which every vertex has degree at least k. In the Edge k-Core optimization problem, we are given a graph G and integers k, b and p. The task is to ensure that the k-core of G has at least p vertices, by adding at most b edges. While Edge k-Core is known to be computationally hard in general, we show that there are efficient algorithms when the k-core has to be constructed from a sparse graph with some structural properties. Our results are as follows. When the input graph is a forest, Edge k-Core is solvable in polynomial time. Edge k-Core is fixed-parameter tractable (FPT) when parameterized by the minimum size of a vertex cover in the input graph. Edge k-Core is FPT when parameterized by the treewidth of the graph plus k.

Abstract In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existence of an (exact) kernel of polynomial size and a PTAS.

k-means and k-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable k-means and k-median clustering in ICML 2020. In this model, a decision tree with k leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the ``best explanation'' by using a decision tree with k leaves? (2) For a given set of points, how to find a decision tree with k leaves minimizing the k-means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering.

In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G)\geq 2 contains a cycle of length at least ad(G). We provide an algorithm that for k\geq 0 in time 2^{O(k)} n^{O(1)} decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

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 disks. Thus the problem of packing equal disks is the special case of our problem with 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. Our main algorithmic contribution is an algorithm that solves the repacking problem in time (h+k)^𝒪(h+k)⋅|I|^𝒪(1), where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h.

Boolean Matrix Factorization (BMF) aims to find an approximation of a given binary matrix as the Boolean product of two low-rank binary matrices. Binary data is ubiquitous in many fields, and representing data by binary matrices is common in medicine, natural language processing, bioinformatics, computer graphics, among many others. Factorizing a matrix into low-rank matrices is used to gain more information about the data, like discovering relationships between the features and samples, roles and users, topics and articles, etc. In many applications, the binary nature of the factor matrices could enormously increase the interpretability of the data. Unfortunately, BMF is computationally hard and heuristic algorithms are used to compute Boolean factorizations. Very re-cently, the theoretical breakthrough was obtained independently by two research groups. Ban et al. (SODA 2019) and Fomin et al. (Trans. Algorithms 2020) show that BMF admits an effi-cient polynomial-time approximation scheme (EPTAS). However, despite the theoretical importance, the high double-exponential dependence of the running times from the rank makes these algorithms unimplementable in practice. The primary research question motivating our work is whether the theoretical advances on BMF could lead to practical algorithms. The main conceptional contribution of our work is the fol-lowing. While EPTAS for BMF is a purely theoretical advance, the general approach behind these algorithms could serve as the basis in designing better heuristics. We also use this strategy to develop new algorithms for related$\mathbb{F}_{p}$-Matrix Factorization. Here, given a matrix A over a finite field GF$(p)$where$p$is a prime, and an integer$r$. our objective is to find a matrix$\mathrm{B}$over the same field with GF$(p)$-rank at most$r$minimizing some norm of A-B. Our empirical research on synthetic and real-world data demonstrates the advantage of the new algorithms over previous works on BMF and$\mathbb{F}_{p}$-Matrix Factorization.

In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of clusters. Additionally, we are given a set F of cluster centers in the same metric space. The goal is to select a set C ⊆ F of k centers and assign each point in P to a center in C, such that the maximum load over all centers is minimized. Here the load of a center is the sum of the distances between it and the points assigned to it. Although clustering/facility location problems have rich literature, the minimum-load objective has not been studied substantially, and hence MLkC has remained a poorly understood problem. More interestingly, the problem is notoriously hard even in some special cases including the one in line metrics as shown by Ahmadian et al. [APPROX 2014, ACM Trans. Algorithms 2018]. They also show APX-hardness of the problem in the plane. On the other hand, the best-known approximation factor for MLkC is O(k), even in the plane. In this work, we study a fair version of MLkC inspired by the work of Chierichetti et al. [NeurIPS, 2017]. Here the input points are partitioned into 𝓁 protected groups, and only clusters that proportionally represent each group are allowed. MLkC is the special case with 𝓁 = 1. For the fair version, we are able to obtain a randomized 3-approximation algorithm in f(k,𝓁)⋅ n^O(1) time. Also, our scheme leads to an improved (1 + ε)-approximation in the case of Euclidean norm with the same running time (depending also linearly on the dimension d). Our results imply the same approximations for MLkC with running time f(k)⋅ n^O(1), achieving the first constant-factor FPT approximations for this problem in general and Euclidean metric spaces.

In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every n-vertex 2-connected graph G with minimum vertex degree δ ≥ 2 contains a cycle with at least min{2δ, n} vertices. In particular, if δ ≥ n/2, then G is Hamiltonian. The proof of Dirac's theorem is constructive, and it yields an algorithm computing the corresponding cycle in polynomial time. The combinatorial bound of Dirac's theorem is tight in the following sense. There are 2-connected graphs that do not contain cycles of length more than 2δ + 1. Also, there are non-Hamiltonian graphs with all vertices but one of degree at least n/2. This prompts naturally to the following algorithmic questions. For k ≥ 1, (A) How difficult is to decide whether a 2-connected graph contains a cycle of length at least min{2δ + k, n}? (B) How difficult is to decide whether a graph G is Hamiltonian, when at least n–k vertices of G are of degrees at least n/2–k? The first question was asked by Fomin, Golovach, Lokshtanov, Panolan, Saurabh, and Zehavi. The second question is due to Jansen, Kozma, and Nederlof. Even for a very special case of k = 1, the existence of a polynomial-time algorithm deciding whether G contains a cycle of length at least min{2δ + 1, n} was open. We resolve both questions by proving the following algorithmic generalization of Dirac's theorem: If all but k vertices of a 2-connected graph G are of degree at least δ, then deciding whether G has a cycle of length at least min{2δ + k, n} can be done in time . The proof of the algorithmic generalization of Dirac's theorem builds on new graph-theoretical results that are interesting on their own.

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.

Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework.

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 The Maximum Covering Location Problem (MCLP) is a well-studied problem in the field of operations research. Given a network with positive or negative demands on the nodes, a positive integer k, the MCLP seeks to find k potential facility centers in the network such that the neighborhood coverage is maximized. We study the variant of MCLP where edges of the network are subject to random failures due to some disruptive events. One of the popular models capturing the unreliable nature of the facility location is the linear reliability ordering (LRO) model. In this model, with every edge e of the network, we associate its survival probability 0 ≤ pe ≤ 1, or equivalently, its failure probability 1 − pe. The failure correlation in LRO is the following: If an edge e fails then every edge $e^{\prime }$ e ′ with $p_{e^{\prime }} \leq p_{e}$ p e ′ ≤ p e surely fails. The task is to identify the positions of k facilities that maximize the expected coverage. We refer to this problem as Expected Coverage problem. We study the Expected Coverage problem from the parameterized complexity perspective and obtain the following results. 1. For the parameter pathwidth, we show that the Expected Coverage problem is W[1]-hard. We find this result a bit surprising, because the variant of the problem with non-negative demands is fixed-parameter tractable (FPT) parameterized by the treewidth of the input graph. 2. We complement the lower bound by the proof that Expected Coverage is FPT being parameterized by the treewidth and the maximum vertex degree. We give an algorithm that solves the problem in time $ 2^{{\mathcal {O}}({\textbf {tw}} \log {\varDelta })} n^{{\mathcal {O}}(1)}$ 2 O ( tw log Δ ) n O ( 1 ) , where tw is the treewidth, Δ is the maximum vertex degree, and n the number of vertices of the input graph. In particular, since Δ ≤ n, it means the problem is solvable in time $ n^{{\mathcal {O}}({\textbf {tw}})} $ n O ( tw ) , that is, is in XP parameterized by treewidth.

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.

The elimination distance to some target graph property P is a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problem’s fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: For every graph property P expressible by a first order-logic formula \( \varphi \in \Sigma _3 \) , that is, of the form \( \begin{equation*} \varphi =\exists x_1\exists x_2\cdots \exists x_r\ \ \forall y_{1}\forall y_{2}\cdots \forall y_{s}\ \ \exists z_1\exists z_2\cdots \exists z_t~~ \psi ,\end{equation*} \) where \( \psi \) is a quantifier-free first-order formula, checking whether the elimination distance of a graph to P does not exceed \( k \) , is fixed-parameter tractable parameterized by \( k \) . Properties of graphs expressible by formulas from \( \Sigma _3 \) include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulas with even slightly more expressive prefix structure: There are formulas \( \varphi \in \Pi _3 \) , for which computing elimination distance is \( {\sf W}[2] \) -hard.

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.

Fair clustering is a variant of constrained clustering where the goal is to partition a set of colored points. The fraction of points of each color in every cluster should be more or less equal to the fraction of points of this color in the dataset. This variant was recently introduced by Chierichetti et al. [NeurIPS 2017] and became widely popular. This paper proposes a new construction of coresets for fair k-means and k-median clustering for Euclidean and general metrics based on random sampling. For the Euclidean space ℝ^d, we provide the first coresets whose size does not depend exponentially on the dimension d. The question of whether such constructions exist was asked by Schmidt, Schwiegelshohn, and Sohler [WAOA 2019] and Huang, Jiang, and Vishnoi [NeurIPS 2019]. For general metric, our construction provides the first coreset for fair k-means and k-median. New coresets appear to be a handy tool for designing better approximation and streaming algorithms for fair and other constrained clustering variants. In particular, we obtain - the first fixed-parameter tractable (FPT) PTAS for fair k-means and k-median clustering in ℝ^d. The near-linear time of our PTAS improves over the previous scheme of Böhm, Fazzone, Leonardi, and Schwiegelshohn [ArXiv 2020] with running time n^{poly(k/ε)}; - FPT "true" constant-approximation for metric fair clustering. All previous algorithms for fair k-means and k-median in general metric are bicriteria and violate the fairness constraints; - FPT 3-approximation for lower-bounded k-median improving the best-known 3.736 factor of Bera, Chakrabarty, and Negahbani [ArXiv 2019]; - the first FPT constant-approximations for metric chromatic clustering and 𝓁-Diversity clustering; - near linear-time (in n) PTAS for capacitated and lower-bounded clustering improving over PTAS of Bhattacharya, Jaiswal, and Kumar [TOCS 2018] with super-quadratic running time; - a streaming (1+ε)-approximation for fair k-means and k-median of space complexity polynomial in k, d, ε and log{n} (the previous algorithms have exponential space complexity on either d or k).

PCA with Outliers is the fundamental problem of identifying an underlying low-dimensional subspace in a data set corrupted with outliers. A large body of work is devoted to the information-theoretic aspects of this problem. However, from the computational perspective, its complexity is still not well-understood. We study this problem from the perspective of parameterized complexity by investigating how parameters like the dimension of the data, the subspace dimension, the number of outliers and their structure, and approximation error, influence the computational complexity of the problem. Our algorithmic methods are based on techniques of randomized linear algebra and algebraic geometry.

The elimination distance to some target graph propertyPis a general graph modification parameter introduced by Bulian and Dawar. We initiate the study of elimination distances to graph properties expressible in first-order logic. We delimit the problem's fixed-parameter tractability by identifying sufficient and necessary conditions on the structure of prefixes of first-order logic formulas. Our main result is the following meta-theorem: For every graph propertyPexpressible by a first order-logic formula φ ∈ Σ3, that is, of the form φ = ∃x1∃x2⋯∃xr∀y1∀y2⋯∀ys∃z1∃z2⋯∃ztψ, where ψ is a quantifier-free first-order formula, checking whether the elimination distance of a graph toPdoes not exceed k, is fixed-parameter tractable parameterized by k. Properties of graphs expressible by formulas from Σ3 include being of bounded degree, excluding a forbidden subgraph, or containing a bounded dominating set. We complement this theorem by showing that such a general statement does not hold for formulas with even slightly more expressive prefix structure: There are formulas φ ∈ Π3, for which computing elimination distance is W[2]-hard.

We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, most of the known feature selection methods are heuristics. We study the following mathematical model. We assume that there are some inadvertent (or undesirable) features of the input data that unnecessarily increase the cost of clustering. Consequently, we want to select a subset of the original features from the data such that there is a small-cost clustering on the selected features. More precisely, for given integers l (the number of irrelevant features) and k (the number of clusters), budget B, and a set of n categorical data points (represented by m-dimensional vectors whose elements belong to a finite set of values Σ), we want to select m-l relevant features such that the cost of any optimal k-clustering on these features does not exceed B. Here the cost of a cluster is the sum of Hamming distances (l0-distances) between the selected features of the elements of the cluster and its center. The clustering cost is the total sum of the costs of the clusters. We use the framework of parameterized complexity to identify how the complexity of the problem depends on parameters k, B, and |Σ|. Our main result is an algorithm that solves the Feature Selection problem in time f(k,B,|Σ|)⋅m^{g(k,|Σ|)}⋅n² for some functions f and g. In other words, the problem is fixed-parameter tractable parameterized by B when |Σ| and k are constants. Our algorithm for Feature Selection is based on a solution to a more general problem, Constrained Clustering with Outliers. In this problem, we want to delete a certain number of outliers such that the remaining points could be clustered around centers satisfying specific constraints. One interesting fact about Constrained Clustering with Outliers is that besides Feature Selection, it encompasses many other fundamental problems regarding categorical data such as Robust Clustering, Binary and Boolean Low-rank Matrix Approximation with Outliers, and Binary Robust Projective Clustering. Thus as a byproduct of our theorem, we obtain algorithms for all these problems. We also complement our algorithmic findings with complexity lower bounds.

We consider a generalization of the fundamental k-means clustering for data with incomplete or corrupted entries. When data objects are represented by points in ℝd, a data point is said to be incomplete when some of its entries are missing or unspecified. An incomplete data point with at most Δ unspecified entries corresponds to an axis-parallel affine subspace of dimension at most Δ, called a Δ-point. Thus we seek a partition of n input Δ-points into k clusters minimizing the k-means objective. For Δ = 0, when all coordinates of each point are specified, this is the usual k-means clustering. We give an algorithm that finds an (1 + ∊)-approximate solution in time f(k, ∊, Δ) · n2 · d for some function f of k, ∊, and Δ only.

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.

Abstract We study algorithmic properties of the graph class $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e . More precisely, we identify a large class of optimization problems on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e solvable in time $$2^{{\mathcal{O}}(\sqrt{k}\log k)}\cdot n^{{\mathcal{O}}(1)}$$ 2 O ( k log k ) · n O ( 1 ) . Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on $${\textsc {Chordal}}{-ke}$$ C H O R D A L - k e graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of $${\textsc {Chordal}}{-ke}$$ C H O R D A L -

In k-Clustering we are given a multiset of n vectors X⊂Zd and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C1,…,Ck such that the cost∑i=1kminci∈Rd⁡∑x∈Ci‖x−ci‖pp≤D, where ‖⋅‖p is the Lp-norm. For p=2, k-Clustering is k-Means. We study k-Clustering from the perspective of parameterized complexity. The problem is known to be NP-hard for k=2 and also for d=2. It is a long-standing open question, whether the problem is fixed-parameter tractable (FPT) for the combined parameter d+k. In this paper, we focus on the parameterization by D. We complement the known negative results by showing that for p=0 and p=∞, k-Clustering is W[1]-hard when parameterized by D. Interestingly, we discover a tractability island of k-Clustering: for every p∈(0,1], k-Clustering is solvable in time 2O(Dlog⁡D)(nd)O(1).

We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known generalizations of the classical Hamiltonian Path and Hamiltonian Cycle problems. Our choice of parameterization is strongly influenced by the work of Biró, Hujter, and Tuza, who in 1992 introduced $H$-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi-)graph $H$. In this work, we turn to proper $H$-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph $H$ is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results. Path Cover admits a kernel of size $\mathcal{O}(\|H\|^8)$, where $\|H\|$ is the size of graph $H$. In other words, we design an algorithm that for an $n$-vertex graph $G$ and integer $k\geq 1$, in time polynomial in $n$ and $\|H\|$, outputs a graph $G'$ of size $\mathcal{O}(\|H\|^8)$ and $k'\leq |V(G')|$ such that the vertex set of $G$ is coverable by $k$ vertex-disjoint paths if and only if the vertex set of $G'$ is coverable by $k'$ vertex-disjoint paths. Hamiltonian Cycle admits a kernel of size $\mathcal{O}(\|H\|^8)$. Cycle Cover admits a polynomial kernel. We prove it by providing a compression of size $\mathcal{O}(\|H\|^{10})$ into another \sf NP-complete problem, namely, Prize Collecting Cycle Cover, that is, we design an algorithm that, in time polynomial in $n$ and $\|H\|$, outputs an equivalent instance of Prize Collecting Cycle Cover of size $\mathcal{O}(\|H\|^{10})$. In all our algorithms we assume that a proper $H$-decomposition is given as a part of the input.

A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs $G$ and $H$ are 2-isomorphic, or equivalently, their cycle matroids are isomorphic if and only if $G$ can be transformed into $H$ by a series of operations called Whitney switches. In this paper we consider the quantitative question arising from Whitney's theorem: Given two 2-isomorphic graphs, can we transform one into another by applying at most $k$ Whitney switches? This problem is already \sf NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size $\mathcal{O}(k)$ and thus is fixed-parameter tractable when parameterized by $k$.

Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AAMAS 2017] initiated the algorithmic study of a geographically-based manipulation problem, where voters must vote at the ballot box closest to them. In this variant of gerrymandering, for a given set of possible locations of ballot boxes and known political preferences of n voters, the task is to identify locations for k boxes out of m possible locations to guarantee victory of a certain party in at least ℓ districts. Here integers k and ℓ are some selected parameter.It is known that the problem is NP-complete already for 4 political parties and prior to our work only heuristic algorithms for this problem were developed. We initiate the rigorous study of the gerrymandering problem from the perspectives of parameterized and fine-grained complexity and provide asymptotically matching lower and upper bounds on its computational complexity. We prove that the problem is W[1]-hard parameterized by k + n and that it does not admit an f(n,k) · mo(√k) algorithm for any function f of k and n only, unless the Exponential Time Hypothesis (ETH) fails. Our lower bounds hold already for 2 parties. On the other hand, we give an algorithm that solves the problem for a constant number of parties in time (m+n)O(√k).

People sometimes act differently when making decisions affecting the present moment versus decisions affecting the future only. This is referred to as time-inconsistent behaviour, and can be modeled as agents exhibiting present bias. A resulting phenomenon is abandonment, which is when an agent initially pursues a task, but ultimately gives up before reaping the rewards. With the introduction of the graph-theoretic time-inconsistent planning model due to Kleinberg and Oren, it has been possible to investigate the computational complexity of how a task designer best can support a present-biased agent in completing the task. In this paper, we study the complexity of finding a choice reduction for the agent; that is, how to remove edges and vertices from the task graph such that a present-biased agent will remain motivated to reach his target even for a limited reward. While this problem is NP-complete in general, this is not necessarily true for instances which occur in practice, or for solutions which are of interest to task designers. For instance, a task designer may desire to find the best task graph which is not too complicated. We therefore investigate the problem of finding simple motivating subgraphs. These are structures where the agent will modify his plan at most k times along the way. We quantify this simplicity in the time-inconsistency model as a structural parameter: The number of branching vertices (vertices with out-degree at least 2) in a minimal motivating subgraph. Our results are as follows: We give a linear algorithm for finding an optimal motivating path, i. e. when k = 0. On the negative side, we show that finding a simple motivating subgraph is NP-complete even if we allow only a single branching vertex — revealing that simple motivating subgraphs are indeed hard to find. However, we give a pseudo-polynomial algorithm for the case when k is fixed and edge weights are rationals, which might be a reasonable assumption in practice.

We consider 𝓁₁-Rank-r Approximation over {GF}(2), where for a binary m× n matrix 𝐀 and a positive integer constant r, one seeks a binary matrix 𝐁 of rank at most r, minimizing the column-sum norm ‖ 𝐀 -𝐁‖₁. We show that for every ε ∈ (0, 1), there is a {randomized} (1+ε)-approximation algorithm for 𝓁₁-Rank-r Approximation over {GF}(2) of running time m^{O(1)}n^{O(2^{4r}⋅ ε^{-4})}. This is the first polynomial time approximation scheme (PTAS) for this problem.

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

The incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about the incidence relations can have some slight noise. In this paper, we initiate the study of the computational complexity of recovering incidence matrices of graphs from a binary matrix: given a binary matrix M which can be written as the superposition of two binary matrices L and S, where S is the incidence matrix of a graph from a specified graph class, and L is a matrix (i) of small rank or, (ii) of small (Hamming) weight. Further, identify all those graphs whose incidence matrices form part of such a superposition. Here, L represents the noise in the input matrix M. Another motivation for this problem comes from the Matroid Minors project of Geelen, Gerards and Whittle, where perturbed graphic and co-graphic matroids play a prominent role. There, it is expected that a perturbed binary matroid (or its dual) is presented as L+S where L is a low rank matrix and S is the incidence matrix of a graph. Here, we address the complexity of constructing such a decomposition. When L is of small rank, we show that the problem is NP-complete, but it can be decided in time (mn)^O(r), where m,n are dimensions of M and r is an upper-bound on the rank of L. When L is of small weight, then the problem is solvable in polynomial time (mn)^O(1). Furthermore, in many applications it is desirable to have the list of all possible solutions for further analysis. We show that our algorithms naturally extend to enumeration algorithms for the above two problems with delay (mn)^O(r) and (mn)^O(1), respectively, between consecutive outputs.

In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex removal, edge removal, edge contraction, or edge addition and the question is, given a graph G and an integer k, whether it is possible to transform G to a graph in 𝒫 after applying k times the operation ⊠ on G. This problem has been extensively studied for particilar instantiations of ⊠ and 𝒫. In this paper we consider the general property 𝒫_ϕ of being planar and, moreover, being a model of some First-Order Logic sentence ϕ (an FOL-sentence). We call the corresponding meta-problem Graph ⊠-Modification to Planarity and ϕ and prove the following algorithmic meta-theorem: there exists a function f: ℕ² → ℕ such that, for every ⊠ and every FOL sentence ϕ, the Graph ⊠-Modification to Planarity and ϕ is solvable in f(k,|ϕ|)⋅n² time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifman’s Locality Theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.

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.

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.

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

A popular model to measure network stability is the k-core, that is the maximal induced subgraph in which every vertex has degree at least k. For example, k-cores are commonly used to model the unraveling phenomena in social networks. In this model, users having less than k connections within the network leave it, so the remaining users form exactly the k-core. In this paper we study the question of whether it is possible to make the network more robust by spending only a limited amount of resources on new connections. A mathematical model for the k-core construction problem is the following Edge k-Core optimization problem. We are given a graph G and integers k, b and p. The task is to ensure that the k-core of G has at least p vertices by adding at most b edges. The previous studies on Edge k-Core demonstrate that the problem is computationally challenging. In particular, it is NP-hard when k = 3, W[1]-hard when parameterized by k+b+p (Chitnis and Talmon, 2018), and APX-hard (Zhou et al, 2019). Nevertheless, we show that there are efficient algorithms with provable guarantee when the k-core has to be constructed from a sparse graph with some additional structural properties. Our results are - When the input graph is a forest, Edge k-Core is solvable in polynomial time; - Edge k-Core is fixed-parameter tractable (FPT) when parameterized by the minimum size of a vertex cover in the input graph. On the other hand, with such parameterization, the problem does not admit a polynomial kernel subject to a widely-believed assumption from complexity theory; - Edge k-Core is FPT parameterized by the treewidth of the graph plus k. This improves upon a result of Chitnis and Talmon by not requiring b to be small. Each of our algorithms is built upon a new graph-theoretical result interesting in its own.

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

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

Abstract For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This class was introduced in the early 1990s by Bíró, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of H-graphs by showing that a number of fundamental optimization problems like Maximum Clique, Maximum Independent Set, or Minimum Dominating Set are solvable in polynomial time on H-graphs. We extend and complement these algorithmic findings in several directions. First we show that for every fixed H, the class of H-graphs is of logarithmically-bounded boolean-width (via mim-width). Pipelined with the plethora of known algorithms on graphs of bounded boolean-width, this describes a large class of problems solvable in polynomial time on H-graphs. We also observe that H-graphs are graphs with polynomially many minimal separators. Combined with the work of Fomin, Todinca and Villanger on algorithmic properties of such classes of graphs, this identify another wide class of problems solvable in polynomial time on H-graphs. The most fundamental optimization problems among the problems solvable in polynomial time on H-graphs are Maximum Clique, Maximum Independent Set, and Minimum Dominating Set. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that Maximum Independent Set and Minimum Dominating Set are W[1]-hard being parameterized by the size of H plus the size of the solution. On the other hand, we prove that when H is a tree, then Minimum Dominating Set is fixed-parameter tractable parameterized by the size of H. For Maximum Clique we show that it admits a polynomial kernel parameterized by H and the solution size.

Abstract A subgraph complement of the graph G is a graph obtained from G by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for a given graph G and graph class $${\mathscr {G}}$$ G , is there a subgraph complement of G which is in $${\mathscr {G}}$$ G ? We show that this problem can be solved in polynomial time for various choices of the graphs class $${\mathscr {G}}$$ G , such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is $${{\mathrm{NP}}}$$ NP -complete when $${\mathscr {G}}$$ G is the class of regular graphs.

Low-rank binary matrix approximation is a generic problem where one seeks a good approximation of a binary matrix by another binary matrix with some specific properties. A good approximation means that the difference between the two matrices in some matrix norm is small. The properties of the approximation binary matrix could be: a small number of different columns, a small binary rank or a small Boolean rank. Unfortunately, most variants of these problems are NP-hard. Due to this, we initiate the systematic algorithmic study of low-rank binary matrix approximation from the perspective of parameterized complexity. We show in which cases and under what conditions the problem is fixed-parameter tractable, admits a polynomial kernel and can be solved in parameterized subexponential time.

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

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.

In k-Clustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} sum_{x in C_i} |x-c_i|_p^p <= D, where |*|_p is the Minkowski (L_p) norm of order p. For p=1, k-Clustering is the well-known k-Median. For p=2, the case of the Euclidean distance, k-Clustering is k-Means. We study k-Clustering from the perspective of parameterized complexity. The problem is known to be NP-hard for k=2 and it is also NP-hard for d=2. It is a long-standing open question, whether the problem is fixed-parameter tractable (FPT) for the combined parameter d+k. In this paper, we focus on the parameterization by D. We complement the known negative results by showing that for p=0 and p=infty, k-Clustering is W1-hard when parameterized by D. Interestingly, the complexity landscape of the problem appears to be more intricate than expected. We discover a tractability island of k-Clustering: for every p in (0,1], k-Clustering is solvable in time 2^O(D log D) (nd)^O(1).

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.

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.

Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and neuroscience. However, it is well-documented that the applicability of PCA in many real scenarios could be constrained by an "immune deficiency" to outliers such as corrupted observations. We consider the following algorithmic question about the PCA with outliers. For a set of $n$ points in $\mathbb{R}^{d}$, how to learn a subset of points, say 1% of the total number of points, such that the remaining part of the points is best fit into some unknown $r$-dimensional subspace? We provide a rigorous algorithmic analysis of the problem. We show that the problem is solvable in time $n^{O(d^2)}$. In particular, for constant dimension the problem is solvable in polynomial time. We complement the algorithmic result by the lower bound, showing that unless Exponential Time Hypothesis fails, in time $f(d)n^{o(d)}$, for any function $f$ of $d$, it is impossible not only to solve the problem exactly but even to approximate it within a constant factor.

A replacement action is a function L that maps each k-vertex labeled graph to another k-vertex graph. We consider a general family of graph modification problems, called L-Replacement to C, where the input is a graph G and the question is whether it is possible to replace in G some k-vertex subgraph H of it by L(H) so that the new graph belongs to the graph class C. L-Replacement to C can simulate several modification operations such as edge addition, edge removal, edge editing, and diverse completion and superposition operations. In this paper, we prove that for any action L, if C is the class of planar graphs, there is an algorithm that solves L-Replacement to C in O(|G|^{2}) steps. We also present several applications of our approach to related problems.

The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class $$\mathsf {\#RH}\Pi _1$$ . It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NP-hard. We study the robustness of the intermediate complexity of #BIS by considering variants of the problem parameterised by the size of the independent set. We map the complexity landscape for three problems, with respect to exact computation and approximation and with respect to conventional and parameterised complexity. The three problems are counting independent sets of a given size, counting independent sets with a given number of vertices in one vertex class and counting maximum independent sets amongst those with a given number of vertices in one vertex class. Among other things, we show that all of these problems are NP-hard to approximate within any polynomial ratio. (This is surprising because the corresponding problems without the size parameter are complete in $$\mathsf {\#RH}\Pi _1$$ , and hence are not believed to be NP-hard.) We also show that the first problem is #W[1]-hard to solve exactly but admits an FPTRAS, whereas the other two are W[1]-hard to approximate even within any polynomial ratio. Finally, we show that, when restricted to graphs of bounded degree, all three problems have efficient exact fixed-parameter algorithms.

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.

We consider the following natural “above-guarantee” parameterization of the classical Longest Path problem: For given vertices $s$ and $t$ of a graph $G$ and integer $k$, the Longest Detour problem asks for an $(s,t)$-path in $G$ that is at least $k$ longer than a shortest $(s,t)$-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time $2^{O(k)} \cdot n^{O(1)}$. Up to the base of the exponential, this running time matches the best algorithms for finding a path of length at least $k$. Furthermore, we study the related Exact Detour problem, which asks whether a graph $G$ contains an $(s,t)$-path that is exactly $k$ longer than a shortest $(s,t)$-path. For this problem, we obtain randomized algorithms with running times $2.746^k\cdot n^{O(1)}$ (for undirected graphs) and $4^k\cdot n^{O(1)}$ (for directed graphs) and a deterministic algorithm with running time $6.745^{k}\cdot n^{O(1)}$, showing that this problem is fixed-parameter tractable as well.

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

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

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.

For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. These graphs naturally generalize several important graph classes like interval graphs or circular-arc graph. This notion was introduced in the early 1990s by Biro, Hujter, and Tuza. Recently, Chaplick et al. initiated the algorithmic study of H-graphs by showing that a number of fundamental optimization problems like Clique, Independent Set, or Dominating Set are solvable in polynomial time on H-graphs. We extend and complement these algorithmic findings in several directions. First we show that for every fixed H, the class of H-graphs is of logarithmically-bounded boolean-width. We also prove that H-graphs are graphs with polynomially many minimal separators. Pipelined with the plethora of known algorithms on graphs of bounded boolean-width and graphs with polynomially many minimal separators, this describes a large class of optimization problems that are solvable in polynomial time on H-graphs. The most fundamental optimization problems among those solvable in polynomial time on H-graphs are Clique, Independent Set, and Dominating Set. We provide a more refined complexity analysis of these problems from the perspective of parameterized complexity. We show that Independent Set and Dominating Set are W[1]-hard being parameterized by the size of H plus the size of the solution. On the other hand, we prove that when H is a tree, Dominating Set is fixed-parameter tractable (FPT) parameterized by the size of H. Besides, we show that Clique admits a polynomial kernel parameterized by H and the solution size.

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.

For a graph G, a set D subseteq V(G) is called a [1,j]-dominating set if every vertex in V(G) setminus D has at least one and at most j neighbors in D. A set D subseteq V(G) is called a [1,j]-total dominating set if every vertex in V(G) has at least one and at most j neighbors in D. In the [1,j]-(Total) Dominating Set problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [1,j]-(total) dominating set of size at most k. The [1,j]-Dominating Set problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [1,2]-Total Dominating Set problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the Dominating Set problem, both are W[1]-hard when parameterized by solution size. In this work, we study [1,j]-Dominating Set on sparse graph classes from the perspective of parameterized complexity and prove the following results when the problem is parameterized by solution size: - [1,j]-Dominating Set is W[1]-hard on d-degenerate graphs for d = j + 1; - [1,j]-Dominating Set is FPT on nowhere dense graphs. We also prove that the known algorithm for [1,j]-Dominating Set on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). Finally, assuming SETH, we provide a lower bound for the running time of any algorithm solving the [1,2]-Total Dominating Set problem parameterized by pathwidth.

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.

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.

We initiate the algorithmic study of the following “structured augmentation” question: is it possible to increase the connectivity of a given graph $G$ by superposing it with another given graph $H$? More precisely, graph $F$ is the superposition of $G$ and $H$ with respect to injective mapping $\varphi\colon V(H)\rightarrow V(G)$ if every edge $uv$ of $F$ is either an edge of $G$ or $\varphi^{-1}(u)\varphi^{-1}(v)$ is an edge of $H.$ Thus $F$ contains both $G$ and $H$ as subgraphs, and the edge set of $F$ is the union of the edge sets of $G$ and $\varphi(H).$ We consider the following optimization problem. Given graphs $G,$ $H,$ and a weight function $\omega$ assigning nonnegative weights to pairs of vertices of $V(G),$ the task is to find $\varphi$ of minimum weight $\omega(\varphi)= \sum_{xy\in E(H)}\omega(\varphi(x)\varphi(y))$ such that the edge connectivity of the superposition $F$ of $G$ and $H$ with respect to $\varphi$ is higher than the edge connectivity of $G$. Our main result is the following “dichotomy” complexity classification. We say that a class of graphs $\mathcal{C}$ has bounded vertex-cover number if there is a constant $t$ depending on $\mathcal{C}$ only such that the vertex-cover number of every graph from $\mathcal{C}$ does not exceed $t.$ We show that for every class of graphs $\mathcal{C}$ with bounded vertex-cover number, the problems of superposing into a connected graph $F$ and to 2-edge connected graph $F$ are solvable in polynomial time when $H\in\mathcal{C}.$ On the other hand, for any hereditary class $\mathcal{C}$ with unbounded vertex-cover number, both problems are NP-hard when $H\in\mathcal{C}.$ For the unweighted variants of structured augmentation problems, i.e., the problems where the task is to identify whether there is a superposition of graphs of required connectivity, we provide necessary and sufficient combinatorial conditions on the existence of such superpositions. These conditions imply polynomial time algorithms solving the unweighted variants of the problems.

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.

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.

In the I nterval C ompletion problem we are given an n -vertex graph G and an integer k , and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of I nterval C ompletion was asked by Kaplan et al. [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger et al. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O ( k 2 k n 3 m ). We give the first subexponential parameterized algorithm solving I nterval C ompletion in time k O (√ k ) n O (1) . This adds I nterval C ompletion to a very small list of parameterized graph modification problems solvable in subexponential time.

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.

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.

We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem Longest Detour asks for an (s,t)-path in G that is at least k longer than a shortest (s,t)-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable (FPT) on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time exp(O(k)) poly(n). This matches (up to the base of the exponential) the best algorithms for finding a path of length at least k. Furthermore, we study the related problem Exact Detour that asks whether a graph G contains an (s,t)-path that is exactly k longer than a shortest (s,t)-path. For this problem, we obtain a randomized algorithm with running time about 2.746^k, and a deterministic algorithm with running time about 6.745^k, showing that this problem is FPT as well. Our algorithms for Exact Detour apply to both undirected and directed graphs.

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

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time | V ( H )| o (| V ( G )|) . We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of | V ( H )| o (| V ( H )|) -time algorithm deciding if graph G is a subgraph of H . For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems. Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.

The notion of resolving sets in a graph was introduced by Slater [Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Util. Math., Winnipeg, 1975, pp. 549--559] and Harary and Melter [Ars Combin., 2 (1976), pp. 191--195] as a way of uniquely identifying every vertex in a graph. A set of vertices in a graph is a resolving set if for any pair of vertices $x$ and $y$ there is a vertex in the set which has distinct distances to $x$ and $y$. A smallest resolving set in a graph is called a metric basis and its size, the metric dimension of the graph. The problem of computing the metric dimension of a graph is a well-known NP-hard problem and while it was known to be polynomial time solvable on trees, it is only recently that efforts have been made to understand its computational complexity on various restricted graph classes. In recent work, Foucaud [Algorithmica, 2016, pp. 1--31] showed that this problem is NP-complete even on interval graphs. They complemented this result by also showing that it is fixed-parameter tractable (FPT) parameterized by the metric dimension of the graph. In this work, we show that this FPT result can in fact be extended to all graphs of bounded tree-length. This includes well-known classes like chordal graphs, AT-free graphs, and permutation graphs. We also show that this problem is FPT parameterized by the modular-width of the input graph.

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.

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.

We overview the recent progress in solving intractable optimization problems on planar graphs as well as other classes of sparse graphs. In particular, we discuss how tools from Graph Minors theory can be used to obtain: * subexponential parameterized algorithms * approximation algorithms, and * preprocessing and kernelization algorithms on these classes of graphs.

In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of Interval Completion was asked by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O(k2kn3m). We give the first subexponential parameterized algorithm solving Interval Completion in time . This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.

We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time |V (H)|o(|V (G)|). We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of |V (H)|o(|V (H)|)-time algorithm deciding if graph G is a subgraph of H. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.

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.

We prove that in a graph with n vertices, induced chordal and interval subgraphs with the maximum number of vertices can be found in time $$\mathcal {O}(2^{\lambda n})$$ for some $$\lambda <1$$ . These are the first algorithms breaking the trivial $$2^n n^{\mathcal {O}(1)}$$ bound of the brute-force search for these problems.

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.

We give an algorithm that for an input $n$-vertex graph $G$ and integer $k>0$, in time $2^{O(k)} n$, either outputs that the treewidth of $G$ is larger than $k$, or gives a tree decomposition of $G$ of width at most $5k+4$. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single exponential in $k$ and linear in $n$. Treewidth-based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single exponential in the treewidth and linear in the input size.

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.

The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a selected path is its exposure, which is the total weight of vertices in its closed neighborhood. In order to minimize the risk of intercepting the information, we are interested in selecting a secluded path, i.e. a path with a small exposure. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure of the tree is minimized. In this work, we obtain the following results about parameterized complexity of secluded connectivity problems. We start from an observation that being parameterized by the size of the exposure, the problem is fixed-parameter tractable (FPT). More precisely, we give an algorithm deciding if a graph G with a given cost function w:V(G)->N contains a secluded path of exposure at most k with the cost at most C in time O(3^{k/3}(n+m) log W), where W is the maximum value of w on an input graph G. Similarly, Secluded Steiner Tree is solvable in time O(2^{k}k^2 (n+m) log W). The main result of this paper is about "above guarantee" parameterizations for secluded problems. We show that Secluded Steiner Tree is FPT being parameterized by r+p, where p is the number of the terminals, l the size of an optimum Steiner tree, and r=k-l. We complement this result by showing that the problem is co-W[1]-hard when parameterized by r only. We also investigate Secluded Steiner Tree from kernelization perspective and provide several lower and upper bounds when parameters are the treewidth, the size of a vertex cover, maximum vertex degree and the solution size. Finally, we refine the algorithmic result of Chechik et al. by improving the exponential dependence from the treewidth of the input graph.

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.

We obtain an algorithmic metatheorem for the following optimization problem. Let $\varphi$ be a counting monadic second order logic (CMSO) formula and $t\geq 0$ be an integer. For a given graph $G=(V,E)$, the task is to maximize $|X|$ subject to the following: there is a set $ F\subseteq V$ such that $X\subseteq F $, the subgraph $G[F]$ induced by $F$ is of treewidth at most $t$, and the structure $(G[F],X)$ models $\varphi$, i.e., $(G[F],X)\models\varphi$. We give an algorithm solving this optimization problem on any $n$-vertex graph $G$ in time ${\cal O}(|\Pi_G| \cdot n^{t+4}\cdot f(t,\varphi))$, where $\Pi_G$ is the set of all potential maximal cliques in $G$ and $f$ is a function of $t$ and $\varphi$ only. Pipelined with the known bounds on the number of potential maximal cliques in different graph classes, there are a plethora of algorithmic consequences extending and subsuming many known results on polynomial-time algorithms for graph classes. We also show that all potential maximal cliques of $G$ can be enumerated in time ${\cal O}(1.7347^n)$. This implies the existence of an exact exponential algorithm of running time ${\cal O}(1.7347^n)$ for many NP-hard problems related to finding maximum induced subgraphs with different properties.

In the Proper Interval Completion problem we are given a graph $G$ and an integer $k$, and the task is to turn $G$ using at most $k$ edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir, and Tarjan [SIAM J. Comput., 28 (1999), pp. 1906--1922], who showed an algorithm for the problem working in $\mathcal{O}(16^k\cdot (n+m))$ time. In this paper we present an algorithm with running time $k^{\mathcal{O}(k^{2/3})} + \mathcal{O}(nm(kn+m))$, which is the first subexponential parameterized algorithm for Proper Interval Completion.

We study the paramereteized complexity of the following connectivity problem. For a vertex subset U of a graph G, trees T_1,...,T_s of G are completely independent spanning trees of U if each of them contains U, and for every two distinct vertices u,v in U, the paths from u to v in T_1,...,T_s are pairwise vertex disjoint except for end-vertices u and v. Then for a given s >= 2 and a parameter k, the task is to decide if a given n-vertex graph G contains a set U of size at least k such that there are s completely independent spanning trees of U. The problem is known to be NP-complete already for s=2. We prove the following results: (*) For s=2 the problem is solvable in time 2^{O(k)}*n^{O(1)}. (*) For s=2 the problem does not admit a polynomial kernel unless NP subseteq coNP/poly. (*) For arbitrary s, we show that the problem is solvable in time f(s,k)n^{O(1)} for some function f of s and k only.

Let M = (E,I) be a matroid and let S = {S1, …, St} 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 ∊ Ŝ disjoint from Y with ∪ Y ∊ I. By the classical result of Bollobás, in a uniform matroid, every family of sets of size p has a q-representative family with at most 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 . As observed by Marx, Lovász's proof is constructive. In this paper we show how Lovász's proof can be turned into an algorithm constructing a q-representative family of size at most in time bounded by a polynomial in , 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 Long Directed Cycle 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 time algorithm, we have that a directed cycle of length at least logn, if such cycle exists, can be found in polynomial time. As it was shown by Björklund, Husfeldt, and Khanna [ICALP 2004], under an appropriate complexity assumption, it is impossible to improve this guarantee by more than a constant factor. Thus our algorithm not only improves over the best previous logn/log logn bound of Gabow and Nie SODA 2004] but also closes the gap between known lower and upper bounds for this problem. In the Minimum Equivalent Graph (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. The existence of a single-exponential cn-time algorithm for some constant c > 1 for MEG was open since the work of Moyles and Thompson [JACM 1969]. To demonstrate the diversity of applications of the approach, we provide an alternative proof of the results recently obtained by Bodlaender, Cygan, Kratsch and Nederlof for algorithms on graphs of bounded treewidth, who showed that many “connectivity” problems such as Hamiltonian Cycle or Steiner Tree can be solved in time 2 (t)n on n-vertex graphs of treewidth at most t. We believe that expressing graph problems in “matroid language” shed light on what makes it possible to solve connectivity problems single-exponential time parameterized by treewidth. For the special case of uniform matroids on n elements, we give a faster algorithm computing a representative family in time . We use this algorithm to provide the fastest known deterministic parameterized algorithms for k-Path, k-Tree, and more generally, for k-Subgraph Isomorphism, where the k-vertex pattern graph is of constant treewidth. For example, our k-Path algorithm runs in time on weighted graphs with maximum edge weight W.

We obtain an algorithmic meta-theorem for the following optimization problem. Let φ be a Counting Monadic Second Order Logic (CMSO) formula and t ≥ 0 be an integer. For a given graph G = (V, E), the task is to maximize |X| subject to the following: there is a set F ⊆ V such that X ⊆ F, the subgraph G[F] induced by F is of treewidth at most t, and structure (G[F], X) models φ, i.e. (G[F], X) ⊨ φ. Special cases of this optimization problem are the following generic examples. Each of these special cases contains various problems as a special subcase: Maximum Induced Subgraph with ≤ ℓ copies of ℱm-cycles, where for fixed nonnegative integers m and ℓ, the task is to find a maximum induced subgraph of a given graph with at most ℓ vertex-disjoint cycles of length 0 (mod m). For example, this encompasses the problems of finding a maximum induced forest or a maximum subgraph without even cycles. Minimum ℱ-Deletion, where for a fixed finite set of graphs ℱ containing a planar graph, the task is to find a maximum induced subgraph of a given graph containing no graph from ℱ as a minor. Examples of Minimum ℱ-Deletion are the problems of finding a minimum vertex cover or a minimum number of vertices required to delete from the graph to obtain an outerplanar graph. Independent ℋ-packing, where for a fixed finite set of connected graphs ℋ, the task is to find an induced subgraph F of a given graph with the maximum number of connected components, such that each connected component of F is isomorphic to some graph from ℋ. For example, the problem of finding a maximum induced matching or packing into nonadjacent triangles, are the special cases of this problem. We give an algorithm solving the optimization problem on an n-vertex graph G in time (|ΠG| · nt+4 · f(t, φ)), where ΠG is the set of all potential maximal cliques in G and f is a function of t and φ only. We also show how similar running time can be obtained for the weighted version of the problem. Pipelined with known bounds on the number of potential maximal cliques, we derive a plethora of algorithmic consequences extending and subsuming many known results on algorithms for special graph classes and exact exponential algorithms.

Let F be a family of graphs. In the F-Completion problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph from F as an induced subgraph. It appeared recently that special cases of F-Completion, the problem of completing into a chordal graph known as "Minimum Fill-in", corresponding to the case of F={C_4,C_5,C_6,...}, and the problem of completing into a split graph, i.e., the case of F={C_4,2K_2,C_5}, are solvable in parameterized subexponential time. The exploration of this phenomenon is the main motivation for our research on F-Completion. In this paper we prove that completions into several well studied classes of graphs without long induced cycles also admit parameterized subexponential time algorithms by showing that: - The problem Trivially Perfect Completion is solvable in parameterized subexponential time, that is F-Completion for F={C_4,P_4}, a cycle and a path on four vertices. - The problems known in the literature as Pseudosplit Completion, the case where F={2K_2,C_4}, and Threshold Completion, where F={2K_2,P_4,C_4}, are also solvable in subexponential time. We complement our algorithms for $F$-Completion with the following lower bounds: - For F={2K_2}, F={C_4}, F={P_4}, and F={2K_2,P_4}, F-Completion cannot be solved in time 2^o(k).n^O(1) unless the Exponential Time Hypothesis (ETH) fails. Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of F-Completion problems for F contained inside {2K_2,C_4,P_4}.

We obtain asymptotically tight algorithmic bounds for Max-Cut and Edge Dominating Set problems on graphs of bounded clique-width. We show that on an $n$-vertex graph of clique-width $t$ both problems (1) cannot be solved in time $f(t)n^{o(t)}$ for any function $f$ of $t$ unless exponential time hypothesis fails, and (2) can be solved in time $n^{O(t)}$.

We study the parameterized complexity of the following Euler subgraph problems: (a) Large Euler Subgraph: For a given graph $G$ and integer parameter $k$, does $G$ contain an induced Eulerian subgraph with at least $k$ vertices? (b) Long Circuit: For a given graph $G$ and integer parameter $k$, does $G$ contain an Eulerian subgraph with at least $k$ edges? Our main algorithmic result is that Large Euler Subgraph is fixed parameter tractable (FPT) on undirected graphs. The complexity of the problem changes drastically on directed graphs, and we obtain the following complexity dichotomy: Large Euler Subgraph is NP-hard for every fixed $k>3$ and is solvable in polynomial time for $k\leq 3$. For Long Circuit, we prove that the problem is FPT on directed and undirected graphs.

The behavior of users in social networks is often observed to be affected by the actions of their friends. Bhawalkar et al. (ICALP '12) introduced a formal mathematical model for user engagement in social networks where each individual derives a benefit proportional to the number of its friends which are engaged. Given a threshold degree k the equilibrium for this model is a maximal subgraph whose minimum degree is at least k. However the dropping out of individuals with degrees less than k might lead to a cascading effect of iterated withdrawals such that the size of equilibrium subgraph becomes very small. To overcome this some special vertices called "anchors" are introduced: these vertices need not have large degree. Bhawalkar et al. considered the Anchored k-Core problem: Given a graph G and integers b, k and p do there exist sets of vertices B, H such that B is a subset of H, size of B is at most b and size of H is at least p, and every vertex v which is in H but not in B has degree at least k in the induced subgraph G[H]. They showed that the problem is NP-hard for all k greater equal 2, and gave some inapproximability and fixed-parameter intractability results. In this paper we give improved hardness results for this problem. In particular we show that the Anchored k-Core problem is W[1]-hard parameterized by p, even for k=3. This improves the result of Bhawalkar et al. (who show W[2]-hardness parameterized by b) as our parameter is always bigger since p is greater equal than b. Then we answer a question of Bhawalkar et al. by showing that the Anchored k-Core problem remains NP-hard on planar graphs for all k greater equal 3, even if the maximum degree of the graph is k+2. Finally we show that the problem is FPT on planar graphs parameterized by b for all k greater equal 7.

We give an algorithm that for an input n-vertex graph G and integer k > 0, in time O(ckn) either outputs that the tree width of G is larger than k, or gives a tree decomposition of G of width at most 5k + 4. This is the first algorithm providing a constant factor approximation for tree width which runs in time single-exponential in k and linear in n. Tree width based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the tree width and linear in the input size.

We consider the Directed Anchored k-Core problem, where the task is for a given directed graph G and integers b, k and p, to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (the anchors) of H have in-degree at least k. For undirected graphs, this problem was introduced by Bhawalkar, Kleinberg, Lewi, Roughgarden, and Sharma [ICALP 2012]. We undertake a systematic analysis of the computational complexity of Directed Anchored k-Core and show that: - The decision version of the problem is NP-complete for every k>=1 even if the input graph is restricted to be a planar directed acyclic graph of maximum degree at most k+2. - The problem is fixed parameter tractable (FPT) parameterized by the size of the core p for k=1, and W[1]-hard for k>=2. - When the maximum degree of the graph is at most Delta, the problem is FPT parameterized by p+Delta if k>=Delta/2.

We give a fixed-parameter tractable (FPT) approximation algorithm computing the pathwidth of a tournament, and more generally, of a semi-complete digraph. Based on this result, we prove the following. The Topological Containment problem is FPT on semi-complete digraphs. More precisely, given a semi-complete n-vertex digraph T and a digraph H, one can check in time f(|H|)n3 log n, where f is some elementary function, whether T contains a subdivision of H as a subgraph. The previous known algorithm for this problem was due to Fradkin and Seymour and was of running time nm(|H|), where m is a quadruple-exponential function. The Rooted Immersion problem is FPT on semi-complete digraphs. The complexity of this problem was left open by Fradkin and Seymour. Our algorithm solves it in time g(|H|)n4 log n, for some elementary function g. Vertex deletion distance to every immersion-closed class of semi-complete digraphs is fixed-parameter tractable. More precisely, for every immersion-closed class П of semi-complete digraphs, there exists an algorithm with running time h(k)n3 log n that checks, whether one can remove at most k vertices from a semi-complete n-vertex digraph to obtain a digraph from class Π. Here, h is some function depending on the class Π.

In the Correlation Clustering problem, also known as Cluster Editing, we are given an undirected graph G and a positive integer k; the task is to decide whether G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, that is, by adding or deleting at most k edges. The motivation of the problem stems from various tasks in computational biology (Ben-Dor et al., Journal of Computational Biology 1999) and machine learning (Bansal et al., Machine Learning 2004). Although in general Correlation Clustering is APX-hard (Charikar et al., FOCS 2003), the version of the problem where the number of cliques may not exceed a prescribed constant p admits a PTAS (Giotis and Guruswami, SODA 2006). We study the parameterized complexity of Correlation Clustering with this restriction on the number of cliques to be created. We give an algorithm that - in time O(2^{O(sqrt{pk})} + n+m) decides whether a graph G on n vertices and m edges can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies. We complement these algorithmic findings by the following, surprisingly tight lower bound on the asymptotic behavior of our algorithm. We show that unless the Exponential Time Hypothesis (ETH) fails - for any constant 0 <= sigma <= 1, there is p = Theta(k^sigma) such that there is no algorithm deciding in time 2^{o(sqrt{pk})} n^{O(1)} whether an n-vertex graph G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies. Thus, our upper and lower bounds provide an asymptotically tight analysis of the multivariate parameterized complexity of the problem for the whole range of values of p from constant to a linear function of k.

We give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor.

Minimum Fill-in is a fundamental and classical problem arising in sparse matrix computations. In terms of graphs it can be formulated as a problem of finding a triangulation of a given graph with the minimum number of edges. By the classical result of Rose, Tarjan, Lueker, and Ohtsuki from 1976, an inclusion minimal triangulation of a graph can be found in polynomial time but, as it was shown by Yannakakis in 1981, finding a triangulation with the minimum number of edges is NP-hard. In this paper, we study the parameterized complexity of local search for the Minimum Fill-in problem in the following form: Given a triangulation H of a graph G, is there a better triangulation, i.e. triangulation with less edges than H, within a given distance from H? We prove that this problem is fixed-parameter tractable (FPT) being parameterized by the distance from the initial triangulation by providing an algorithm that in time O(f(k) |G|^{O(1)}) decides if a better triangulation of G can be obtained by swapping at most k edges of H. Our result adds Minimum Fill-in to the list of very few problems for which local search is known to be FPT.

The Minimum Fill-in problem is used to decide if a graph can be triangulated by adding at most $k$ edges. In 1994, Kaplan, Shamir, and Tarjan showed that the problem is solvable in time $\mathcal{O}(2^{\mathcal{O}({k})}+k^2 nm)$ on graphs with $n$ vertices and $m$ edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving Minimum Fill-in in time $\mathcal{O}(2^{\mathcal{O}(\sqrt{k}\log{k})} +k^2 nm)$. This substantially lowers the complexity of the problem. Techniques developed for Minimum Fill-in can be used to obtain subexponential parameterized algorithms for several related problems, including Minimum Chain Completion, Chordal Graph Sandwich, and Triangulating Colored Graph.

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

Let F be a finite set of graphs. In the F-DELETION problem, we are given an n-vertex graph G and an integer k as input, and asked whether at most k vertices can be deleted from G such that the resulting graph does not contain a graph from F as a minor. F-DELETION is a generic problem and by selecting different sets of forbidden minors F, one can obtain various fundamental problems such as VERTEX COVER, FEEDBACK VERTEX SET or TREEWIDTH η-DELETION. In this paper we obtain a number of generic algorithmic results about F-DELETION, when F contains at least one planar graph. The highlights of our work are · A constant factor approximation algorithm for the optimization version of F-DELETION; · A linear time and single exponential parameterized algorithm, that is, an algorithm running in time O(2O(k)n), for the parameterized version of F-DELETION where all graphs in F are connected; · A polynomial kernel for parameterized F-DELETION. These algorithms unify, generalize, and improve a multitude of results in the literature. Our main results have several direct applications, but also the methods we develop on the way have applicability beyond the scope of this paper. Our results - constant factor approximation, polynomial kernelization and FPT algorithms - are stringed together by a common theme of polynomial time preprocessing.

Bidimensionality theory was introduced by Demaine et al. [JACM 2005] as a framework to obtain algorithmic results for hard problems on minor closed graph classes. The theory has been successfully applied to yield subexponential time parameterized algorithms, EPTASs and linear kernels for many problems on families of graphs excluding a fixed graph H as a minor. In this paper we use several of the key ideas from Bidimensionality to give a new generic approach to design EPTASs and subexponential time parameterized algorithms for problems on classes of graphs which are not minor closed, but instead exhibit a geometric structure. In particular we present EPTASs and subexponential time parameterized algorithms for Feedback Vertex Set, Vertex Cover, Connected Vertex Cover, on map graphs and unit disk graphs, PTASs for Diamond Hitting Set on map graphs and unit disk graphs, and a PTAS and a subexponential time algorithm for Cycle Packing on unit disk graphs. To the best of our knowledge, these results were previously unknown, with the exception of the EPTAS and a subexponential time parameterized algorithm on unit disk graphs for Vertex Cover, which were obtained by Marx [ESA 2005] and Alber and Fiala [J. Algorithms 2004], respectively. Our results are based on the recent decomposition theorems proved by Fomin et al. in [SODA 2011] and novel grid-excluding theorems in unit disk and map graphs without large cliques. Our algorithms work directly on the input graph and do not require the geometric representations of the input graph. We also show that our approach can not be extended in its full generality to more general classes of geometric graphs, such as intersection graphs of unit balls in ℝd, d ≥ 3. Specifically, we prove that Feedback Vertex Set on unit-ball graphs in ℝ3 neither admits PTASs unless P=NP, nor subexponential time algorithms unless the Exponential Time Hypothesis fails. Additionally, we show that the decomposition theorems which our approach is based on, fail for disk graphs and that therefore any extension of our results to disk graphs would require new algorithmic ideas. On the other hand, we prove that our EPTASs and subexponential time algorithms for Vertex Cover and Connected Vertex Cover carry over both to disk graphs and to unit-ball graphs in ℝd for every fixed d.

We give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a minor. In other words, we give polynomial time algorithms that, for a given H-minor free graph G and positive integer k, output an H-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. Prior to our work, the only polynomial kernel for Dominating Set on graphs excluding a fixed graph H as a minor was due to Alon and Gutner [ECCC 2008, IWPEC 2009] and to Philip, Raman, and Sikdar [ESA 2009] but the size of their kernel is kc(H), where c(H) is a constant depending on the size of H. Alon and Gutner asked explicitly, whether one can obtain a linear kernel for Dominating Set on H-minor free graphs. We answer this question in affirmative. For Connected Dominating Set no polynomial kernel on H-minor free graphs was known prior to our work. Our results are based on a novel generic reduction rule producing an equivalent instance of the problem with treewidth O(√k). The application of this rule in a divide-and-conquer fashion together with protrusion techniques brings us to linear kernels. As a byproduct of our results we obtain the first subexponential time algorithms for Connected Dominating Set, a deterministic algorithm solving the problem on an n-vertex H-minor free graph in time 2O(√k log k) + nO(1) and a Monte Carlo algorithm of running time 2O(√k) + nO(1). For Dominating Set our results implies a significant simplification and refinement of a 2O(√k) nO(1) algorithm on H minor free graphs due to Demaine et al. [SODA 2003, J. ACM 2005].

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. Kaplan, Shamir, and Tarjan [FOCS 1994] have shown that the problem is solvable in time on graphs with n vertices and m edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving Minimum Fill-in in time . This substantially lowers the complexity of the problem. Techniques developed for Minimum Fill-in can be used to obtain subexponential parameterized algorithms for several related problems including Minimum Chain Completion, Chordal Graph Sandwich, and Triangulating Colored Graph.

Cai and Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs. For a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about - a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and - a connected k- vertex induced subgraph with all vertices of even degrees, the problem known as k-Vertex Eulerian Subgraph. We resolve both open problems and thus complete the characterization of even/odd subgraph problems from parameterized complexity perspective. We show that k-Edge Connected Odd Subgraph is FPT and that k-Vertex Eulerian Subgraph is W[1]-hard. Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges.

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

In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply.

We introduce a generic approach for counting subgraphs in a graph. The main idea is to relate counting subgraphs to counting graph homomorphisms. This approach provides new algorithms and unifies several well-known results in algorithms and combinatorics, including the recent algorithm of Björklund, Husfeldt, and Koivisto for computing the chromatic polynomial, the classical algorithm of Kohn et al. for counting Hamiltonian cycles, Ryser's formula for counting perfect matchings of a bipartite graph, and color-coding-based algorithms of Alon, Yuster, and Zwick. By combining our method with known combinatorial bounds, ideas from succinct data structures, partition functions, and the color coding technique, we obtain the following new results. The number of optimal bandwidth permutations of a graph on n vertices excluding a fixed graph as a minor can be computed in time $ 2^{n+o(n)} $, in particular, in time $\mathcal{O}(2^{n}n^3)$ for trees and in time $2^{n+\mathcal{O}(\sqrt{n})}$ for planar graphs. Counting all maximum planar subgraphs, subgraphs of bounded genus, or more generally subgraphs excluding a fixed graph M as a minor can be done in $2^{\mathcal{O}(n)}$ time. Counting all subtrees with a given maximum degree (a generalization of counting Hamiltonian paths) of a given graph can be done in time $2^{\mathcal{O}(n)}$. A generalization of Ryser's formula is, Let G be a graph with an independent set of size $\ell$. Then the number of perfect matchings in G can be found in time $\mathcal{O}(2^{n-\ell} n^3)$. Let ${\cal H}$ be a graph class excluding a fixed graph M as a minor. Then the maximum number of vertex disjoint subgraphs from ${\cal H}$ in a graph G on n vertices can be found in time $2^{\mathcal{O}(n)}$. In order to show this, we prove that there exists a constant $c_M$ depending only on M such that the number of nonisomorphic n-vertex graphs in ${\cal H}$ is at most $c_M^n$. Let F be a k-vertex graph of treewidth t and let G be an n-vertex graph. A subgraph of G isomorphic to F (if one exists) can be found in $\mathcal{O}(4.32^k \cdot k \cdot t \cdot n^{t+1})$ expected time using $\mathcal{O}(\log{k} \cdot n^{t+1})$ space.

Cops and robber is a classical pursuit-evasion game on undirected graphs, where the task is to identify the minimum number of cops sufficient to catch the robber. In this paper, we investigate the changes in problem's complexity and combinatorial properties with constraining the following natural game parameters: fuel, the number of steps each cop can make; cost, the total sum of steps along edges all cops can make; and time, the number of rounds of the game.

The k -Leaf Out-Branching problem is to find an out-branching, that is a rooted oriented spanning tree, with at least k leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the k -Leaf-Out-Branching problem. We give the first polynomial kernel for Rooted k -Leaf-Out-Branching, a variant of k -Leaf-Out-Branching where the root of the tree searched for is also a part of the input. Our kernel with O ( k 3 ) vertices is obtained using extremal combinatorics. For the k -Leaf-Out-Branching problem, we show that no polynomial-sized kernel is possible unless coNP is in NP/poly . However, our positive results for Rooted k -Leaf-Out-Branching immediately imply that the seemingly intractable k -Leaf-Out-Branching problem admits a data reduction to n independent polynomial-sized kernels. These two results, tractability and intractability side by side, are the first ones separating Karp kernelization from Turing kernelization . This answers affirmatively an open problem regarding “cheat kernelization” raised by Mike Fellows and Jiong Guo independently.

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O *(2 n ). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the Traveling Salesman problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing Treewidth under the restriction that the space used is only polynomial and give a simple O *(4 n ) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, Treewidth can be computed in O *(2.9512 n ) time and polynomial space.

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop kernelization algorithms for the problem on several classes of sparse graphs. We obtain linear kernels on planar graphs, and kernels of size O(k^{3/2}) in graphs excluding some fixed graph as a minor and in graphs of bounded degeneracy. As a byproduct of our results, we obtain approximation algorithms with approximation ratios O(log{k}) on planar graphs and O(sqrt{k} log{k}) on H-minor-free graphs. These results significantly improve the previously known kernelization and approximation results for Minimum Fill-in on sparse graphs.

Bidimensionality theory appears to be a powerful framework for the development of meta-algorithmic techniques. It was introduced by Demaine et al. [J. ACM 2005] as a tool to obtain sub-exponential time parameterized algorithms for problems on H-minor free graphs. Demaine and Hajiaghayi [SODA 2005] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems, and subsequently improved these results to EPTASs. Fomin et. al [SODA 2010] established a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In this paper we revisit bidimensionality theory from the perspective of approximation algorithms and redesign the framework for obtaining EPTASs to be more powerful, easier to apply and easier to understand. One of the important conditions required in the framework developed by Demaine and Hajiaghayi [SODA 2005] is that to obtain an EPTAS for a graph optimization problem П, we have to know a constant-factor approximation algorithm for П. Our approach eliminates this strong requirement, which makes it amenable to more problems. At the heart of our framework is a decomposition lemma which states that for “most” bidimensional problems, there is a polynomial time algorithm which given an H-minor-free graph G as input and an ε > 0 outputs a vertex set X of size ε · OPT such that the treewidth of G\X is O(1/ε). Here, OPT is the objective function value of the problem in question 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 Cycle Packing, Vertex-H-Packing, Maximum Leaf Spanning Tree, and Partial r-Dominating Set no EPTASs on planar graphs were previously known.

We study a general class of problems called F-deletion problems. In an 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 F of forbidden minors. We obtain a number of algorithmic results on the F-deletion problem when F contains a planar graph. We give (1) a linear vertex kernel on graphs excluding $t$-claw $K_{1,t}$, the star with $t$ leves, as an induced subgraph, where $t$ is a fixed integer. (2) 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 F contains graph $θ_c$ as a minor for a fixed integer $c$. The graph $θ_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 {\sc Vertex Cover}, {\sc Feedback Vertex Set} and Diamond Hitting Set. The generic kernelization algorithm is based on a non-trivial application of protrusion techniques, previously used only for problems on topological graph classes.

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending the tractability of many problems in database theory and artificial intelligence. In this paper, we study the approximability of (generalized, fractional) hypertree width of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph [Formula: see text] is constant factor sandwiched by the treewidth of its incidence graph when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above in which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some [Formula: see text]-minor-free graph class.

We present a fast local search algorithm that finds an improved solution (if there is any) in the k-exchange neighborhood of the given solutionto an instance of Weighted Feedback Arc Set in Tournaments. More precisely,given an arc weighted tournament T on n vertices and a feedback arc set F (a set of arcs whose deletion from T turns it into a directed acyclic graph), our algorithm decides in time O(2o(k) n log n) if there is a feedback arc set of smaller weight and that differs from F in at most k arcs. To our knowledge this is the first algorithm searching the k-exchange neighborhood of an NP-complete problem that runs in (parameterized) subexponential time. Using this local search algorithm for Weighted Feedback Arc Set in Tournaments, we obtain subexponential time algorithms for a local search variant of Kemeny Ranking — a problem in social choice theory and of One-Sided Cross Minimization — a problem in graph drawing.

Many NP-hard problems can be solved efficiently when the input is restricted to graphs of bounded tree-width or clique-width. In particular, by the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the tree-width of the input graph. On the other hand if we restrict ourselves to graphs of clique-width at most t, then there are many natural problems for which the running time of the best known algorithms is of the form nf(t), where n is the input length and f is some function. It was an open question whether natural problems like Graph Coloring, Max-Cut, Edge Dominating Set, and Hamiltonian Path are fixed parameter tractable when parameterized by the clique-width of the input graph. As a first step toward obtaining lower bounds for clique-width parameterizations, in [SODA 2009], we showed that unless FPT≠W[1], there is no algorithm with run time O(g(t) · nc), for some function g and a constant c not depending on t, for Graph Coloring, Edge Dominating Set and Hamiltonian Path. But the lower bounds obtained in [SODA 2009] are weak when compared to the upper bounds on the time complexity of the known algorithms for these problems when parameterized by the clique-width. In this paper, we obtain the asymptotically tight bounds for Max-Cut and Edge Dominating Set by showing that both problems cannot be solved in time f(t)no(t), unless Exponential Time Hypothesis (ETH) collapses; and can be solved in time nO(t), where f is an arbitrary function of t, on input of size n and clique-width at most t. We obtain our lower bounds by giving non-trivial structure-preserving “linear FPT reductions”.

Bidimensionality theory appears to be a powerful framework in the development of meta-algorithmic techniques. It was introduced by Demaine et al. [J. ACM 2005] as a tool to obtain sub-exponential time parameterized algorithms for bidimensional problems on H-minor free graphs. Demaine and Hajiaghayi [SODA 2005] extended the theory to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this paper, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In parameterized complexity, each problem instance comes with a parameter k and the parameterized problem is said to admit a linear kernel if there is a polynomial time algorithm, called a kernelization algorithm, that reduces the input instance to an equivalent instance (called kernel) with size linearly bounded by k. We show that “essentially” all bidimensional problems not only have sub-exponential time algorithms and PTASs but they also have linear kernels, affirmatively answering an open question from [J. ACM 2005] where the existence of linear kernels was conjectured for the first time. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies the separation property and is of finite integer index, admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph H) H as a minor. Recently, Bodlaender et al. [FOCS 2009] laid the foundation for obtaining meta-algorithmic results for kernelization and showed that various problems satisfying some logical and compactness properties have polynomial, even linear kernels on graphs of bounded genus. With the use of bidimensionality we are able to extend these results to minor-free and apex-minor-free graphs. Our results imply that a multitude of bidimensional problems, which include Dominating Set, Feedback Vertex Set, Edge Dominating Set, Vertex Cover, r-Dominating Set, Connected Dominating Set, Cycle Packing, Connected Vertex Cover, Almost Constant Treewidth, and various other vertex covering and packing 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.

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, $k$-Leaf Out-Branching, which is to find an oriented spanning tree with at least $k$ leaves, we obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k} \log k)} n+ n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed graph $H$ as a minor. For the special case when the input directed graph is planar, the running time can be improved to $2^{\cO(\sqrt{k} )}n + n^{\cO(1)}$. The second example is a generalization of the {\sc Directed Hamiltonian Path} problem, namely $k$-Internal Out-Branching, which is to find an oriented spanning tree with at least $k$ internal vertices. We obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k} \log k)} + n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed apex graph $H$ as a minor. Finally, we observe that for any $\ve>0$, the $k$-Directed Path problem is solvable in time $\cO((1+\ve)^k n^{f(\ve)})$, where $f$ is some function of $\ve$. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem specific combinatorial structures and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.

Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulation problems including Minimum Fill-in and Treewidth. We discover unexpected applications of these notions to the field of moderate exponential algorithms. In particular, we show that given an n-vertex graph G together with its set of potential maximal cliques, and an integer t, it is possible in time the number of potential maximal cliques times $O(n^{O(t)})$ to find a maximum induced subgraph of treewidth t in G and for a given graph F of treewidth t, to decide if G contains an induced subgraph isomorphic to F. Combined with an improved algorithm enumerating all potential maximal cliques in time $O(1.734601^n)$, this yields that both the problems are solvable in time $1.734601^n$ * $n^{O(t)}$.

Abstract We show that the mixed search number and the linear‐width of interval graphs and of split graphs can be computed in linear time and in polynomial time, respectively. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are $W[1]$-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time $g(k)\cdot n^{O(1)}$ on n-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time $O(n^{f(k)})$ of many clique-width-based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely $FPT\neq W[1]$).

Polynomial time preprocessing to reduce instance size is one of the most commonly deployed heuristics to tackle computationally hard problems. 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, we can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this paper, we show that all problems expressible in Counting Monadic Second Order Logic and satisfying a compactness 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 compactness condition admit a linear kernel on graphs of bounded genus. The study of kernels on planar graphs was initiated by a seminal paper of Alber, Fellows, and Niedermeier [J. ACM, 2004 ] who showed that Planar Dominating Set admits a linear kernel. Following this result, a multitude of problems have been shown to admit linear kernels on planar graphs by combining the ideas of Alber et al. with problem specific reduction rules. Our theorems unify and extend all previously known kernelization results for planar graph problems. Combining our theorems with the Erdos-Posa property we obtain various new results on linear kernels for a number of packing and covering problems.

A tournament $T = (V,A)$ is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on $n$ vertices and an integer parameter $k$, the {\sc Feedback Arc Set} problem asks whether thegiven digraph has a set of $k$ arcs whose removal results in an acyclicdigraph. The {\sc Feedback Arc Set} problem restricted to tournaments is knownas the {\sc $k$-Feedback Arc Set in Tournaments ($k$-FAST)} problem. In thispaper we obtain a linear vertex kernel for \FAST{}. That is, we give apolynomial time algorithm which given an input instance $T$ to \FAST{} obtains an equivalent instance $T'$ on $O(k)$ vertices. In fact, given any fixed $\epsilon > 0$, the kernelized instance has at most $(2 + \epsilon)k$ vertices.Our result improves the previous known bound of $O(k^2)$ on the kernel size for\FAST{}. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for \FAST.

Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number ($k$) of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by $k$. It was recently shown by Amini et. al. [{\em FSTTCS 08}\,] that {\sc Partial Vertex Cover} and {\sc Partial Dominating Set} are fixed parameter tractable on large classes of sparse graphs, namely $H$-minor free graphs, which include planar graphs and graphs of bounded genus. In particular, it was shown that on planar graphs both problems can be solved in time $2^{\cO(k)}n^{\cO(1)}$.

Many hard problems can be solved efficiently when the input is restricted to graphs of bounded treewidth. By the celebrated result of Courcelle, every decision problem expressible in monadic second order logic is fixed parameter tractable when parameterized by the treewidth of the input graph. Moreover, for every fixed k ≥ 0, such problems can be solved in linear time on graphs of treewidth at most k. In particular, this implies that basic problems like Dominating Set, Graph Coloring, Clique, and Hamiltonian Cycle are solvable in linear time on graphs of bounded treewidth. A significant amount of research in graph algorithms has been devoted to extending this result to larger classes of graphs. It was shown that some of the algorithmic meta-theorems for treewidth can be carried over to graphs of bounded clique-width. Courcelle, Makowsky, and Rotics proved that the analogue of Courcelle's result holds for graphs of bounded clique-width when the logical formulas do not use edge set quantifications. Despite of its generality, this does not resolve the parameterized complexity of many basic problems concerning edge subsets (like Edge Dominating Set), vertex partitioning (like Graph Coloring), or global connectivity (like Hamiltonian Cycle). There are various algorithms solving some of these problems in polynomial time on graphs of clique-width at most k. However, these are not fixed parameter tractable algorithms and have typical running times O(nf(k)), where n is the input length and f is some function. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, i.e. solvable in time O(g(k)·nc), for some function g and a constant c not depending on k. In this paper we resolve this problem by showing that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. This shows that the running time O(nf(k)) of many clique-width based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1])—the price we pay for generality.

The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the {\sc $k$-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\sc Rooted $k$-Leaf-Out-Branching}, a variant of {\sc $k$-Leaf-Out-Branching} where the root of the tree searched for is also a part of the input. Our kernel has cubic size and is obtained using extremal combinatorics. For the {\sc $k$-Leaf-Out-Branching} problem, we show that no polynomial kernel is possible unless the polynomial hierarchy collapses to third level by applying a recent breakthrough result by Bodlaender et al. (ICALP 2008) in a non-trivial fashion. However, our positive results for {\sc Rooted $k$-Leaf-Out-Branching} immediately imply that the seemingly intractable {\sc $k$-Leaf-Out-Branching} problem admits a data reduction to $n$ independent $O(k^3)$ kernels. These two results, tractability and intractability side by side, are the first ones separating {\it many-to-one kernelization} from {\it Turing kernelization}. This answers affirmatively an open problem regarding ``cheat kernelization'' raised by Mike Fellows and Jiong Guo independently.

The notions of hypertree width and generalized hypertree width were introduced by Gottlob, Leone, and Scarcello (PODS'99, PODS'01) in order to extend the concept of hypergraph acyclicity. These notions were further generalized by Grohe and Marx in SODA'06, who introduced the fractional hypertree width of a hypergraph. All these width parameters on hypergraphs are useful for extending tractability of many problems in database theory and artificial intelligence. Computing each of these width parameters is known to be an NP-hard problem. Moreover, the (generalized) hypertree width of an n-vertex hypergraph cannot be approximated within a logarithmic factor unless P=NP. In this paper, we study the approximability of (generalized, fractional) hyper treewidth of sparse hypergraphs where the criterion of sparsity reflects the sparsity of their incidence graphs. Our first step is to prove that the (generalized, fractional) hypertree width of a hypergraph is constant-factor sandwiched by the treewidth of its incidence graph, when the incidence graph belongs to some apex-minor-free graph class (the family of apex-minor-free graph classes includes planar graphs and graphs of bounded genus). This determines the combinatorial borderline above which the notion of (generalized, fractional) hypertree width becomes essentially more general than treewidth, justifying that way its functionality as a hypergraph acyclicity measure. While for more general sparse families of hypergraphs treewidth of incidence graphs and all hypertree width parameters may differ arbitrarily, there are sparse families where a constant factor approximation algorithm is possible. In particular, we give a constant factor approximation polynomial time algorithm for (generalized, fractional) hypertree width on hypergraphs whose incidence graphs belong to some H-minor-free graph class. This extends the results of Feige, Hajiaghayi, and Lee from STOC'05 on approximating treewidth of H-minor-free graphs.

For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such recursive algorithms is still far from producing tight worst-case running time bounds. Motivated by this, we use an approach, that we call “Measure & Conquer”, as an attempt to step beyond such limitations. The approach is based on the careful design of a nonstandard measure of the subproblem size; this measure is then used to lower bound the progress made by the algorithm at each branching step. The idea is that a smarter measure may capture behaviors of the algorithm that a standard measure might not be able to exploit, and hence lead to a significantly better worst-case time analysis. In order to show the potentialities of Measure & Conquer, we consider two well-studied NP-hard problems: minimum dominating set and maximum independent set. For the first problem, we consider the current best algorithm, and prove (thanks to a better measure) a much tighter running time bound for it. For the second problem, we describe a new, simple algorithm, and show that its running time is competitive with the current best time bounds, achieved with far more complicated algorithms (and standard analysis). Our examples show that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.

The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e., a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two combinatorial results on the number of leaves in out-branchings. We show that (1) every strongly connected n-vertex digraph D with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; (2) if a strongly connected digraph D does not contain an out-branching with k leaves, then the pathwidth of its underlying graph $\mathrm{UG}(D)$ is $O(k\log k)$, and if the digraph is acyclic with a single vertex of in-degree zero, then the pathwidth is at most $4k$. The last result implies that it can be decided in time $2^{O(k\log^2k)}\cdot n^{O(1)}$ whether a strongly connected digraph on n vertices has an out-branching with at least k leaves. On acyclic digraphs the running time of our algorithm is $2^{O(k\log k)}\cdot n^{O(1)}$.

Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets.

We show that the treewidth and the minimum fill-in of an n-vertex graph can be computed in time $\mathcal{O}(1.8899^n)$. Our results are based on combinatorial proofs that an n-vertex graph has $\mathcal{O}(1.7087^n)$ minimal separators and $\mathcal{O}(1.8135^n)$ potential maximal cliques. We also show that for the class of asteroidal triple–free graphs the running time of our algorithms can be reduced to $\mathcal{O}(1.4142^n)$.

We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O (1.7159 n ). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159 n , thus improving on the trivial O (2 n /√ n ) bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms. Based on this result, we derive an O (2.8718 n ) algorithm for the domatic number problem.

We introduce a new approach to design parameterized algorithms on planar graphs which builds on the seminal results of Robertson and Seymour on graph minors. Graph minors provide a list of powerful theoretical results and tools. However, the widespread opinion in the graph algorithms community about this theory is that it is of mainly theoretical importance. In this paper we show how deep min-max and duality theorems from graph minors can be used to obtain exponential speed-up to many known practical algorithms for different domination problems. Our use of branch-width instead of the usual tree-width allows us to obtain much faster algorithms. By using this approach, we show that the k-dominating set problem on planar graphs can be solved in time O(2 15.13 \sqrt k + n 3 ).

We introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2 O(√k) n O(1) . Our results apply to a broad family of graph problems, called bidimensional problems , which includes many domination and problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, disk dimension, and many others restricted to bounded-genus graphs (phrased as bipartite-graph problem ). Furthermore, it is fairly straightforward to prove that a problem is bidimensional. In particular, our framework includes, as special cases, all previously known problems to have such subexponential algorithms. Previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and/or map graphs; we extend these results to apply to bounded-genus graphs as well. In a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph H as a minor. This bound depends linearly on the size |V(H)| of the excluded graph H and the genus g(G) of the graph G , and applies and extends the graph-minors work of Robertson and Seymour.Building on these results, we develop subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph H as a minor. In particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. Specifically, the running time is 2 O(√k) n h , where h is a constant depending only on H , which is polynomial for k = O (log 2 n ). We introduce a general approach for developing algorithms on H -minor-free graphs, based on structural results about H -minor-free graphs at the heart of Robertson and Seymour's graph-minors work. We believe this approach opens the way to further development on problems in H -minor-free graphs.

The ( k , r )-center problem asks whether an input graph G has ≤ k vertices (called centers ) such that every vertex of G is within distance ≤ r from some center. In this article, we prove that the ( k , r )-center problem, parameterized by k and R , is fixed-parameter tractable (FPT) on planar graphs, i.e., it admits an algorithm of complexity f ( k , r ) n O (1) where the function f is independent of n . In particular, we show that f ( k,r ) = 2 O ( r log r ) √k , where the exponent of the exponential term grows sublinearly in the number of centers. Moreover, we prove that the same type of FPT algorithms can be designed for the more general class of map graphs introduced by Chen, Grigni, and Papadimitriou. Our results combine dynamic-programming algorithms for graphs of small branchwidth and a graph-theoretic result bounding this parameter in terms of k and r . Finally, a byproduct of our algorithm is the existence of a PTAS for the r -domination problem in both planar graphs and map graphs.Our approach builds on the seminal results of Robertson and Seymour on Graph Minors, and as a result is much more powerful than the previous machinery of Alber et al. for exponential speedup on planar graphs. To demonstrate the versatility of our results, we show how our algorithms can be extended to general parameters that are “large” on grids. In addition, our use of branchwidth instead of the usual treewidth allows us to obtain much faster algorithms, and requires more complicated dynamic programming than the standard leaf/introduce/forget/join structure of nice tree decompositions. Our results are also unique in that they apply to classes of graphs that are not minor-closed, namely, constant powers of planar graphs and map graphs.

For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k, then the treewidth of the graph is bounded by some function of k. This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs, single-crossing-minor-free graphs, and graphs of bounded genus. In this paper we examine whether similar bounds can be obtained for larger minor-closed graph classes and for general families of graph parameters, including all those for which such behavior has been reported so far. Given a graph parameter P, we say that a graph family $\mathcal{F}$ has the parameter-treewidth property for P if there is an increasing function t such that every graph $G\in\mathcal{F}$ has treewidth at most t(P(G)). We prove as our main result that, for a large family of graph parameters called contraction-bidimensional, a minor-closed graph family $\mathcal{F}$ has the parameter-treewidth property if $\mathcal{F}$ has bounded local treewidth. We also show "if and only if" for some graph parameters, and thus, this result is in some sense tight. In addition we show that, for a slightly smaller family of graph parameters called minor-bidimensional, all minor-closed graph families $\mathcal{F}$, excluding some fixed graphs, have the parameter-treewidth property. The contraction-bidimensional parameters include many domination and covering graph parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set, and q-dominating set (for fixed q). We use our theorems to develop new fixed-parameter algorithms in these contexts.