Search

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et al. [5] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture [8] in the case of ordered graphs. [ABSTRACT FROM AUTHOR]

We provide a O (k 2 log k) vertex kernel for cograph edge editing. This improves a cubic kernel found by Guillemot, Havet, Paul and Perez (Guillemot et al., 2010) which involved four reduction rules. We generalize one of their rules, based on packing of induced paths of length four, by introducing t -modules, which are modules up to t edge modifications. The key fact is that large t -modules cannot be edited more than t times, and this allows to obtain a near quadratic kernel. The extra log k factor seems tricky to remove as it is necessary in the combinatorial lemma on trees which is central in our proof. Nevertheless, we think that a quadratic bound should be reachable. [ABSTRACT FROM AUTHOR]

The Set Packing problem is, given a collection of sets S over a ground set U, to find a maximum collection of sets that are pairwise disjoint. The problem is among the most fundamental NP-hard optimization problems that have been studied extensively in various computational regimes. The focus of this work is on parameterized complexity, Parameterized Set Packing (PSP): Given parameter r ∈ N , is there a collection S ′ ⊆ S : | S ′ | = r such that the sets in S ′ are pairwise disjoint? Unfortunately, the problem is not fixed parameter tractable unless W [ 1 ] = FPT , and, in fact, an "enumerative" running time of | S | Ω (r) is required unless the exponential time hypothesis (ETH) fails. This paper is a quest for tractable instances of Set Packing from parameterized complexity perspectives. We say that the input (U , S) is "compact" if | U | = f (r) · poly (log | S |) , for some f (r) ≥ r . In the Compact PSP problem, we are given a compact instance of PSP. In this direction, we present a "dichotomy" result of PSP: When | U | = f (r) · o (log | S |) , PSP is in FPT, while for | U | = r · Θ (log (| S |)) , the problem is W[1]-hard; moreover, assuming ETH, Compact PSP does not admit | S | o (r / log r) time algorithm even when | U | = r · Θ (log (| S |)) . Although certain results in the literature imply hardness of compact versions of related problems such as Set r -Covering and Exact r -Covering, these constructions fail to extend to Compact PSP. A novel contribution of our work is the identification and construction of a gadget, which we call Compatible Intersecting Set System pair, that is crucial in obtaining the hardness result for Compact PSP. Finally, our framework can be extended to obtain improved running time lower bounds for Compact r -VectorSum. [ABSTRACT FROM AUTHOR]

We present a parameterized dichotomy for the k - Sparsest Cut problem in weighted and unweighted versions. In particular, we show that the weighted k - Sparsest Cut problem is NP-hard for every k ≥ 3 even on graphs with bounded vertex cover number. Also, the unweighted k - Sparsest Cut problem is W[1]-hard when parameterized by the three combined parameters tree-depth, feedback vertex set number, and k. On the positive side, we show that the unweighted k - Sparsest Cut problem is FPT when parameterized by the vertex cover number and k , and when k is fixed, it is FPT with respect to the treewidth. Moreover, we show that the generalized version κ - Small-Set Expansion problem is FPT when parameterized by κ and the maximum degree of the graph, though it is W[1]-hard for each of these parameters separately. [ABSTRACT FROM AUTHOR]

Our work is motivated by the challenges presented in preparing arrays of atoms for use in quantum simulation. The recently-developed process of loading atoms into traps results in approximately half of the traps being filled. To consolidate the atoms so that they form a dense and regular arrangement, such as all locations in a grid, atoms are rearranged using moving optical tweezers. Time is of the essence, as the longer that the process takes and the more that atoms are moved, the higher the chance that atoms will be lost in the process. Viewed as a problem on graphs, we wish to solve the problem of reconfiguring one arrangement of tokens (representing atoms) to another using as few moves as possible. Because the problem is NP-complete on general graphs as well as on grids, we focus on the parameterized complexity for various parameters, considering both undirected and directed graphs, and tokens with and without labels. For unlabelled tokens, the problem is fixed-parameter tractable when parameterized by the number of tokens, the number of moves, or the number of moves plus the number of vertices without tokens in either the source or target configuration, but intractable when parameterized by the difference between the number of moves and the number of differences in the placement of tokens in the source and target configurations. When labels are added to tokens, however, most of the tractability results are replaced by hardness results. [ABSTRACT FROM AUTHOR]

Computing planar orthogonal drawings with the minimum number of bends is one of the most studied topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia in SIAM J Comput 31(2):601–625, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number b of bends, the number k of vertices of degree at most two, and the treewidth tw of the input graph (Di Giacomo et al. in J Comput Syst Sci 125:129–148, 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by b + k . As a consequence, rectilinear planarity testing lies in FPT parameterized by the number of vertices of degree at most two. We also prove that our choice of parameters is minimal, as deciding if an orthogonal drawing with at most b bends exists is already NP-hard when k is zero (i.e., the problem is para-NP-hard parameterized in k); hence, there is neither an FPT nor an XP algorithm parameterized only by the parameter k (unless P = NP). In addition, we prove that the problem is W[1]-hard parameterized by k + tw , complementing a recent result (Jansen et al. in Upward and orthogonal planarity are W[1]-hard parameterized by treewidth. CoRR, abs/2309.01264, 2023; in: Bekos MA, Chimani M (eds) Graph Drawing and Network Visualization, vol 14466, Springer, Cham, pp 203–217, 2023) that shows W[1]-hardness for the parameterization b + tw . As a consequence, we are able to trace a clear parameterized tractability landscape for the bend-minimum orthogonal planarity problem with respect to the three parameters b, k, and tw . [ABSTRACT FROM AUTHOR]

Parameterized complexity, introduced to efficiently solve NP‐hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity (nd$$ \mathsf{nd} $$) for several graph theoretic problems in P$$ P $$: Maximumb$$ b $$‐Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular‐width (mw$$ \mathsf{mw} $$) and consequently—as nd$$ \mathsf{nd} $$ is a special case of mw$$ \mathsf{mw} $$—by nd$$ \mathsf{nd} $$. However, the proposed novel algorithms allow for improving the computational complexity from time O(f(mw)·n+m)$$ O\left(f\left(\mathsf{mw}\right)\cdotp n+m\right) $$—where n$$ n $$ and m$$ m $$ denote, respectively, the number of vertices and edges in the input graph—to time O(g(nd)+n+m)$$ O\left(g\left(\mathsf{nd}\right)+n+m\right) $$ which is only additive in the size of the input. Then we consider some classical NP‐hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter. [ABSTRACT FROM AUTHOR]

We introduce the multicolored graph realization problem (MGR). The input to this problem is a colored graph (G , φ) , i.e., a graph G together with a coloring φ on its vertices. We associate each colored graph (G , φ) with a cluster graph (G φ) in which, after collapsing all vertices with the same color to a node, we remove multiple edges and self-loops. A set of vertices S is multicolored when S has exactly one vertex from each color class. The MGR problem is to decide whether there is a multicolored set S so that, after identifying each vertex in S with its color class, G [ S ] coincides with G φ. The MGR problem is related to the well-known class of generalized network problems, most of which are NP-hard, like the generalized Minimum Spanning Tree problem. The MGR is a generalization of the multicolored clique problem, which is known to be W [ 1 ] -hard when parameterized by the number of colors. Thus, MGR remains W [ 1 ] -hard, when parameterized by the size of the cluster graph. These results imply that the MGR problem is W [ 1 ] -hard when parameterized by any graph parameter on G φ , among which lies treewidth. Consequently, we look at the instances of the problem in which both the number of color classes and the treewidth of G φ are unbounded. We consider three natural such graph classes: chordal graphs, convex bipartite graphs and 2-dimensional grid graphs. We show that MGR is NP-complete when G φ is either chordal, biconvex bipartite, complete bipartite or a 2-dimensional grid. Our reductions show that the problem remains hard even when the maximum number of vertices in a color class is 3. In the case of the grid, the hardness holds even for graphs with bounded degree. We provide a complexity dichotomy with respect to cluster size. [ABSTRACT FROM AUTHOR]

The main complexity classes of the Parameterized Intractability Theory are based on weighted Boolean circuit satisfiability problems and organized into a hierarchy so-called W-hierarchy. The W-hierarchy enables fine-grained complexity analyses of parameterized problems that are unlikely to belong to the FPT class. In this paper, we introduce the Th-hierarchy, a natural generalization of the W-hierarchy defined by unweighted threshold circuit satisfiability problems. Investigating the relationship between Th-hierarchy and W-hierarchy, we discuss the complexity of transforming Threshold circuits into Boolean circuits, and observe that sorting networks are powerful tools to handle such transformations. First, we show that these hierarchies collapse at the last level (W[P] = Th[P]). After that, we present a time complexity analysis of an AKS sorting network construction, which supports some of our results. Finally, we prove that Th[ t ] ⊆ W[SAT] for every t ∈ ℕ. As a by-product, our studies suggest that it is relevant to consider a new class based on logarithmic depth circuits in the W-hierarchy. [ABSTRACT FROM AUTHOR]

In k-Digraph Coloring we are given a digraph and are asked to partition its vertices into at most k sets, so that each set induces a DAG. This well-known problem is NP-hard, as it generalizes (undirected) k-Coloring, but becomes trivial if the input digraph is acyclic. This poses the natural parameterized complexity question of what happens when the input is "almost" acyclic. In this paper we study this question using parameters that measure the input's distance to acyclicity in either the directed or the undirected sense. In the directed sense perhaps the most natural notion of distance to acyclicity is directed feedback vertex set. It is already known that, for all k ≥ 2, k-Digraph Coloring is NP-hard on digraphs of directed feedback vertex set of size at most k + 4. We strengthen this result to show that, for all k ≥ 2, k-Digraph Coloring is already NP-hard for directed feedback vertex set of size exactly k. This immediately provides a dichotomy, as k-Digraph Coloring is trivial if directed feedback vertex set has size at most k − 1. Refining our reduction we obtain three further consequences: (i) 2-Digraph Coloring is NP-hard for oriented graphs of directed feedback vertex set at most 3; (ii) for all k ≥ 2, k-Digraph Coloring is NP-hard for graphs of feedback arc set of size at most k2; interestingly, this leads to a second dichotomy, as we show that the problem is FPT by k if feedback arc set has size at most k2 − 1; (iii) k-Digraph Coloring is NP-hard for graphs of directed feedback vertex k, even if the maximum degree Δ is at most 4k − 1; we show that this is also almost tight, as the problem becomes FPT for digraphs of directed feedback vertex set of size k and Δ ≤ 4k − 3. Since these results imply that the problem is also NP-hard on graphs of bounded directed treewidth, we then consider parameters that measure the distance from acyclicity of the underlying graph. On the positive side, we show that k-Digraph Coloring admits an FPT algorithm parameterized by treewidth, whose parameter dependence is (tw!)ktw. Since this is considerably worse than the ktw dependence of (undirected) k-Coloring, we pose the question of whether the tw! factor can be eliminated. Our main contribution in this part is to settle this question in the negative and show that our algorithm is essentially optimal, even for the much more restricted parameter treedepth and for k = 2. Specifically, we show that an FPT algorithm solving 2-Digraph Coloring with dependence tdo(td) would contradict the ETH. Then, we consider the class of tournaments. It is known that deciding whether a tournament is 2-colorable is NP-complete. We present an algorithm that decides if we can 2-color a tournament in O ∗ ( 6 3 n) time. Finally, we explain how this algorithm can be modified to decide if a tournament is k-colorable. [ABSTRACT FROM AUTHOR]

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P ∩ Z n , assuming that P is a polyhedron, defined by systems A x ≤ b or A x = b , x ≥ 0 with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on sparse instances with bounded elements in terms of the computational complexity. Assuming that the matrix A has bounded elements, our complexity bounds have the form s O (n) , where s is the minimum between numbers of non-zeroes in columns and rows of A, respectively. For s = o (log n) , this bound outperforms the state-of-the-art ILP feasibility complexity bound (log n) O (n) , due to Reis & Rothvoss (in: 2023 IEEE 64th Annual symposium on foundations of computer science (FOCS), IEEE, pp. 974–988). For s = ϕ o (log n) , where ϕ denotes the input bit-encoding length, it outperforms the state-of-the-art ILP counting complexity bound ϕ O (n log n) , due to Barvinok et al. (in: Proceedings of 1993 IEEE 34th annual foundations of computer science, pp. 566–572, https://doi.org/10.1109/SFCS.1993.366830, 1993), Dyer, Kannan (Math Oper Res 22(3):545–549, https://doi.org/10.1287/moor.22.3.545, 1997), Barvinok, Pommersheim (Algebr Combin 38:91–147, 1999), Barvinok (in: European Mathematical Society, ETH-Zentrum, Zurich, 2008). We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximum Matching problems. [ABSTRACT FROM AUTHOR]

Given a bipartite graph G, the Bicluster Editing problem asks for the minimum number of edges to insert or delete in G so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter k, which is the number of allowed modified edges. We first show that one can obtain a kernel with 4.5k vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time O ∗ (2. 581 k) . Our algorithm has the advantage of being conceptually simple and should be easy to implement. [ABSTRACT FROM AUTHOR]

In this article, we study the computational complexity of solving a class of block structured integer programs (IPs), the so-called multistage stochastic IPs. A multistage stochastic IP is an IP of the form min {cTx | Ax = b, x ≥ 0, x integral} where the constraint matrix \({A}\) consists of small block matrices ordered on the diagonal line, and for each stage there are larger blocks with few columns connecting the blocks in a treelike fashion. Over the past few years there was enormous progress in the area of block structured IPs. For many of the known block IP classes, such as n-fold, tree-fold, and two-stage stochastic IPs, nearly matching upper and lower bounds are known concerning their computational complexity. One of the major gaps that remained, however, was the parameter dependency in the running time for an algorithm solving multistage stochastic IPs. Previous algorithms require a tower of t exponentials, where t is the number of stages. In contrast, only a double exponential lower bound was known based on the exponential time hypothesis. In this article, we show that the tower of t exponentials is actually not necessary. We show an improved running time of \(2^{(d\Vert A \Vert _\infty)^{\mathcal {O}(d^{3t+1})}} \cdot rn\log ^{\mathcal {O}(2^d)}(rn)\) for the algorithm solving multistage stochastic IPs, where d is the sum of columns in the connecting blocks and rn is the number of rows. Hence, we obtain the first bound by an elementary function for the running time of an algorithm solving multistage stochastic IPs. In contrast to previous works, our algorithm has only a triple exponential dependency on the parameters and only doubly exponential for every constant t. By this, we come very close to the known double exponential bound that holds already for two-stage stochastic IPs, i.e., multistage stochastic IPs with two stages. The improved running time of the algorithm is based on new bounds for the proximity of multistage stochastic IPs. The idea behind the bound is based on generalization of a structural lemma originally used for two-stage stochastic IPs. While the structural lemma requires iteration to be applied to multistage stochastic IPs, our generalization directly applies to inherent combinatorial properties of multiple stages. Already a special case of our lemma yields an improved bound for the Graver complexity of multistage stochastic IPs. [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]

In the Determinant Maximization problem, given an n × n positive semi-definite matrix A in Q n × n and an integer k, we are required to find a k × k principal submatrix of A having the maximum determinant. This problem is known to be NP-hard and further proven to be W[1]-hard with respect to k by Koutis (Inf Process Lett 100:8–13, 2006); i.e., a f (k) n O (1) -time algorithm is unlikely to exist for any computable function f. However, there is still room to explore its parameterized complexity in the restricted case, in the hope of overcoming the general-case parameterized intractability. In this study, we rule out the fixed-parameter tractability of Determinant Maximization even if an input matrix is extremely sparse or low rank, or an approximate solution is acceptable. We first prove that Determinant Maximization is NP-hard and W[1]-hard even if an input matrix is an arrowhead matrix; i.e., the underlying graph formed by nonzero entries is a star, implying that the structural sparsity is not helpful. By contrast, Determinant Maximization is known to be solvable in polynomial time on tridiagonal matrices (Al-Thani and Lee, in: LAGOS, 2021). Thereafter, we demonstrate the W[1]-hardness with respect to the rankr of an input matrix. Our result is stronger than Koutis' result in the sense that any k × k principal submatrix is singular whenever k > r . We finally give evidence that it is W[1]-hard to approximate Determinant Maximization parameterized by k within a factor of 2 - c k for some universal constant c > 0 . Our hardness result is conditional on the Parameterized Inapproximability Hypothesis posed by Lokshtanov et al. (in: SODA, 2020), which asserts that a gap version of Binary Constraint Satisfaction Problem is W[1]-hard. To complement this result, we develop an ε -additive approximation algorithm that runs in ε - r 2 · r O (r 3) · n O (1) time for the rank r of an input matrix, provided that the diagonal entries are bounded. [ABSTRACT FROM AUTHOR]

We consider GROUP CONTROL BY ADDING INDIVIDUALS (GCAI) in the setting of group identification for two procedural rules—the consensus-start-respecting rule and the liberal-start-respecting rule. It is known that GCAI for both rules are NP-hard, but whether they are fixed-parameter tractable with respect to the number of distinguished individuals remained open. We resolve both open problems in the affirmative. In addition, we strengthen the NP-hardness of GCAI by showing that, with respect to the natural parameter the number of added individuals, GCAI for both rules are W[2]-hard. Notably, the W[2]-hardness for the liberal-start-respecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones property. However, for the consensus-start-respecting rule, the problem becomes polynomial-time solvable in this special case. We also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property, and show that under this restriction GCAI for both rules turn out to be polynomial-time solvable. Our reductions for showing W[2]-hardness also imply several algorithmic lower bounds. [ABSTRACT FROM AUTHOR]

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset S ⊆ V (G) of size at most k such that G - S is a forest. After a long line of improvement, recently, Li and Nederlof [TALG, 2022] designed a randomized algorithm for the problem running in time O ⋆ (2. 7 k) ∗ . In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in G - S has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers k , ℓ ∈ N , and the objective is to test whether there exists a vertex subset S of size at most k, such that G - S is ℓ edges away from a forest. In this paper, using the methodology of Li and Nederlof [TALG, 2022], we obtain the current fastest algorithms for all these problems. In particular we obtain the following randomized algorithms. Independent Feedback Vertex Set can be solved in time O ⋆ (2. 7 k) . Pseudo Forest Deletion can be solved in time O ⋆ (2. 85 k) . Almost Forest Deletion can be solved in time O ⋆ (min { 2. 85 k · 8. 54 ℓ , 2. 7 k · 36. 61 ℓ , 3 k · 1. 78 ℓ }) . [ABSTRACT FROM AUTHOR]

In this paper, we study the Harmless Set problem from a parameterized complexity perspective. Given a graph G = (V , E) , a threshold function t : V → N and an integer k, we study Harmless Set, where the goal is to find a subset of vertices S ⊆ V of size at least k such that every vertex v ∈ V has fewer than t(v) neighbours in S. On the positive side, we obtain fixed-parameter algorithms for the problem when parameterized by the neighbourhood diversity, the twin-cover number and the vertex integrity of the input graph. We complement two of these results from the negative side. On dense graphs, we show that the problem is W[1]-hard parameterized by cluster vertex deletion number—a natural generalization of the twin-cover number. We show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, and treedepth—a natural generalization of the vertex integrity. We thereby resolve one open question stated by Bazgan and Chopin (Discrete Optim 14(C):170–182, 2014) concerning the complexity of Harmless Set parameterized by the treewidth of the input graph. We also show that Harmless Set for a special case where each vertex has the threshold set to half of its degree (the so-called Majority Harmless Set problem) is W[1]-hard when parameterized by the treewidth of the input graph. Given a graph G and an irredundant c-expression of G, we prove that Harmless Set can be solved in XP-time when parameterized by clique-width. [ABSTRACT FROM AUTHOR]

In this article, we study the complexity of weighted team definability for logics with team semantics. This problem is a natural analog of one of the most studied problems in parameterized complexity, the notion of weighted Fagin-definability, which is formulated in terms of satisfaction of first-order formulas with free relation variables. We focus on the parameterized complexity of weighted team definability for a fixed formula $\varphi$ of central team-based logics. Given a first-order structure $\mathcal{A}$ and the parameter value $k\in \mathbb N$ as input, the question is to determine whether $\mathcal{A},T\models \varphi$ for some team T of size k. We show several results on the complexity of this problem for dependence, independence, and inclusion logic formulas. Moreover, we also relate the complexity of weighted team definability to the complexity classes in the well-known W-hierarchy as well as paraNP. [ABSTRACT FROM AUTHOR]

A homomorphism φ from a guest graph G to a host graph H is locally bijective, injective, or surjective if for every u ∈ V(G), the restriction of φ to the neighbourhood ofu is bijective, injective, or surjective, respectively. We prove a number of new FPT (fixed-parameter tractable), W[1]-hard, and paraNP-complete results for the corresponding decision problems LBHOM, LIHOM, and LSHOM by considering a hierarchy of parameters of the guest graph G. In this way we strengthen several existing results. For our FPT results, we develop a new algorithmic framework that involves a general ILP (integer linear program) model. We also use our framework to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms. [ABSTRACT FROM AUTHOR]

Given two integers ℓ and p as well as ℓ graph classes H1, . . ., Hℓ, the problems GraphPart(H1, . . ., Hℓ, p), VertPart(H1, . . ., Hℓ), and EdgePart(H1, . . ., Hℓ) ask, given graph G as input, whether V (G), V (G), E(G) respectively can be partitioned into ℓ sets S1, . . ., Sℓ such that, for each i between 1 and ℓ, G[Si] ∈ Hi, G[Si] ∈ Hi, (V (G), Si) ∈ Hi respectively. Moreover in GraphPart(H1, . . ., Hℓ, p), we request that the number of edges with endpoints in different sets of the partition is bounded by p. We show that if there exist dynamic programming treedecomposition-based algorithms for recognizing the graph classes Hi, for each i, then we can constructively create a dynamic programming tree-decomposition-based algorithms for GraphPart(H1, . . ., Hℓ, p), VertPart(H1, . . ., Hℓ), and EdgePart(H1, . . ., Hℓ). We apply this approach to known problems. For well-studied problems, like VERTEX COVER and GRAPH q-COLORING, we obtain running times that are comparable to those of the best known problemspecific algorithms. For an exotic problem from bioinformatics, called DISPLAYGRAPH, this approach improves the known algorithm parameterized by treewidth. [ABSTRACT FROM AUTHOR]

We give a new decomposition theorem in unit disk graphs (UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits an "almost" Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010], and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, and therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi (www.youtube.com/watch?v=2Bq2gy1N01w) regarding the existence of contraction decompositions for classes of graphs beyond H-minor free graphs though under a relaxation of the original formulation. Second, we present a "parameteric version" of our new decomposition theorem. We prove that there is an algorithm that, given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of \(\mathcal {O}(k)\) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into \(\mathcal {O}(k)\) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece that is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or slightly super-exponential) algorithms for well-studied problems such as Min Bisection, Steiner Cut, s-Way Cut, and Edge Multiway Cut-Uncut on UDGs; these algorithms are substantially faster than the best-known algorithms for these problems on general graphs. [ABSTRACT FROM AUTHOR]

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G, H, and lists L (v) ⊆ V(H) for every v∈ V(G), a f:V(G)→ V(H) that preserves the edges (i.e., uv∈ E(G) implies f(u)f(v)∈ E(H)) and respects the lists (i.e., f(v)∈ L(v)). Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time |V(H)|t⋅ n(1). Our main result is determining, for every fixed graph H, how much the base |V(H)| in the running time can be improved. For a connected graph H, we define irr(H) in the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S⊆ V(H) where any two vertices have different neighborhoods; if H is bipartite, then irr(H) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr(H) as the maximum of irr(C) over every connected component C of H. It follows from earlier results that if irr(H)=1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H, the number of list homomorphisms from (G,L) to H — can be counted in time \(\operatorname{irr}(H)^t\cdot n^{\mathcal {O}(1)}\) if a tree decomposition of G having width at most t is given in the input, and, — given that \(\operatorname{irr}(H)\ge 2\) , cannot be counted in time \((\operatorname{irr}(H)-\varepsilon)^t\cdot n^{\mathcal {O}(1)}\) for any \(\varepsilon \gt 0\) , even if a tree decomposition of G having width at most t is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails. Thereby, we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops. [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 ArtGallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of ArtGallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of ArtGallery are all W[1]-hard with respect to k [Bonnet and Miltzow in 24th Annual European Symposium on Algorithms (Aarhus 2016)], the classic variant has an O (log k) -approximation algorithm [Bonnet and Miltzow in 33rd International Symposium on Computational Geometry (Brisbane 2017)], and it may require irrational guards [Abrahamsen et al. in 33rd International Symposium on Computational Geometry (Brisbane 2017)]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ R -complete [Abrahamsen et al. in 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018)]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)]: Is ArtGallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of ArtGallery, this case can also be viewed as the classic DominatingSet problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-VertexArtGallery is solvable in time r O (r 2) · n O (1) . Furthermore, our approach extends to assert that Vertex-BoundaryArtGallery and Boundary-VertexArtGallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-VertexArtGallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions. [ABSTRACT FROM AUTHOR]

We study the computational complexity of the problem #IndSub(Φ) of counting k-vertex induced subgraphs of a graph G that satisfy a graph property Φ. Our main result establishes an exhaustive and explicit classification for all hereditary properties, including tight conditional lower bounds under the Exponential Time Hypothesis (ETH): - If a hereditary property Φ is true for all graphs, or if it is true only for finitely many graphs, then #IndSub(Φ) is solvable in polynomial time. - Otherwise, #IndSub(Φ) is #W[1]-complete when parameterised by k, and, assuming ETH, it cannot be solved in time f(k)µ/G/o(k) for any function f. This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [TCS 02]) is tractable but counting is hard. Moreover, even for properties which are already intractable in their decision version, our results yield significantly stronger lower bounds for the counting problem. As additional result, we also present an exhaustive and explicit parameterised complexity classification for all properties that are invariant under homomorphic equivalence. By covering one of the most natural and general notions of closure, namely, closure under vertex-deletion (hereditary), we generalise some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of #IndSub(Φ) for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [FOCS 20]. [ABSTRACT FROM AUTHOR]

Deciding whether a diagram of a knot can be untangled with a given number of moves (as a part of the input) is known to be NP-complete. In this paper we determine the parameterized complexity of this problem with respect to a natural parameter called defect. Roughly speaking, it measures the efficiency of the moves used in the shortest untangling sequence of Reidemeister moves. We show that the II- moves in a shortest untangling sequence can be essentially performed greedily. Using that, we show that this problem belongs to W[P] when parameterized by the defect. We also show that this problem is W[P]-hard by a reduction from MINIMUM AXIOM SET. [ABSTRACT FROM AUTHOR]

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

Given a graph G with a terminal set R ⊆ V (G) , the Steiner tree problem (STREE) asks for a set S ⊆ V (G) \ R such that the graph induced on S ∪ R is connected. A split graph is a graph which can be partitioned into a clique and an independent set. It is known that STREE is NP-complete on split graphs White et al. (Networks 15(1):109–124, 1985). To strengthen this result, we introduce convex ordering on one of the partitions (clique or independent set), and prove that STREE is polynomial-time solvable for tree-convex split graphs with convexity on clique (K), whereas STREE is NP-complete on tree-convex split graphs with convexity on independent set (I). We further strengthen our NP-complete result by establishing a dichotomy which says that for unary-tree-convex split graphs (path-convex split graphs), STREE is polynomial-time solvable, and NP-complete for binary-tree-convex split graphs (comb-convex split graphs). We also show that STREE is polynomial-time solvable for triad-convex split graphs with convexity on I, and circular-convex split graphs. Further, we show that STREE can be used as a framework for the dominating set problem (DS) on split graphs, and hence the classical complexity (P vs NPC) of STREE and DS is the same for all these subclasses of split graphs. Finally, from the parameterized perspective with solution size being the parameter, we show that the Steiner tree problem on split graphs is W[2]-hard, whereas when the parameter is treewidth, we show that the problem is fixed-parameter tractable, and if the parameter is the solution size and the maximum degree of I (d), then we show that the Steiner tree problem on split graphs has a kernel of size at most (2 d - 1) k d - 1 + k , k = | S | . [ABSTRACT FROM AUTHOR]

In the Token Sliding problem we are given a graph G and two independent sets I s and I t in G of size k ≥ 1 . The goal is to decide whether there exists a sequence ⟨ I 1 , I 2 , ... , I ℓ ⟩ of independent sets such that for all j ∈ { 1 , ... , ℓ - 1 } the set I j is an independent set of size k, I 1 = I s , I ℓ = I t and I j ▵ I j + 1 = { u , v } ∈ E (G) . Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms I s into I t where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by k. As shown by Bartier et al. (Algorithmica 83(9):2914–2951, 2021. https://doi.org/10.1007/s00453-021-00848-1), the problem is W[1]-hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant p ≥ 5 such that the problem becomes fixed-parameter tractable on graphs of girth at least p. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph. [ABSTRACT FROM AUTHOR]

One of the first applications of the recently introduced technique of flow augmentation [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of Directed Feedback Vertex Set, a landmark problem in parameterized complexity. In this article, we explore the applicability of flow augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following: \bullet In weighted undirected graphs, Multicut is fixed-parameter tractable (FPT) in both the edge- and the vertex-deletion version. \bullet The weighted version of Group Feedback Vertex Set is FPT, even with oracle access to group operations. \bullet The weighted version of Directed Subset Feedback Vertex Set is FPT. Our study reveals Directed Symmetric Multicut as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting. [ABSTRACT FROM AUTHOR]