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

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G , a temporal graph is represented by assigning a set of integer time-labels to every edge e of G , indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching , taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching , we are looking for the largest possible number of time-labeled edges (simply time-edges) (e , t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ N is given. We prove strong computational hardness results for Maximum Temporal Matching , even for elementary cases, as well as fixed-parameter algorithms with respect to natural parameters and polynomial-time approximation algorithms. [ABSTRACT FROM AUTHOR]

A target set selection model is a graph G with a threshold function τ : V (G) → N upper-bounded by the vertex degree. For a given model, a set S 0 ⊆ V (G) is a target set if V (G) can be partitioned into non-empty subsets S 0 , S 1 , ... , S t such that, for all i ∈ { 1 , ... , t } , S i contains exactly every vertex v outside S 0 ∪ ⋯ ∪ S i − 1 having at least τ (v) neighbors in S 0 ∪ ⋯ ∪ S i − 1 . We say that t is the activation time t τ (S 0) of the target set S 0. The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time , in which the goal is to find a target set S 0 that maximizes t τ (S 0). That is, given a graph G , a threshold function τ in G , and an integer k , the objective of the TSS-time problem is to decide whether G contains a target set S 0 such that t τ (S 0) ≥ k. Let τ ⋆ = max v ∈ V (G) τ (v). Our main result is the following dichotomy about the complexity of TSS-time when G belongs to a minor-closed graph class C : if C has bounded local treewidth, the problem is FPT parameterized by k and τ ⋆ ; otherwise, it is NP -complete even for fixed k = 4 and τ ⋆ = 2. We also prove that, with τ ∗ = 2 , the problem is NP -hard in bipartite graphs for fixed k = 5 , and from previous results we observe that TSS-time is NP -hard in planar graphs and W [1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set S 0 in a given tree maximizing t τ (S 0). [ABSTRACT FROM AUTHOR]

We consider the problem of assigning agents to resources under the two-sided preference list setting where resources specify an upper-quota and a lower-quota, that is, respectively the maximum and minimum number of agents that can be assigned to it. Different notions of optimality including envy-freeness and relaxed stability are investigated for this setting. Krishnaa et al. (2020) show that in this setting, the problem of computing a maximum size envy-free matching (MAXEFM) or a maximum size relaxed stable matching (MAXRSM) that satisfies lower quotas is not approximable within a certain constant factor unless P = NP. In this work, we investigate the parameterized complexity of MAXEFM and MAXRSM. We show that MAXEFM is W [ 1 ] -hard and MAXRSM is para- NP -hard when parameterized on several natural parameters derived from the instance. We present kernelization results and FPT algorithms for both problems parameterized on other relevant parameters. [ABSTRACT FROM AUTHOR]

The s-Club problem asks whether a given undirected graph G contains a vertex set S of size at least k such that G[S], the subgraph of G induced by S, has diameter at most s. We consider variants of s-Club where one additionally demands that each vertex of G[S] is contained in at least ℓ triangles in G[S], that each edge of G[S] is contained in at least ℓ triangles in G[S], or that S contains a given set W of seed vertices. We show that in general these variants are W[1]-hard when parameterized by the solution size k, making them significantly harder than the unconstrained s-Club problem. On the positive side, we obtain some FPT algorithms for the case when ℓ = 1 and for the case when G[W], the graph induced by the set of seed vertices, is a clique. [ABSTRACT FROM AUTHOR]

The problem of deletion of vertices to a hereditary graph class is a well-studied problem in parameterized complexity. Recently, a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes and we determine whether k vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be fixed parameter tractable (FPT) when the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. This paper focuses on pairs of specific graph classes (Π 1 , Π 2) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. [ABSTRACT FROM AUTHOR]

We study the NP-hard Temporal (s , z) -Separation problem on temporal graphs, which are graphs with fixed vertex sets but edge sets that change over discrete time steps. We tackle Temporal (s , z) -Separation by restricting the layers (i.e., graphs characterized by edges that are present at a certain point in time) to specific graph classes. We restrict the layers of the temporal graphs to be either all split graphs or all permutation graphs (both being perfect graph classes) and provide both intractability and tractability results. In particular, we show that in general Temporal (s , z) -Separation remains NP-hard both on temporal split and temporal permutation graphs, but we also spot promising islands of fixed-parameter tractability particularly based on parameterizations that measure the amount of "change over time". [ABSTRACT FROM AUTHOR]

We study the fixed-parameter tractability of the problem of deciding whether a given temporal graph admits a temporal walk that visits all vertices (temporal exploration) or, in some variants, a certain subset of the vertices. In the strict variant, edges must be traversed in strictly increasing timesteps; in the non-strict variant, any number of edges can be traversed in each timestep. For both variants, we give FPT algorithms for finding a temporal walk that visits a given set X of vertices, parameterised by | X | , and for finding a temporal walk that visits at least k distinct vertices, parameterised by k. We also show W [ 2 ] -hardness for a set version of temporal exploration. For the non-strict variant, we give an FPT algorithm for temporal exploration parameterised by the lifetime, and show that temporal exploration can be solved in polynomial time if the graph in each timestep has at most two connected components. [ABSTRACT FROM AUTHOR]

Motivated by an application in cancer genomics, Hajirasouliha and Raphael [Proceedings of the 14th International Workshop on Algorithms in Bioinformatics, 2014, pp. 354-367] proposed the split-row problem (SR). In this problem, an m\times n binary matrix M is given. A split-row operation on M is defined as replacing a row r by k > 1 rows r(1), r(2), . . ., r(k) whose bitwise OR is equal to r. The cost of the operation is the number of additional rows induced, that is, k 1. The goal is to find a sequence of split-row operations that transforms M into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Recently, Hujdurovi\'c et al. [ACM Trans. Algorithms, 14 (2018), 26] proved the APX-hardness of SR and presented efficient exact and approximation algorithms. The parameterized study of SR was left as a direction for future work. Let\varepsilon (M) denote the minimum total cost. This paper gives an O*(2min(n,2x(M))-time exact algorithm for SR. This result indicates that SR is fixed-parameter tractable when parameterized by E (M). In addition, in the worst case, our algorithm requires O* (2n) time, significantly improving the previous upper bound of O\ast (nn). Hujdurovi\'c et al.'s exact algorithm can be modified to solve a variant of SR, called the distinct split-row problem (DSR). Our algorithm can be adapted to this variant as well. In addition, our algorithms can be extended to solve SR and DSR with the following additional constraint: only the rows in a given subset are allowed to be split. [ABSTRACT FROM AUTHOR]

A graph G is weakly γ -closed if every induced subgraph of G contains one vertex v such that for each non-neighbor u of v it holds that | N (u) ∩ N (v) | < γ . The weak closure γ (G) of a graph, recently introduced by Fox et al. (SIAM J Comput 49(2):448–464, 2020), is the smallest number such that G is weakly γ -closed. This graph parameter is never larger than the degeneracy (plus one) and can be significantly smaller. Extending the work of Fox et al. (2020) on clique enumeration, we show that several problems related to finding dense subgraphs, such as the enumeration of bicliques and s-plexes, are fixed-parameter tractable with respect to γ (G) . Moreover, we show that the problem of determining whether a weakly γ -closed graph G has a subgraph on at least k vertices that belongs to a graph class G which is closed under taking subgraphs admits a kernel with at most γ k 2 vertices. Finally, we provide fixed-parameter algorithms for Independent Dominating Set and Dominating Clique when parameterized by γ + k where k is the solution size. Furthermore, we show that Independent Dominating Set does not admit a polynomial kernel for constant γ under standard assumptions. [ABSTRACT FROM AUTHOR]

Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called TREE CONTAINMENT, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) TREE CONTAINMENT using the treewidth t of the input network N as parameter, showing that the problem can be solved in 2O(t2)·|N| time and space. [ABSTRACT FROM AUTHOR]

We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number c and weak closure number γ (Fox et al. SIAM J Comput 49(2):448–464, 2020) in addition to the standard parameter solution size k. The weak closure number γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size k O (γ) , k O (γ) , and (γ k) O (γ) , respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size k o (γ) by previous results on their kernelization complexity on degenerate graphs (Cygan et al. ACM Trans Algorithms 13(3):43:1–43:22, 2017). For Capacitated Vertex Cover, we show that even a kernel of size k o (c) is unlikely. In contrast, for Connected Vertex Cover, we obtain a kernel with O (c k 2) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class G admits a kernel of size k O (γ) when G contains all complete and all edgeless graphs. Finally, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number c and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs. [ABSTRACT FROM AUTHOR]

In the target set selection model (TSS), introduced by Chen in 2009, it is given a graph G with a threshold function τ : V (G) → N upper-bounded by the vertex degree. For a given model, a set S 0 ⊆ V (G) is a target set if V (G) can be partitioned into non-empty subsets S 0 , S 1 , ... , S t such that, for i ∈ { 1 , ... , t } , S i contains exactly every vertex v outside S 0 ∪ ⋯ ∪ S i − 1 having at least τ (v) neighbors in S 0 ∪ ⋯ ∪ S i − 1 . We say that t is the activation time t τ (S 0) of the target set S 0. The problem TSS-Size of finding a minimum target set has been widely studied in the literature. In 2013, Cicalese et al. investigated the problem of finding a target set with activation time 1, which we call here TSS-Domination. In 2021, Keiler et al. investigated the problem TSS-Time of finding a target set with maximum activation time. In this paper, we introduce the problem of finding a maximum proper subset of vertices which is not a target set, which we call TSS-Max-Convex. We prove that, even in split graphs and bipartite graphs, TSS-max-convex is Poly-APX-Complete, TSS-Domination is Log-APX-Complete and their parameterized versions are W[1]-hard and W[2]-hard, respectively, when parameterized by the size of the solution and the maximum threshold τ ∗ = max v ∈ V (G) τ (v). Moreover, we prove that both problems are FPT in bounded local-treewidth graphs when parameterized by the size of the solution and the maximum threshold τ ∗. Finally, we prove that TSS-Domination is FPT in d -degenerate graphs when parameterized by the size of the solution and the degeneracy d , extending the main result of Alon and Gutner in 2009. [ABSTRACT FROM AUTHOR]

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. A widely-studied special case are edge-colored graphs, where a compatible walk is forbidden to take two edges of the same color in a row. We initiate the study of fundamental problems on finding paths, cycles and walks in forbidden-transition graphs from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth for finding a compatible Hamiltonian cycle in the edge-colored graph setting. [ABSTRACT FROM AUTHOR]

The q - Coloring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q - Coloring with respect to a hierarchy of structural parameters. We show that unless the Exponential Time Hypothesis fails, there is no constant θ such that q - Coloring parameterized by the size k of a vertex cover can be solved in O ∗ (θ k) time for all fixed q. We prove that there are O ∗ ( (q − ɛ) k) time algorithms where k is the vertex deletion distance to several graph classes for which q - Coloring is known to be solvable in polynomial time, including all graph classes F whose (q + 1) -colorable members have bounded treedepth. In contrast, we prove that if F is the class of paths – some of the simplest graphs of unbounded treedepth – then no such algorithm can exist unless the Strong Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

In this work, we study a range of constrained versions of the k-supplier and k-center problems. In the classical (unconstrained) k -supplier problem, we are given a set of clients C in a metric space X , with distance function d (. ,.). We are also given a set of feasible facility locations L ⊆ X. The goal is to open a set F of k facilities in L to minimize the maximum distance of any client to the closest open facility, i.e., minimize, cost (F , C) ≡ max j ∈ C ⁡ { d (F , j) } , where d (F , j) is the distance of client j to the closest facility in F. The k -center problem is a special case of the k -supplier problem where L = C. We study various constrained versions of the k -supplier problem such as: capacitated , fault-tolerant , ℓ -diversity, etc. These problems fall under a broad framework of constrained clustering. A unified framework for constrained clustering was proposed by Ding and Xu [Algorithmica 2020] in the context of the k -median and k -means objectives. We extend this framework to the k -supplier and k -center objectives in this work. This unified framework allows us to obtain results simultaneously for the following constrained versions of the k -supplier problem: r-gather, r-capacity, balanced, chromatic, fault-tolerant, strongly private, ℓ-diversity, and fair k-supplier problems, with and without outliers. We design Fixed-Parameter Tractable (FPT) algorithms for these problems. FPT algorithms have polynomial running time if the parameter under consideration is a constant. This may be relevant even to a practitioner since the parameter k is a small number in many real clustering scenarios. We obtain the following results: • We give 3 and 2 approximation algorithms for the constrained k -supplier and k -center problems, respectively, with FPT running time k O (k) ⋅ n O (1) , where n = | C ∪ L |. Moreover, these approximation guarantees are tight; that is, for any constant ε > 0 , no algorithm can achieve (3 − ε) and (2 − ε) approximation guarantees for the constrained k -supplier and k -center problems in FPT time, assuming FPT ≠ W [ 2 ]. • We study the constrained clustering problem with outliers. Our algorithm gives 3 and 2 approximation guarantees for the constrained outlier k -supplier and k -center problems, respectively, with FPT running time (k + m) O (k) ⋅ n O (1) , where n = | C ∪ L | and m is the number of outliers. • Our techniques generalise for distance function d (. ,.) z. That is, for any positive real number z , if the cost of a client is defined by d (. ,.) z instead of d (. ,.) , then our algorithm gives 3 z and 2 z approximation guarantees for the constrained k -supplier and k -center problems, respectively. • We design 3 approximation algorithm for a wide range of constrained k -supplier problems with FPT running time f (k). p o l y (n). • We design 2 approximation algorithm for a range of constrained k -center problems with FPT running time f (k). p o l y (n). • We extend the algorithm to outlier setting with FPT running time f (k , m). p o l y (n) , where m = number of outliers. • We show matching lower bounds for the constrained k -supplier and k -center problems in the outlier and non-outlier settings. [ABSTRACT FROM AUTHOR]

For an integer r ≥ 0 the r-th iterated line graph L r (G) of a graph G is defined by: (i) L 0 (G) = G and (ii) L r (G) = L (L (r − 1) (G)) for r > 0 , where L (G) denotes the line graph of G. The Hamiltonian Index h (G) of G is the smallest r such that L r (G) has a Hamiltonian cycle [Chartrand, 1968]. Checking if h (G) = k is NP -hard for any fixed integer k ≥ 0 even for subcubic graphs G [Ryjáček et al., 2011]. We study the parameterized complexity of this problem with the parameter treewidth, t w (G) , and show that we can find h (G) in time1 O ⋆ ((1 + 2 (ω + 3)) t w (G)) where ω is the matrix multiplication exponent. Prior work on computing h (G) includes various O ⋆ (2 O (t w (G))) -time algorithms for checking if h (G) = 0 holds; i.e., whether G has a Hamiltonian Cycle [Cygan et al., FOCS 2011; Bodlaender et al., Inform. Comput., 2015; Fomin et al., JACM 2016]; an O ⋆ (t w (G) O (t w (G))) -time algorithm for checking if h (G) = 1 holds; i.e., whether L (G) has a Hamiltonian Cycle [Lampis et al., Discrete Appl. Math., 2017]; and, most recently, an O ⋆ ((1 + 2 (ω + 3)) t w (G)) -time algorithm for checking if h (G) = 1 holds [Misra et al., CSR 2019]. Our algorithm for computing h (G) generalizes these results. The NP -hard Eulerian Steiner Subgraph problem takes as input a graph G and a specified subset K of terminal vertices of G and asks if G has an Eulerian2 subgraph H containing all the terminals. A key ingredient of our algorithm for finding h (G) is an algorithm which solves Eulerian Steiner Subgraph in O ⋆ ((1 + 2 (ω + 3)) t w (G)) time. To the best of our knowledge this is the first FPT algorithm for Eulerian Steiner Subgraph. Prior work on the special case of finding a spanning Eulerian subgraph (i.e., with K = V (G)) includes a polynomial-time algorithm for series-parallel graphs [Richey et al., 1985] and an O ⋆ (2 O (n)) -time algorithm for planar graphs on n vertices [Sau and Thilikos, 2010]. Our algorithm for Eulerian Steiner Subgraph generalizes both these results. [ABSTRACT FROM AUTHOR]

While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and show that it is aligned with the general concept of clique-width of relational structures by Blumensath and Courcelle (2006). We also relate the new notion to monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given. [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]

In the F -Minor-Free Deletion problem one is given an undirected graph G , an integer k , and the task is to determine whether there exists a vertex set S of size at most k , so that G - S contains no graph from the finite family F as a minor. It is known that whenever F contains at least one planar graph, then F -Minor-Free Deletion admits a polynomial kernel, that is, there is a polynomial-time algorithm that outputs an equivalent instance of size k O (1) [Fomin, Lokshtanov, Misra, Saurabh; FOCS 2012]. However, this result relies on non-constructive arguments based on well-quasi-ordering and does not provide a concrete bound on the kernel size. We study the Outerplanar Deletion problem, in which we want to remove at most k vertices from a graph to make it outerplanar. This is a special case of F -Minor-Free Deletion for the family F = { K 4 , K 2 , 3 } . The class of outerplanar graphs is arguably the simplest class of graphs for which no explicit kernelization size bounds are known. By exploiting the combinatorial properties of outerplanar graphs we present elementary reduction rules decreasing the size of a graph. This yields a constructive kernel with O ( k 4) vertices and edges. As a corollary, we derive that any minor-minimal obstruction to having an outerplanar deletion set of size k has O ( k 4) vertices and edges. [ABSTRACT FROM AUTHOR]

In the NP-hard Colored (s,t)-Cut problem, the input is a graph G = (V,E) together with an edge-coloring ℓ : E → C, two vertices s and t, and a number k. The question is whether there is a set S ⊆ C of at most k colors such that deleting every edge with a color from S destroys all paths between s and t in G. We continue the study of the parameterized complexity of Colored (s,t)-Cut. First, we consider parameters related to the structure of G. For example, we study parameterization by the number ξi of edge deletions that are needed to transform G into a graph with maximum degree i. We show that Colored (s,t)-Cut is W[2]-hard when parameterized by ξ3, but fixed-parameter tractable when parameterized by ξ2. Second, we consider parameters related to the coloring ℓ. We show fixed-parameter tractability for three parameters that are potentially smaller than the total number of colors |C| and provide a linear-size problem kernel for a parameter related to the number of edges with rare edge colors. [ABSTRACT FROM AUTHOR]

A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number c such that G is c-closed. Fox et al. [SIAM J. Comput., 49 (2020), pp. 448-464] defined c-closure and investigated it in the context of clique enumeration. We show that c-closure can be applied in kernelization algorithms for several classic graph problems. We show that Dominating Set admits a kernel of size kO(c), that Induced Matching admits a kernel with O(c7k8) vertices, and that Irredundant Set admits a kernel with O(c5/2k3) vertices. As we show, our kernelizations exploit the fact that c-closed graphs have polynomially bounded Ramsey numbers. [ABSTRACT FROM AUTHOR]

The usual integer programming formulation for the maximum clique problem has several undesirable properties, including a weak LP relaxation, a quadratic number of constraints and nonzeros when applied to sparse graphs, and poor guarantees on the number of branch-and-bound nodes needed to solve it. With this as motivation, we propose new mixed integer programs (MIPs) for the clique problem that have more desirable worst-case properties, especially for sparse graphs. The smallest MIP that we propose has just O (n + m) nonzeros for graphs with n vertices and m edges. Nevertheless, it ensures a root LP bound of at most d + 1 , where d denotes the graph's degeneracy (a measure of density), and is solved in O (2 d n) branch-and-bound nodes. Meanwhile, the strongest MIP that we propose visits fewer nodes, O (1. 62 d n) . Further, when a best-bound node selection strategy is used, O (2 g n) nodes are visited, where g = (d + 1) - ω is the clique-core gap. Often, g is so small that it can be treated as a constant in which case O(n) nodes are visited. Experiments are conducted to understand their performance in practice. [ABSTRACT FROM AUTHOR]

Traditionally, finite automata theory has been used as a framework for the representation of possibly infinite sets of strings. In this work, we introduce the notion of second-order finite automata, a formalism that combines finite automata with ordered decision diagrams, with the aim of representing possibly infinite sets of sets of strings. Our main result states that second-order finite automata can be canonized with respect to the second-order languages they represent. Using this canonization result, we show that sets of sets of strings represented by second-order finite automata are closed under the usual Boolean operations, such as union, intersection, difference and even under a suitable notion of complementation. Additionally, emptiness of intersection and inclusion are decidable. We provide two algorithmic applications for second-order automata. First, we show that several width/size minimization problems for deterministic and nondeterministic ODDs are solvable in fixed-parameter tractable time when parameterized by the width of the input ODD. In particular, our results imply FPT algorithms for corresponding width/size minimization problems for ordered binary decision diagrams (OBDDs) with a fixed variable ordering. Previously, only algorithms that take exponential time in the size of the input OBDD were known for width minimization, even for OBDDs of constant width. Second, we show that for each k and w one can count the number of distinct functions computable by ODDs of width at most w and length k in time h(|Σ|,w) ⋅ kO(1), for a suitable h : ℕ × ℕ → ℕ . This improves exponentially on the time necessary to explicitly enumerate all such functions, which is exponential in both the width parameter w and in the length k of the ODDs. [ABSTRACT FROM AUTHOR]

We study a natural variant of scheduling that we call partial scheduling: in this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type f (k) n O (1) or n O (f (k)) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in P , N P -complete and fixed-parameter tractable by k, or W [ 1 ] -hard parameterized by k. Second, for many interesting cases we further investigate the runtime on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an O (8 k k (| V | + | E |)) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where G = (V , E) is the graph with precedence constraints. [ABSTRACT FROM AUTHOR]

Graph Burning asks, given a graph G = (V , E) and an integer k, whether there exists (b 0 , ⋯ , b k - 1) ∈ V k such that every vertex in G has distance at most i from some b i . This problem is known to be NP-complete even on connected caterpillars of maximum degree 3. We study the parameterized complexity of this problem and answer all questions by Kare and Reddy [IWOCA 2019] about the parameterized complexity of the problem. We show that the problem is W[2]-complete parameterized by k and that it does not admit a polynomial kernel parameterized by vertex cover number unless NP ⊆ coNP / poly . We also show that the problem is fixed-parameter tractable parameterized by clique-width plus the maximum diameter among all connected components. This implies the fixed-parameter tractability parameterized by modular-width, by treedepth, and by distance to cographs. Using a different technique, we show that parameterization by distance to split graphs is also tractable. We finally show that the problem parameterized by max leaf number is XP. [ABSTRACT FROM AUTHOR]

Token Sliding Optimization asks whether there exists a sequence of at most ℓ steps that transforms independent set S into T , where at each step a token slides to an unoccupied neighboring vertex (while maintaining independence). In Token Jumping Optimization , we are instead allowed to jump from a vertex to any unoccupied vertex. Both problems are known to be FPT when parameterized by ℓ on nowhere dense graphs. In this work, we show that both problems are FPT for parameter k + ℓ + d on d -degenerate graphs as well as for parameter | M | + ℓ + Δ on graphs having a modulator M to maximum degree Δ. We complement these results by showing that for parameter ℓ both problems become hard already on 2-degenerate graphs. Finally, we show that using such families one can obtain a unified algorithm for the standard Token Jumping problem parameterized by k on degenerate and nowhere dense graphs. [ABSTRACT FROM AUTHOR]

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry Δ are solvable in time g(d,Δ)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual treedepth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*, Δ) poly(n) where d* is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , A ⊆ V , and integers k and ℓ , the (A , ℓ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly ℓ that have endpoints in A and internal points in V \ A . We study the parameterized complexity of this problem with parameters |A|, ℓ , k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when ℓ ≤ 3 , while it is NP-complete for constant ℓ ≥ 4 . We also show that the problem is W[1]-hard parameterized by pathwidth + | A | , while it is fixed-parameter tractable parameterized by treewidth + ℓ . Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at most ℓ . We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where |A| or ℓ is a constant. [ABSTRACT FROM AUTHOR]

The classical, linear-time solvable Feedback Edge Set problem is concerned with finding a minimum number of edges intersecting all cycles in a (static, unweighted) graph. We provide a first study of this problem in the setting of temporal graphs , where edges are present only at certain points in time. We find that there are four natural generalizations of Feedback Edge Set , all of which turn out to be NP-hard. We also study the tractability of these problems with respect to several parameters (solution size, lifetime, and number of graph vertices, among others) and obtain some parameterized hardness but also fixed-parameter tractability results. [ABSTRACT FROM AUTHOR]

In this paper we study the parameterized complexity for the Maximum Happy Set problem (MaxHS): For an undirected graph G = (V , E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S ; otherwise unhappy. Given an undirected graph G = (V , E) and an integer k , the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k , by neighborhood diversity, or by cluster deletion number. [ABSTRACT FROM AUTHOR]

Clustering genes in similarity graphs is a popular approach for orthology prediction. Most algorithms group genes without considering their species, which results in clusters that contain several paralogous genes. Moreover, clustering is known to be problematic when in-paralogs arise from ancient duplications. Recently, we proposed a two-step process that avoids these problems. First, we infer clusters of only orthologs (i.e. with only genes from distinct species), and second, we infer the missing inter-cluster orthologs. In this paper, we focus on the first step, which leads to a problem we call Colorful Clustering. In general, this is as hard as classical clustering. However, in similarity graphs, the number of species is usually small, as well as the neighborhood size of genes in other species. We therefore study the problem of clustering in which the number of colors is bounded by k , and each gene has at most d neighbors in another species. We show that the well-known cluster editing formulation remains NP-hard even when d = 1 and k ∈ O (1). We then propose a fixed-parameter algorithm in k + d to find the single best cluster in the graph. We implemented this algorithm and included it in the aforementioned two-step approach. Experiments on simulated data show that this approach performs favorably to applying only an unconstrained clustering step. [ABSTRACT FROM AUTHOR]

We study the NP-hard graph problem Collapsed k-Core where, given an undirected graph G and integers b, x, and k, we are asked to remove b vertices such that the k-core of remaining graph, that is, the (uniquely determined) largest induced subgraph with minimum degree k, has size at most x. Collapsed k-Core was introduced by Zhang et al. (2017) and it is motivated by the study of engagement behavior of users in a social network and measuring the resilience of a network against user drop outs. Collapsed k-Core is a generalization of r-Degenerate Vertex Deletion (which is known to be NP-hard for all r ≥ 0) where, given an undirected graph G and integers b and r, we are asked to remove b vertices such that the remaining graph is r-degenerate, that is, every its subgraph has minimum degree at most r. We investigate the parameterized complexity of Collapsed k-Core with respect to the parameters b, x, and k, and several structural parameters of the input graph. We reveal a dichotomy in the computational complexity of Collapsed k-Core for k ≤ 2 and k ≥ 3. For the latter case it is known that for all x ≥ 0 Collapsed k-Core is W[P]-hard when parameterized by b. For k ≤ 2 we show that Collapsed k-Core is W[1]-hard when parameterized by b and in FPT when parameterized by (b + x). Furthermore, we outline that Collapsed k-Core is in FPT when parameterized by the treewidth of the input graph and presumably does not admit a polynomial kernel when parameterized by the vertex cover number of the input graph. [ABSTRACT FROM AUTHOR]

Given n subspaces of a finite-dimensional vector space over a fixed finite field F, we wish to find a "branch-decomposition" of these subspaces of width at most k that is a subcubic tree T with n leaves mapped bijectively to the subspaces such that for every edge e of T, the sum of subspaces associated to the leaves in one component of T -e and the sum of subspaces associated to the leaves in the other component have the intersection of dimension at most k. This problem includes the problems of computing branch-width of F-represented matroids, rank-width of graphs, branch-width of hypergraphs, and carving-width of graphs. We present a fixed-parameter algorithm to construct such a branch-decomposition of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over F. Our algorithm is analogous to the algorithm of Bodlaender and Kloks [J. Algorithms, 21 (1996), pp. 358-402] on tree-width of graphs. To extend their framework to branchdecompositions of vector spaces, we developed highly generic tools for branch-decompositions on vector spaces. The only known previous fixed-parameter algorithm for branch-width of F-represented matroids was due to Hliněný and Oum [SIAM J. Comput., 38 (2008), pp. 1012-1032] that runs in time O(n3) where n is the number of elements of the input F-represented matroid. But their method is highly indirect. Their algorithm uses the nontrivial fact by Geelen et al. [J. Combin. Theory Ser. B, 88 (2003), pp. 261-265] that the number of forbidden minors is finite and uses the algorithm of Hliněný [J. Combin. Theory Ser. B, 96 (2006), pp. 325-351] on checking monadic second-order formulas on F-represented matroids of small branch-width. Our result does not depend on such a fact and is completely self-contained, and yet matches their asymptotic running time for each fixed k. [ABSTRACT FROM AUTHOR]

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in contrast to practice where data is inherently dynamic. A temporal graph has an edge set that changes over time. We present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and integers k and Δ, we ask for a coloring sequence with at most k colors for each vertex such that in every time window of Δ consecutive time steps, in which an edge is present, this edge is properly colored at least once. We thoroughly investigate the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V , E) the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as weak and strong such that at most k edges are weak and for each induced P 3 in G at least one edge is weak. We study the following generalizations of STC with c different strong edge colors. In Multi-STC an induced P 3 may receive two strong labels as long as they are different. In Edge-List Multi-STC and Vertex-List Multi-STC we may restrict the set of permitted colors for each edge of G. We show that, under the Exponential Time Hypothesis (ETH), Edge-List Multi-STC and Vertex-List Multi-STC cannot be solved in time 2 o (| V | 2). We proceed with a parameterized complexity analysis in which we extend previous algorithms and kernelizations for STC [11,14] to the three variants or outline the limits of such an extension. [ABSTRACT FROM AUTHOR]

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information spread over social networks and biological diseases spreading over contact networks. Often, the networks over which these processes spread are dynamic in nature, and can be modelled with temporal graphs. Here, we study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path. We introduce a natural edge-deletion problem for temporal graphs and provide positive and negative results on its computational complexity and approximability. [ABSTRACT FROM AUTHOR]

For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that (1) the subgraph induced by each cluster is drawn in the interior of the corresponding disk, (2) each edge intersects any disk at most once, and (3) the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA'95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT (resp., XP) algorithm for embedded flat (resp., non-flat) clustered graphs, when parameterized by the carving-width of the dual graph of the input. These are the first FPT and XP algorithms for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. In particular, our algorithm runs in quadratic time for flat instances of bounded treewidth and bounded face size. To further strengthen the relevance of this result, we show that an algorithm with running time O(r(n)) for flat instances whose underlying graph has pathwidth 1 would result in an algorithm with running time O(r(n)) for flat instances and with running time O (r (n 2) + n 2) for general, possibly non-flat, instances. [ABSTRACT FROM AUTHOR]

We introduce and investigate the approximability of the maximum binary tree problem (MBT) in directed and undirected graphs. The goal in MBT is to find a maximum-sized binary tree in a given graph. MBT is a natural variant of the well-studied longest path problem, since both can be viewed as finding a maximum-sized tree of bounded degree in a given graph. The connection to longest path motivates the study of MBT in directed acyclic graphs (DAGs), since the longest path problem is solvable efficiently in DAGs. In contrast, we show that MBT in DAGs is hard: it has no efficient exp (- O (log n / log log n)) -approximation under the exponential time hypothesis, where n is the number of vertices in the input graph. In undirected graphs, we show that MBT has no efficient exp (- O (log 0.63 n)) -approximation under the exponential time hypothesis. Our inapproximability results rely on self-improving reductions and structural properties of binary trees. We also show constant-factor inapproximability assuming P ≠ NP . In addition to inapproximability results, we present algorithmic results along two different flavors: (1) We design a randomized algorithm to verify if a given directed graph on n vertices contains a binary tree of size k in 2 k poly (n) time. (2) Motivated by the longest heapable subsequence problem, introduced by Byers, Heeringa, Mitzenmacher, and Zervas, ANALCO 2011, which is equivalent to MBT in permutation DAGs, we design efficient algorithms for MBT in bipartite permutation graphs. [ABSTRACT FROM AUTHOR]

Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-coloring is a vertex coloring c: V (G) \rightarrow \{ 1, 2, . . ., q\} such that for each vertex v \in V (G) there is a vertex in N(v) that is uniquely colored from the rest of the vertices in N(v). When we replace N(v) by the closed neighborhood N[v], then we call such a coloring a q-closed neighborhood conflict-free coloring or simply q-CNCF-coloring. In this paper, we study the NP-hard decision questions of whether for a constant q an input graph has a q-ONCF-coloring or a q-CNCF-coloring. We will study these two problems in the parameterized setting. First of all, we study running time bounds on fixed-parameter tractable algorithms for these problems when parameterized by treewidth. We improve the existing upper bounds, and also provide lower bounds on the running time under the exponential time hypothesis and the strong exponential time hypothesis. Second, we study the kernelization complexity of both problems, using vertex cover as the parameter. We show that both (q \geq 2)-ONCF-coloring and (q \geq 3)-CNCF-coloring cannot have polynomial kernels when parameterized by the size of a vertex cover unless \sansN \sansP \subseteq \sansc \sanso \sansN \sansP/\sansp \sanso \sansl \sansy. On the other hand, we obtain a polynomial kernel for 2-CNCF-coloring parameterized by vertex cover. We conclude the study with some combinatorial results. Denote \chi ON(G) and \chi CN(G) to be the minimum number of colors required to ONCF-color and CNCFcolor G, respectively. Upper bounds on \chi CN(G) with respect to structural parameters like minimum vertex cover size, minimum feedback vertex set size, and treewidth are known. To the best of our knowledge only an upper bound on \chi ON(G) with respect to minimum vertex cover size was known. We provide tight bounds for \chi ON(G) with respect to minimum vertex cover size. Also, we provide the first upper bounds on \chi ON(G) with respect to minimum feedback vertex set size and treewidth. [ABSTRACT FROM AUTHOR]

• A quadratic-time algorithm for the maximum bisection problem on bounded-treewidth graphs is presented. • The running time of our algorithm is optimal, assuming some complexity-theoretic lower bounds. • Several algorithmic and complexity results for restricted graph classes are discussed. The maximum/minimum bisection problems are, given an edge-weighted graph, to find a bipartition of the vertex set into two sets whose sizes differ by at most one, such that the total weight of edges between the two sets is maximized/minimized. Although these two problems are known to be NP-hard, there is an efficient algorithm for bounded-treewidth graphs. In particular, Jansen et al. (2005) [5] gave an O (2 t n 3) -time algorithm when given a tree decomposition of width t of the input graph, where n is the number of vertices of the input graph. Eiben et al. (2021) [10] improved the dependency of n in the running time by giving an O (8 t t 5 n 2 log ⁡ n) -time algorithm. Moreover, they showed that there is no O (n 2 − ε) -time algorithm for trees under some reasonable complexity assumption. In this paper, we show an O (2 t (t n) 2) -time algorithm for both problems, which is asymptotically tight to their conditional lower bound. We also show that the exponential dependency of the treewidth is asymptotically optimal under the Strong Exponential Time Hypothesis. Finally, we discuss the (in)tractability of both problems with respect to special graph classes. [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]