Search

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 a longest cycle L is at least 2 δ (G) . Thus the "essential" part in 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)) . [ABSTRACT FROM AUTHOR]

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

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

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

A linkage in a graph G of size k is a subgraph L of G whose connected components are k paths. The pattern of a linkage of size k is the set of k pairs formed by the endpoints of these paths. A consequence of the Unique Linkage Theorem is the following: there exists a function f: N rightarrow N such that if a plane graph G contains a sequence\scrC of at least f(k) nested cycles and a linkage of size at most k whose pattern vertices lay outside the outer cycle of scrC, then G contains a linkage with the same pattern avoiding the inner cycle of\scrC. In this paper we prove the following variant of this result: Assume that all the cycles in\scrC are "orthogonally" traversed by a linkage P and L is a linkage whose pattern vertices may lay either outside the outer cycle or inside the inner cycle of scrC := [C1,...,Cp, . . ., C2p-1]. We prove that there are two functions g, f: Nrightarrow N, such that if L has size at most k, P has size at least f(k), and | scrC | geq g(k), then there is a linkage with the same pattern as L that is "internally combed" by P, in the sense that L cap Cp subseteq P\cap Cp. This result applies to any graph that is partially embedded on a disk (wherescrC is also embedded). In fact, we prove this result in the most general version where the linkage L is s-scattered: every two vertices of distinct paths are within a distance bigger than s. We deduce several variants of this result in the cases where s = 0 and s > 0. These variants permit the application of the Unique Linkage Theorem on several path routing problems on embedded graphs. [ABSTRACT FROM AUTHOR]

In the Categorical Clustering problem, we are given a set of vectors (matrix) A = { a 1 , ... , a n } 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 2 O (B log ⁡ B) | Σ | B ⋅ (m n) O (1). [ABSTRACT FROM AUTHOR]

A natural way of increasing our understanding of NP -complete graph problems is to restrict the input to a special graph class. Classes of H -free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ideal testbed for such a complexity study. However, if the forbidden graph H contains a cycle or claw, then these problems often stay NP -complete. A recent complexity study (MFCS 2019) on the k -Colouring problem shows that we may still obtain tractable results if we also bound the diameter of the H -free input graph. We continue this line of research by initiating a complexity study on the impact of bounding the diameter for a variety of classical vertex partitioning problems restricted to H -free graphs. We prove that bounding the diameter does not help for Independent Set , but leads to new tractable cases for problems closely related to 3 -Colouring. That is, we show that Near-Bipartiteness , Independent Feedback Vertex Set , Independent Odd Cycle Transversal , Acyclic 3 -Colouring and Star 3 -Colouring are all polynomial-time solvable for chair-free graphs of bounded diameter. To obtain these results we exploit a new structural property of 3-colourable chair-free graphs. [ABSTRACT FROM AUTHOR]

Given a graph class H , the task of the H -Square Root problem is to decide whether an input graph G has a square root H from H . We are interested in the parameterized complexity of the problem for classes H that are composed by the graphs at vertex deletion distance at most k from graphs of maximum degree at most one, that is, we are looking for a square root H such that there is a modulator S of size k such that H − S is the disjoint union of isolated vertices and disjoint edges. We show that different variants of the problems with constraints on the number of isolated vertices and edges in H − S are FPT when parameterized by k by demonstrating algorithms with running time 2 2 O (k) ⋅ n 5 . We further show that the running time of our algorithms is asymptotically optimal and it is unlikely that the double-exponential dependence on k could be avoided. In particular, we prove that the VC-kRoot problem, that asks whether an input graph has a square root with vertex cover of size at most k, cannot be solved in time 2 2 o (k) ⋅ n O (1) unless the Exponential Time Hypothesis fails. Moreover, we point out that VC-kRoot parameterized by k does not admit a subexponential kernel unless P = NP. [ABSTRACT FROM AUTHOR]

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 (i) Directed Multiplicative Spanner admits a polynomial kernel of size O (k 4 t 5) and can be solved in randomized (4 t) k · n O (1) time, (ii) the weighted variant of Directed Multiplicative Spanner can be solved in k 2 k · n O (1) time on directed acyclic graphs, (iii) Directed Additive Spanner is W [ 1 ] -hard when parameterized by k for every fixed 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 FPT when parameterized by t and k. [ABSTRACT FROM AUTHOR]

A subset T ⊆ V (G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T , and for a positive integer k , a graph G is k - cyclable if every set of vertices of size at most k is cyclable. The Terminal Cyclability problem asks, given a graph G and a set T of vertices, whether T is cyclable, and the k - Cyclability problem asks, given a graph G and a positive integer k , whether G is k -cyclable. These problems are generalizations of the classical Hamiltonian Cycle problem. We initiate the study of these problems for graph classes that admit polynomial algorithms for Hamiltonian Cycle. We show that Terminal Cyclability can be solved in linear time for interval graphs, bipartite permutation graphs and cographs. Moreover, we construct certifying algorithms that either produce a solution, that is a cycle, or output a graph separator that certifies a no-answer. We use these results to show that k - Cyclability can be solved in polynomial time when restricted to the aforementioned graph classes. [ABSTRACT FROM AUTHOR]

Paths P 1 , ... , P k are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (s i , t i) contains k mutually induced paths P i such that each P i connects s i and t i. This problem is NP-complete even for k = 2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. Consequently, the problem of deciding if an AT-free graph contains a fixed graph H as an induced topological minor admits a polynomial-time algorithm. We show that such an algorithm is essentially optimal by proving that the problem is W [ 1 ] -hard with parameter | V H | , even for a subclass of AT-free graphs, namely cobipartite graphs. We also show that the problems k -in-a-Path and k -in-a-Tree are polynomial-time solvable on AT-free graphs even if k is part of the input. [ABSTRACT FROM AUTHOR]

An enumeration kernel as defined by Creignou et al. (2017) [11] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions. [ABSTRACT FROM AUTHOR]

Among the twenty-five papers presented at IPEC, we invited the authors of the papers with the best scores of Program Committee to submit the full extended versions to this volume. We are pleased to present this special issue of Algorithmica dedicated to the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) which took place September 8-10, 2021. This special issue is a successor of the following special issue volumes of Algorithmica: Volumes 64(1)-2012 and 65(4)-2013 dedicated to IPEC 2010, held in Chennai (India); Volume 71(3)-2015 dedicated to IPEC 2013, held in Sophia Antipolis (France); Volume 75(2)-2016 dedicated to IPEC 2014, held in Wroclaw (Poland); Volume 79(1)-2017 dedicated to IPEC 2015, held in Patras (Greece); Volume 81(2)-2019 dedicated to IPEC 2016, held in Aarhus (Denmark); Volume 81(10)-2019 dedicated to IPEC 2017, held in Vienna (Austria); Volume 82(8)-2020 dedicated to IPEC 2018, held in Helsinki (Finland); Volume 83(8)-2021 dedicated to IPEC 2019, held in Munich (Germany); and Volume 84(8)-2022 dedicated to IPEC 2020, held online. [Extracted from the article]

We study algorithmic properties of the graph class 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 C H O R D A L - k e . More precisely, we identify a large class of optimization problems on C H O R D A L - k e solvable in time 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 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 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 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 C H O R D A L - k e graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of C H O R D A L - k e , namely, I N T E R V A L - k e and S P L I T - k e graphs. [ABSTRACT FROM AUTHOR]

In k -Clustering we are given a multiset of n vectors X ⊂ 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 ∑ i = 1 k min c i ∈ R d ⁡ ∑ x ∈ C i ‖ x − c i ‖ p p ≤ D , where ‖ ⋅ ‖ p is the L p -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 2 O (D log ⁡ D) (n d) O (1). [ABSTRACT FROM AUTHOR]

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 NP-complete for cycles, and we investigate its parameterized complexity. We show that the problem admits a kernel of size O(k) and thus is fixed-parameter tractable when parameterized by k. [ABSTRACT FROM AUTHOR]

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\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n+k$$\end{document} disks. Thus the problem of packing equal disks is the special case of our problem with n=h=0\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n=h=0$$\end{document}. 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\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$h=0$$\end{document}. Our main algorithmic contribution is an algorithm that solves the repacking problem in time (h+k)O(h+k)·|I|O(1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(h+k)^{\mathcal {O}(h+k)}\cdot |I|^{\mathcal {O}(1)}$$\end{document}, where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h. [ABSTRACT FROM AUTHOR]

Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. However, for many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the Secluded Π- Subgraph problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Π, even when parameterized by k + t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Π. In particular, we show that the Connected Secluded Π -Subgraph problem is FPT when parameterized by just t for many important graph properties Π. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

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 2O(k) .| V (G)| 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 2O(k) .nO(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 ε > 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 + ε )d. [ABSTRACT FROM AUTHOR]

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 G , is there a subgraph complement of G which is in G ? We show that this problem can be solved in polynomial time for various choices of the graphs class G , such as bipartite, d-degenerate, or cographs. We complement these results by proving that the problem is NP -complete when G is the class of regular graphs. [ABSTRACT FROM AUTHOR]

Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the StrongF-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In StrongF-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence, the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to forbid that strong copy of F in G. We study StrongF-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when F = P 3 . In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization k - μ (G) , where μ (G) is the maximum matching size of G. We conclude with some results on the parameterization of StrongF-closure by the number of edges of G that are not selected as strong. [ABSTRACT FROM AUTHOR]

Enumerating objects of specified type is one of the principal tasks in algorithms. In graph algorithms an often studied task is the enumeration of vertex subsets of the input graph satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input chordal graph. We establish an enumeration algorithm running in time O (1. 473 6 n) improving upon a previous O (1. 715 9 n) algorithm (Golovach et al., 2016). This is used to show that every n -vertex chordal graph has at most 1. 473 6 n minimal connected dominating sets. [ABSTRACT FROM AUTHOR]

We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formula φ, we consider the problem of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the resulting modification has the property expressible by φ. We provide sufficient and necessary conditions on the structure of the prefix of φ specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by k) and when it admits a polynomial kernel. [ABSTRACT FROM AUTHOR]

We study the enumeration of the minimal dominating sets and upper bounds for the number of such sets in chordal graphs. We show that the maximum number of minimal dominating sets of an n -vertex chordal graph is at most 1.5048 n and prove that these sets can be enumerated in time O (1.5048 n). In this way we improve the previous upper bound of 1.5214 n , recently established by Abu-Khzam and Heggernes, and narrow the gap between the upper bound and the known lower bound of 1.4422 n. [ABSTRACT FROM AUTHOR]

In this paper we provide exponential-time algorithms to enumerate the maximal irredundant sets of chordal graphs and two of their subclasses. We show that the maximum number of maximal irredundant sets of an n -vertex chordal graph is at most 1. 754 9 n , and these can be enumerated in time O (1. 754 9 n). For interval graphs, we achieve the better upper bound of 1. 695 7 n for the number of maximal irredundant sets and we show that they can be enumerated in time O (1. 695 7 n). Finally, we show that an n -vertex forest has at most 1. 618 1 n maximal irredundant sets that can be enumerated in time O (1. 618 1 n). We complement the latter result by providing a family of forests having at least 1. 529 2 n maximal irredundant sets. [ABSTRACT FROM AUTHOR]

Deciding if a graph has a square root is a classical problem, which has been studied extensively both from graph-theoretic and algorithmic perspective. As the problem is NP-complete, substantial effort has been dedicated to determining the complexity of deciding if a graph has a square root belonging to some specific graph class H . There are both polynomial-time solvable and NP-complete results in this direction, depending on H . We present a general framework for the problem if H is a class of sparse graphs. This enables us to generalize a number of known results and to give polynomial-time algorithms for the cases where H is the class of outerplanar graphs and H is the class of graphs of pathwidth at most 2. [ABSTRACT FROM AUTHOR]

In the EDGE EDITING TO CONNECTED f-Degree Graph problem we are given a graph G, an integer fc, 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)Δ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 time2O(k)nO(1). We complement this result by showing that the weighted version of the problem with costs 1 and 0 is W[l]-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 l-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. [ABSTRACT FROM AUTHOR]

Abstract Domination is one of the classical subjects in structural graph theory and in graph algorithms. The Minimum Dominating Set problem and many of its variants are NP-complete and have been studied from various algorithmic perspectives. One of those variants called irredundance is highly related to domination. For example, every minimal dominating set of a graph G is also a maximal irredundant set of G. In this paper we study the enumeration of the maximal irredundant sets of a claw-free graph. We show that an n -vertex claw-free graph has O (1.9341 n) maximal irredundant sets and these sets can be enumerated in the same time. We complement the aforementioned upper bound with a lower bound by providing a family of graphs having 1.5848 n maximal irredundant sets. [ABSTRACT FROM AUTHOR]

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f (u) and f (v) of H whenever there is an edge between vertices u and v of G. The H-Colouring problem is to decide if a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the SurjectiveH-Colouring problem, which imposes the homomorphism to be vertex-surjective. We build upon previous results and show that this problem is NP -complete for every connected graph H that has exactly two vertices with a self-loop as long as these two vertices are not adjacent. As a result, we can classify the computational complexity of SurjectiveH-Colouring for every graph H on at most four vertices. [ABSTRACT FROM AUTHOR]

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 2Oh(k). | | M| |Oh(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. [ABSTRACT FROM AUTHOR]

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 P 5 -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 τ. [ABSTRACT FROM AUTHOR]

A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The SQUARE ROOT problem is that of deciding whether a given graph admits a square root. The problem of testing whether a graph admits a square root which belongs to some specified graph class ℋ is called the ℋ-SQUARE ROOT problem. By showing boundedness of treewidth we prove that SQUARE ROOT is polynomial-time solvable on some classes of graphs with small clique number and that ℋ-SQUARE ROOT is polynomial-time solvable when ℋ is the class of cactuses. [ABSTRACT FROM AUTHOR]

Connected Vertex Cover is one of the classical problems of computer science, already mentioned in the monograph of Garey and Johnson (1979). Although the optimization and decision variants of finding connected vertex covers of minimum size or weight are well-studied, surprisingly there is no work on the enumeration or maximum number of minimal connected vertex covers of a graph. In this paper we show that the number of minimal connected vertex covers of a graph is at most 1 . 866 8 n , and these sets can be enumerated in time O ( 1 . 866 8 n ) . For graphs of chordality at most 5, we are able to give a better upper bound, and for chordal graphs and distance-hereditary graphs we are able to give tight bounds on the maximum number of minimal connected vertex covers. [ABSTRACT FROM AUTHOR]

The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this paper we study output-polynomial enumeration algorithms on graphs of bounded LMIM-width and graphs of bounded local LMIM-width. In particular, we show that all 1-minimal and all 1-maximal (σ,ρ)-dominating sets, and hence all minimal dominating sets, of graphs of bounded LMIM-width can be enumerated with polynomial (linear) delay using polynomial space. Furthermore, we show that all minimal dominating sets of a unit square graph can be enumerated in incremental polynomial time. [ABSTRACT FROM AUTHOR]

The Secluded Path problem models a situation where 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 cost, which is the total cost of vertices in its closed neighborhood. The task is to select a secluded path, i.e., a path with a small exposure cost. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure cost of the tree is minimized. In this paper we present a systematic study of the parameterized complexity of Secluded Steiner Tree. In particular, we establish the tractability of Secluded Path being parameterized by 'above guarantee' value, which in this case is the length of a shortest path between vertices. We also show how to extend this result for Secluded Steiner Tree, in this case we parameterize above the size of an optimal Steiner tree and the number of terminals. We also consider various parameterization of the problems such as by the treewidth, the size of a vertex cover, feedback vertex set, or the maximum vertex degree and establish kernelization complexity of the problem subject to different choices of parameters. [ABSTRACT FROM AUTHOR]

We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks, given a graph G , non-negative integers d , k and a function δ : V ( G ) → { 1 , … , d } , whether it is possible to obtain a connected graph G ′ from G such that the degree of v is δ ( v ) for every vertex v by at most k edge editing operations. As the problem is NP-complete even if δ ( v ) = 2 , we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d + k . For the special case δ ( v ) = d , i.e., when the aim is to obtain a connected d -regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. [ABSTRACT FROM AUTHOR]

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are at distance 2 from each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the “distance from triviality” framework. For an integer k , a planar + k v graph (or k -apex graph) is a graph that can be made planar by the removal of at most k vertices. We prove that a generalization of Square Root , in which some edges are prescribed to be either in or out of any solution, has a kernel of size O ( k ) for planar + k v graphs, when parameterized by k . Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem. [ABSTRACT FROM AUTHOR]

We consider the following graph modification problem. Let the input consist of a graph G = ( V , E ) , a weight function w : V ∪ E → N , a cost function c : V ∪ E → N 0 and a degree function δ : V → N 0 , together with three integers k v , k e and C . The question is whether we can delete a set of vertices of total weight at most k v and a set of edges of total weight at most k e so that the total cost of the deleted elements is at most C and every non-deleted vertex v has degree δ ( v ) in the resulting graph G ′ . We also consider the variant in which G ′ must be connected. Both problems are known to be NP -complete and W [ 1 ] -hard when parameterized by k v + k e . We prove that, when restricted to planar graphs, they stay NP -complete but have polynomial kernels when parameterized by k v + k e . [ABSTRACT FROM AUTHOR]

For a positive integer k, a k- coloring of a graph [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of the graph editing problem called Editing to a Graph with a Given Degree Sequence where the aim is to obtain a graph with a given degree sequence σ by at most k vertex deletions, edge deletions and edge additions. We show that the problem is W [ 1 ] -hard when parameterized by k for any combination of the allowed editing operations. From the positive side, we show that the problem can be solved in time 2 O ( k ( Δ ⁎ + k ) 2 ) n 2 log ⁡ n for n -vertex graphs, where Δ ⁎ = max ⁡ σ , i.e., the problem is FPT when parameterized by k + Δ ⁎ . We also show that Editing to a Graph with a Given Degree Sequence has a polynomial kernel when parameterized by k + Δ ⁎ if only edge additions are allowed, and there is no polynomial kernel unless NP ⊆ co - NP / poly for all other combinations of the allowed editing operations. [ABSTRACT FROM AUTHOR]

A graph G = ( V , E ) is a threshold tolerance graph if each vertex v ∈ V can be assigned a weight w v and a tolerance t v such that two vertices x , y ∈ V are adjacent if w x + w y ≥ min ( t x , t y ) . Currently, the most efficient recognition algorithm for threshold tolerance graphs is the algorithm of Monma, Reed, and Trotter which has an O ( n 4 ) runtime. We give an O ( n 2 ) algorithm for recognizing threshold tolerance and their complements, the co-threshold tolerance (co-TT) graphs, resolving an open question of Golumbic, Weingarten, and Limouzy. [ABSTRACT FROM AUTHOR]

We show that interval graphs on n vertices have at most 3 n / 3 ≈ 1.442 2 n minimal dominating sets, and that these can be enumerated in time O ∗ ( 3 n / 3 ) . As there are examples of interval graphs that actually have 3 n / 3 minimal dominating sets, our bound is tight. We show that the same upper bound holds also for trees, i.e. trees on n vertices have at most 3 n / 3 ≈ 1.442 2 n minimal dominating sets. The previous best upper bound on the number of minimal dominating sets in trees was 1.465 6 n , and there are trees that have 1.416 7 n minimal dominating sets. Hence our result narrows this gap. On general graphs there is a larger gap, with 1.715 9 n being the best known upper bound, whereas no graph with 1.570 5 n or more minimal dominating sets is known. [ABSTRACT FROM AUTHOR]

For a fixed graph H , the H - Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H - Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP -complete cases depending on the choice of H . Moreover, when G is AT-free, chordal or planar, we show that H - Minor Edit is polynomial-time solvable for all graphs H . [ABSTRACT FROM AUTHOR]

The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a nonnegative integer k, decide whether the cyclability of G is at least k, is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by k, is co-W[1]-hard and that it does not admit a polynomial kernel on planar graphs, unless NP ⊆ co-NP=poly. On the positive side, we give an FPT algorithm for planar graphs that runs in time 22O(k2 log k). n2. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs. [ABSTRACT FROM AUTHOR]

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

Enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input graph from various graph classes of bounded chordality. We establish enumeration algorithms as well as lower and upper bounds for the maximum number of minimal connected dominating sets in such graphs. In particular, we present algorithms to enumerate all minimal connected dominating sets of chordal graphs in time O ( 1.7159 n ) , of split graphs in time O ( 1.3803 n ) , and of AT-free, strongly chordal, and distance-hereditary graphs in time O ⁎ ( 3 n / 3 ) , where n is the number of vertices of the input graph. Our algorithms imply corresponding upper bounds for the number of minimal connected dominating sets for these graph classes. [ABSTRACT FROM AUTHOR]

The Eulerian Editing problem asks, given a graph G and an integer k , whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations. [ABSTRACT FROM AUTHOR]

We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is equivalent to enumeration of minimal transversals in hypergraphs. Whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a well-studied and challenging question that has been open for several decades. With this result we contribute to the known cases having an affirmative reply to this important question. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]