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]

Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA'14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, Kt -free unit d-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of d-contractions, witness that the twin-width is at most d. We show that FO model checking, that is deciding if a given first-order formula ϕ evaluates to true for a given binary structure G on a domain D, is FPT in |ϕ| on classes of bounded twin-width, provided the witness is given. More precisely, being given a d-contraction sequence for G, our algorithm runs in time f (d, |ϕ|) · |D| where f is a computable but non-elementary function. We also prove that bounded twin-width is preserved under FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS'15]. [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]

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]

We introduce a natural but seemingly yet unstudied variant of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. The novelty of our new variant lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k ≤ m days. This corresponds to an equitable schedule where each client is guaranteed a minimal level of service throughout the period of m days. We provide a thorough analysis of the computational complexity of three main variants of this problem, identifying both efficient algorithms and worst-case intractability results. [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]