Search

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

We investigate preprocessing for vertex-subset problems on graphs. While the notion of kernelization, originating in parameterized complexity theory, is a formalization of provably effective preprocessing aimed at reducing the total instance size, our focus is on finding a nonempty vertex set that belongs to an optimal solution. This decreases the size of the remaining part of the solution which still has to be found, and therefore shrinks the search space of fixed-parameter tractable algorithms for parameterizations based on the solution size. We introduce the notion of a c-essential vertex as one that is contained in all c-approximate solutions. For several classic combinatorial problems such as Odd Cycle Transversal and Directed Feedback Vertex Set, we show that under mild conditions a polynomial-time preprocessing algorithm can find a subset of an optimal solution that contains all 2-essential vertices, by exploiting packing/covering duality. This leads to FPT algorithms to solve these problems where the exponential term in the running time depends only on the number of nonessential vertices in the solution. [ABSTRACT FROM AUTHOR]

This paper deals with the complexity of some natural graph problems parameterized by some measures that are restrictions of clique-width, such as modular-width and neighborhood diversity. We introduce a novel parameter, called iterated type partition number, that can be computed in linear time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W [ 1 ] -hard when parameterized by the iterated type partition number. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parameterized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithms parameterized by iterated type partition number, which enables us to find optimal solutions for several graph problems. As an example, in this paper, we present algorithms parameterized by the iterated type partition number of the input graph for some generalized versions of the Maximum Clique , Minimum Graph Coloring , (Total) Minimum Dominating Set , Minimum Vertex Cover and Maximum Independent Set problems. Each algorithm outputs not only the optimal value but also the optimal solution. We stress that while the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. We finally show that the proposed scheme can be used to devise polynomial kernels, with respect to iterated type partition number, for the decisional version of most of the problems mentioned above. [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 present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph G with distinguished vertices s,t ∈ V(G) and an integer k, one can in randomized k(1) ⋅ (|V(G)| + |E(G)|) time sample a set A ⊆ \(\binom{V(G)}{2}\) such that the following holds: for every inclusion-wise minimal st-cut Z in G of cardinality at most k, Z becomes a minimum-cardinality cut between s and t in G+A (i.e., in the multigraph G with all edges of A added) with probability 2-(k log k). Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability (2-(k log k) instead of 2-(k4 log k)), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective st-Cut problem can be solved in randomized FPT time 2(k log k)(|V(G)|+|E(G)|) on undirected graphs. [ABSTRACT FROM AUTHOR]

We study three problems introduced by Bang-Jensen and Yeo (2015) and by Bang-Jensen et al. (2016) about finding disjoint "balanced" spanning rooted substructures in graphs and digraphs, which generalize classic packing problems such as detecting the existence of multiple arc-disjoint spanning arborescences. Namely, given a positive integer k , a digraph D = (V , A) , and a root r ∈ V , we first consider the problem of finding two arc-disjoint k -safe spanning r -arborescences, meaning arborescences rooted at a vertex r such that deleting any arc r v and every vertex in the sub-arborescence rooted at v leaves at least k vertices. Then, we consider the problem of finding two arc-disjoint (r , k) -flow branchings meaning arc sets admitting a flow that distributes one unit from r to every other vertex while respecting a capacity limit of n − k on every arc. We show that both these problems are FPT with parameter k , improving on existing XP algorithms. The latter of these results answers a question of Bang-Jensen et al. (2016). Further, given a positive integer k , a graph G = (V , E) , and r ∈ V , we consider the problem of finding two edge-disjoint (r , k) -safe spanning trees meaning spanning trees such that the component containing r has size at least k when deleting any vertex different from r. We show that this problem is also FPT with parameter k , again improving on a previous XP algorithm. Our main technical contribution is to prove that the existence of such spanning substructures is equivalent to the existence of substructures with size and maximum (out-)degree both bounded by a (linear or quadratic) function of k , which may be of independent interest. [ABSTRACT FROM AUTHOR]

The Kneser graph K(n, k) is defined for integers n and k with n \geq 2k as the graph whose vertices are all the k-subsets of [n] = { 1, 2, ..., n} where two such sets are adjacent if they are disjoint. The Schrijver graph S(n, k) is defined as the subgraph of K(n, k) induced by the collection of all k-subsets of [n] that do not include two consecutive elements modulo n. It is known that the chromatic number of both K(n, k) and S(n, k) is n - 2k + 2. In the computational Kneser and Schrijver problems, we are given access to a coloring with n - 2k + 1 colors of the vertices of K(n, k) and S(n, k), respectively, and the goal is to find a monochromatic edge. We prove that the problems admit randomized algorithms with running time nO(1) µ kO(k), hence they are fixed-parameter tractable with respect to the parameter k. The analysis involves structural results on intersecting families and on induced subgraphs of Kneser and Schrijver graphs. We also study the AGREEABLE-SET problem of assigning a small subset of a set of m items to a group of l agents, so that all agents value the subset at least as much as its complement. As an application of our algorithm for the KNESER problem, we obtain a randomized polynomial-time algorithm for the AGREEABLE-SET problem for instances with l ≤ m - ) (log m/log log m). We further show that the Agreeable-Set problem is at least as hard as a variant of the KNESER problem with extended access to the input coloring. [ABSTRACT FROM AUTHOR]

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

We present an isomorphism test for graphs of Euler genus g running in time 2O (g4 log) nO(1). Our algorithm provides the first explicit upper bound on the dependence on g for an fpt isomorphism test parameterized by the Euler genus of the input graphs. The only previous fpt algorithm runs in time f(g)n for some function f (Kawarabayashi 2015). Actually, our algorithm even works when the input graphs only exclude K3,h as a minor. For such graphs, no fpt isomorphism test was known before. The algorithm builds on an elegant combination of simple group-theoretic, combinatorial, and graph-theoretic approaches. In particular, our algorithm relies on the notion of (t, k)-WL-bounded graphs which provide a powerful tool to combine group-theoretic techniques with the standard Weisfeiler--Leman algorithm. This concept may be of independent interest. [ABSTRACT FROM AUTHOR]

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

Given a graph G =(V,E) and an integer k, the Cluster Editing problem asks whether we can transform G into a union of vertex-disjoint cliques by at most k modifications (edge deletions or insertions). In this paper, we study the following variant of Cluster Editing. We are given a graph G = (V,E), a packing ℋ of modification-disjoint induced P3s (no pair of P3s in ℋ share an edge or non-edge) and an integer ℓ. The task is to decide whether G can be transformed into a union of vertex-disjoint cliques by at most ℓ +|ℋ| modifications (edge deletions or insertions). We show that this problem is NP-hard even when ℓ = 0 (in which case the problem asks to turn G into a disjoint union of cliques by performing exactly one edge deletion or insertion per element of ℋ) and when each vertex is in at most 23 P3s of the packing. This answers negatively a question of van Bevern, Froese, and Komusiewicz (CSR 2016, ToCS 2018), repeated by C. Komusiewicz at Shonan meeting no. 144 in March 2019. We then initiate the study to find the largest integer c such that the problem remains tractable when restricting to packings such that each vertex is in at most c packed P3s. Here packed P3s are those belonging to the packing ℋ. Van Bevern et al. showed that the case c = 1 is fixed-parameter tractable with respect to ℓ and we show that the case c = 2 is solvable in |V|2ℓ + O(1) time. [ABSTRACT FROM AUTHOR]

We provide new parameterized complexity results for Interval Scheduling on Eligible Machines. In this problem, a set of n jobs is given to be processed non-preemptively on a set of m machines. Each job has a processing time , a deadline , a weight , and a set of eligible machines that can process it. The goal is to find a maximum weight subset of jobs that can each be processed on one of its eligible machines such that it completes exactly at its deadline. We focus on two parameters: The number m of machines, and the largest processing time p max. Our main contribution is showing W[1] -hardness when parameterized by m. This answers Open Problem 8 of Mnich and van Bevern's list of 15 open problems in parameterized complexity of scheduling problems [Computers & Operations Research, 2018]. Furthermore, we show NP -hardness even when p max = O (1) and present an FPT -algorithm with for the combined parameter m + p max. [ABSTRACT FROM AUTHOR]

We consider the product of determinantal point processes (DPPs), a point process whose probability mass is proportional to the product of principal minors of multiple matrices, as a natural, promising generalization of DPPs. We study the computational complexity of computing its normalizing constant , which is among the most essential probabilistic inference tasks. Our complexity-theoretic results (almost) rule out the existence of efficient algorithms for this task unless the input matrices are forced to have favorable structures. In particular, we prove the following: • Computing ∑ S det ⁡ (A S , S) p exactly for every (fixed) positive even integer p is UP -hard and Mod 3 P -hard, which gives a negative answer to an open question posed by Kulesza and Taskar [51]. • ∑ S det ⁡ (A S , S) det ⁡ (B S , S) det ⁡ (C S , S) is NP -hard to approximate within a factor of 2 O (| I | 1 − ε) or 2 O (n 1 / ε) for any ε > 0 , where | I | is the input size and n is the order of the input matrix. This result is stronger than the # P -hardness for the case of two matrices derived by Gillenwater [36]. • There exists a k O (k) n O (1) -time algorithm for computing ∑ S det ⁡ (A S , S) det ⁡ (B S , S) , where k is the maximum rank of A and B or the treewidth of the graph formed by nonzero entries of A and B. Such parameterized algorithms are said to be fixed-parameter tractable. These results can be extended to the fixed-size case. Further, we present two applications of fixed-parameter tractable algorithms given a matrix A of treewidth w : • We can compute a 2 n 2 p − 1 -approximation to ∑ S det ⁡ (A S , S) p for any fractional number p > 1 in w O (w p) n O (1) time. • We can find a 2 n -approximation to unconstrained maximum a posteriori inference in w O (w n) n O (1) time. [ABSTRACT FROM AUTHOR]

This paper studies the relationship between undirected (unrooted) and directed (rooted) phylogenetic networks. We describe a polynomial-time algorithm for deciding whether an undirected nonbinary phylogenetic network, given the locations of the root and reticulation vertices, can be oriented as a directed nonbinary phylogenetic network. Moreover, we characterize when this is possible and show that, in such instances, the resulting directed nonbinary phylogenetic network is unique. In addition, without being given the location of the root and the reticulation vertices, we describe an algorithm for deciding whether an undirected binary phylogenetic network N can be oriented as a directed binary phylogenetic network of a certain class. The algorithm is fixed-parameter tractable (FPT) when the parameter is the level of N and is applicable to classes of directed phylogenetic networks that satisfy certain conditions. As an example, we show that the well-studied class of binary tree-child networks satisfies these conditions. [ABSTRACT FROM AUTHOR]