In this paper, we explore the limits of algorithmic meta-theorems for combinatorial reconfiguration on graphs and prove several intractability results for highly restricted cases, which tightly complement the positive results by Mouawad et al. [IPEC 2014] and Gima et al. [Algorithmica 2024]. In this setting, we study reconfiguration problems on graphs in which the feasible sets are defined by formulas of first-order or monadic second-order logic: for a formula φ(X) with a free set variable X, the problem asks whether two given sets are connected by a token-jumping sequence in which every set satisfies φ on the input graph. Our main contribution is to show that the problem is intractable even for first-order logic and for severely restricted graphs, such as paths and disjoint unions of stars or cliques. Combined with known results, these results settle the parameterized complexity for most of the well-studied structural parameters. We also study the setting where the sets to be reconfigured are small, i.e., their size is part of the parameter, and show that even in this setting the problem is hard for caterpillars, whereas it becomes tractable even for monadic second-order logic when parameterized additionally by shrub-depth.

Abstract. Directed Token Sliding asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. Directed Token Sliding is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions. In this paper, we initiate the algorithmic study of Directed Token Sliding. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees [Demaine et al., Theoret. Comput. Sci., 600 (2015), pp. 132–142], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which yield an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences.

Given a graph G = (V,E), a set T of vertex pairs, and an integer k, Hitting Geodesic Intervals asks whether there is a set S ⊆ V of size at most k such that for each terminal pair {u,v} ∈ T, the set S intersects at least one shortest u-v path. Aravind and Saxena [WALCOM 2024] introduced this problem and showed several parameterized complexity results. In this paper, we extend the known results in both negative and positive directions and present sharp complexity contrasts with respect to structural graph parameters. We first show that the problem is NP-complete even on graphs with highly restricted shortest-path structures. More precisely, we show the NP-completeness on graphs obtained by adding a single vertex to a disjoint union of 5-vertex paths. By modifying the proof of this result, we also show the NP-completeness on graphs obtained from a path by adding one vertex and on graphs obtained from a disjoint union of triangles by adding one universal vertex. Furthermore, we show the NP-completeness on graphs of bandwidth 4 and maximum degree 5 by replacing the universal vertex in the last case with a long path. Under standard complexity assumptions, these negative results rule out fixed-parameter algorithms for most of the structural parameters studied in the literature (if the solution size k is not part of the parameter). We next present fixed-parameter algorithms parameterized by k plus modular-width and by k plus vertex integrity. The algorithm for the latter case does indeed solve a more general setting that includes the parameterization by the minimum vertex multiway-cut size of the terminal vertices. We show that this is tight in the sense that the problem parameterized by the minimum vertex multicut size of the terminal pairs is W[2]-complete. We then modify the proof of this intractability result and show that the problem is W[2]-complete parameterized by k even in the setting where T = binom(Q,2) for some Q ⊆ V.

In the Telephone Broadcast problem we are given a graph G = (V,E) with a designated source vertex s ∈ V. Our goal is to transmit a message, which is initially known only to s, to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds. Following up on several recent works, we investigate the structurally parameterized complexity of Telephone Broadcast. In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph G with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha [ICALP 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from 𝒪(4^pw) to 𝒪(pw).

In this paper we study the Spanning Tree Congestion problem, where we are given an undirected graph G = (V,E) and are asked to find a spanning tree T of minimum maximum congestion. Here, the congestion of an edge e ∈ T is the number of edges uv ∈ E such that the (unique) path from u to v in T traverses e. We consider this well-studied NP-hard problem from the point of view of (structural) parameterized complexity and obtain the following results: - We resolve a natural open problem by showing that Spanning Tree Congestion is not FPT parameterized by treewidth (under standard assumptions). More strongly, we present a generic reduction which applies to (almost) any parameter of the form "vertex-deletion distance to class 𝒞", thus obtaining W[1]-hardness for more restricted parameters, including tree-depth plus feedback vertex set, or incomparable to treewidth, such as twin cover. Via a slight tweak of the same reduction we also show that the problem is NP-complete on graphs of modular-width 4. - Even though it is known that Spanning Tree Congestion remains NP-hard on instances with only one vertex of unbounded degree, it is currently open whether the problem remains hard on bounded-degree graphs. We resolve this question by showing NP-hardness on graphs of maximum degree 8. - Complementing the problem’s W[1]-hardness for treewidth, we formulate an algorithm that runs in time roughly {(k+w)}^{𝒪(w)}, where k is the desired congestion and w the treewidth, improving a previous argument for parameter k+w that was based on Courcelle’s theorem. This explicit algorithm pays off in two ways: it allows us to obtain an FPT approximation scheme for parameter treewidth, that is, a (1+ε)-approximation running in time roughly {(w/ε)}^{𝒪(w)}; and it leads to an exact FPT algorithm for parameter clique-width+k via a Win/Win argument. - Finally, motivated by the problem’s hardness for most standard structural parameters, we present FPT algorithms for several more restricted cases, namely, for the parameters vertex-deletion distance to clique; vertex integrity; and feedback edge set, in the latter case also achieving a single-exponential running time dependence on the parameter.

Finding a \emph{single} best solution is the most common objective in combinatorial optimization problems. However, such a single solution may not be applicable to real-world problems as objective functions and constraints are only ``approximately'' formulated for original real-world problems. To solve this issue, finding \emph{multiple} solutions is a natural direction, and diversity of solutions is an important concept in this context. Unfortunately, finding diverse solutions is much harder than finding a single solution. To cope with the difficulty, we investigate the approximability of finding diverse solutions. As a main result, we propose a framework to design approximation algorithms for finding diverse solutions, which yields several outcomes including constant-factor approximation algorithms for finding diverse matchings in graphs and diverse common bases in two matroids and PTASes for finding diverse minimum cuts and interval schedulings.

Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020; Fomin et al. 2020; Hanaka et al. 2021). In this paper we study the following type of problems: given an integer k, the problem asks for k solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called diverse solutions. We present a polynomial-time algorithm for finding diverse shortest st-paths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest st-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.

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, Mouawad et al. [IPEC 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 $\textrm{treewidth} + \ell$, where $\ell$ is the number of steps allowed to reach the target set. On the other hand, it is shown by Wrochna [J. Comput. Syst. Sci. 2018] that if $\ell$ is not part of the parameter, then the problem is PSPACE-complete even on graphs of bounded bandwidth. In this paper, we present the first algorithmic meta-theorems for the case where $\ell$ 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 $\textrm{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$.

A homomorphism $f$ from a guest graph $G$ to a host graph $H$ is locally bijective, injective or surjective if for every $u\in V(G)$, the restriction of $f$ to the neighbourhood of $u$ is bijective, injective or surjective, respectively. The corresponding decision problems, LBHOM, LIHOM and LSHOM, are well studied both on general graphs and on special graph classes. Apart from complexity results when the problems are parameterized by the treewidth and maximum degree of the guest graph, the three problems still lack a thorough study of their parameterized complexity. This paper fills this gap: we prove a number of new FPT, W[1]-hard and para-NP-complete results by considering a hierarchy of parameters of the guest graph $G$. For our FPT results, we do this through the development of a new algorithmic framework that involves a general ILP model. To illustrate the applicability of the new framework, we also use it to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms.

For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V(P) is connected. An s-t path P is non-disconnecting if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t.

Directed Token Sliding asks, given a directed graph and two sets of pairwise nonadjacent vertices, whether one can reach from one set to the other by repeatedly applying a local operation that exchanges a vertex in the current set with one of its out-neighbors, while keeping the nonadjacency. It can be seen as a reconfiguration process where a token is placed on each vertex in the current set, and the local operation slides a token along an arc respecting its direction. Previously, such a problem was extensively studied on undirected graphs, where the edges have no directions and thus the local operation is symmetric. Directed Token Sliding is a generalization of its undirected variant since an undirected edge can be simulated by two arcs of opposite directions. In this paper, we initiate the algorithmic study of Directed Token Sliding. We first observe that the problem is PSPACE-complete even if we forbid parallel arcs in opposite directions and that the problem on directed acyclic graphs is NP-complete and W[1]-hard parameterized by the size of the sets in consideration. We then show our main result: a linear-time algorithm for the problem on directed graphs whose underlying undirected graphs are trees, which are called polytrees. Such a result is also known for the undirected variant of the problem on trees [Demaine et al. TCS 2015], but the techniques used here are quite different because of the asymmetric nature of the directed problem. We present a characterization of yes-instances based on the existence of a certain set of directed paths, and then derive simple equivalent conditions from it by some observations, which yield an efficient algorithm. For the polytree case, we also present a quadratic-time algorithm that outputs, if the input is a yes-instance, one of the shortest reconfiguration sequences.

Abstract Given a graph $$G = (V,E)$$ G = ( V , E ) , $$A \subseteq V$$ A ⊆ V , and integers k and $$\ell $$ ℓ , the $$(A,\ell )$$ ( A , ℓ ) -Path Packing problem asks to find k vertex-disjoint paths of length exactly $$\ell $$ ℓ that have endpoints in A and internal points in $$V{\setminus }A$$ V \ A . We study the parameterized complexity of this problem with parameters |A|, $$\ell $$ ℓ , 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 $$\ell \le 3$$ ℓ ≤ 3 , while it is NP-complete for constant $$\ell \ge 4$$ ℓ ≥ 4 . We also show that the problem is W[1]-hard parameterized by pathwidth $${}+|A|$$ + | A | , while it is fixed-parameter tractable parameterized by treewidth $${}+\ell $$ + ℓ . Additionally, we study a variant called Short A-Path Packing that asks to find k vertex-disjoint paths of length at most $$\ell $$ ℓ . 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 $$\ell $$ ℓ is a constant.

Abstract Graph Burning asks, given a graph $$G = (V,E)$$ G = ( V , E ) and an integer k , whether there exists $$(b_{0},\dots ,b_{k-1}) \in V^{k}$$ ( b 0 , ⋯ , b k - 1 ) ∈ V k such that every vertex in G has distance at most i from some $$b_{i}$$ 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 $$\mathrm {NP} \subseteq \mathrm {coNP/poly}$$ 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 A graph $$G = (V,E)$$ G = ( V , E ) is a double-threshold graph if there exist a vertex-weight function $$w :V \rightarrow \mathbb {R}$$ w : V → R and two real numbers $$\mathtt {lb}, \mathtt {ub}\in \mathbb {R}$$ lb , ub ∈ R such that $$uv \in E$$ u v ∈ E if and only if $$\mathtt {lb}\le \mathtt {w}(u) + \mathtt {w}(v) \le \mathtt {ub}$$ lb ≤ w ( u ) + w ( v ) ≤ ub . In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [Algorithmica 2020] ran in $$O(n^{3} m)$$ O ( n 3 m ) time, where n and m are the numbers of vertices and edges, respectively.

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the “price of generality” of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable (FPT) to intractable? This type of question is by now very well studied, but somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that, for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes “for free.” Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy first-fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP--hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.

Mathematical modeling is a standard approach to solve many real-world problems and diversity of solutions is an important issue, emerging in applying solutions obtained from mathematical models to real-world problems. Many studies have been devoted to finding diverse solutions. Baste et al. (Algorithms 2019, IJCAI 2020) recently initiated the study of computing diverse solutions of combinatorial problems from the perspective of fixed-parameter tractability. They considered problems of finding r solutions that maximize some diversity measures (the minimum or sum of the pairwise Hamming distances among them) and gave some fixed-parameter tractable algorithms for the diverse version of several well-known problems, such as Vertex Cover, Feedback Vertex Set, d-Hitting Set}, and problems on bounded-treewidth graphs. In this work, we further investigate the (fixed-parameter) tractability of problems of finding diverse spanning trees, paths, and several subgraphs. In particular, we show that, given a graph G and an integer r, the problem of computing r spanning trees of G maximizing the sum of the pairwise Hamming distances among them can be solved in polynomial time. To the best of the authors' knowledge, this is the first polynomial-time solvable case for finding diverse solutions of unbounded size.

Abstract Distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound of $${\tilde{\Omega }}(\sqrt{n} + D)$$ Ω ~ ( n + D ) rounds for several global problems, where n denotes the number of nodes and D the diameter of the input graph. Because such a lower bound is derived from special “hard-core” instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept of low-congestion shortcuts was initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. In particular, given a graph class $${\mathcal {C}}$$ C , an f-round algorithm for constructing shortcuts of quality q for any instance in $${\mathcal {C}}$$ C results in $${\tilde{O}}(q + f)$$ O ~ ( q + f ) -round algorithms for solving several fundamental graph problems such as minimum spanning tree and minimum cut, for $${\mathcal {C}}$$ C . The main interest on this line is to identify the graph classes allowing the shortcuts that are efficient in the sense of breaking $${\tilde{O}}(\sqrt{n}+D)$$ O ~ ( n + D ) -round general lower bounds. In this study, we consider the relationship between the quality of low-congestion shortcuts and the following four major graph parameters: doubling dimension, chordality, diameter, and clique-width. The key ingredient of the upper-bound side is a novel shortcut construction technique known as short-hop extension, which might be of independent interest.

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status deteriorate from fixed-parameter tractable to intractable? This type of question is by now very well-studied, but, somewhat strikingly, the algorithmic frontier between the two (arguably) most central width notions, treewidth and pathwidth, is still not understood: currently, no natural graph problem is known to be W-hard for one but FPT for the other. Indeed, a surprising development of the last few years has been the observation that for many of the most paradigmatic problems, their complexities for the two parameters actually coincide exactly, despite the fact that treewidth is a much more general parameter. It would thus appear that the extra generality of treewidth over pathwidth often comes "for free". Our main contribution in this paper is to uncover the first natural example where this generality comes with a high price. We consider Grundy Coloring, a variation of coloring where one seeks to calculate the worst possible coloring that could be assigned to a graph by a greedy First-Fit algorithm. We show that this well-studied problem is FPT parameterized by pathwidth; however, it becomes significantly harder (W[1]-hard) when parameterized by treewidth. Furthermore, we show that Grundy Coloring makes a second complexity jump for more general widths, as it becomes para-NP-hard for clique-width. Hence, Grundy Coloring nicely captures the complexity trade-offs between the three most well-studied parameters. Completing the picture, we show that Grundy Coloring is FPT parameterized by modular-width.

The lexicographic depth-first search (Lex-DFS) is one of the first basic graph problems studied in the context of space-efficient algorithms. It is shown independently by Asano et al. [ISAAC 2014] and Elmasry et al. [STACS 2015] that Lex-DFS admits polynomial-time algorithms that run with O(n)-bit working memory, where n is the number of vertices in the graph. Lex-DFS is known to be P-complete under logspace reduction, and giving or ruling out polynomial-time sublinear-space algorithms for Lex-DFS on general graphs is quite challenging. In this paper, we study Lex-DFS on graphs of bounded treewidth. We first show that given a tree decomposition of width O(n^(1-ε)) with ε > 0, Lex-DFS can be solved in sublinear space. We then complement this result by presenting a space-efficient algorithm that can compute, for w ≤ √n, a tree decomposition of width O(w √nlog n) or correctly decide that the graph has a treewidth more than w. This algorithm itself would be of independent interest as the first space-efficient algorithm for computing a tree decomposition of moderate (small but non-constant) width. By combining these results, we can show in particular that graphs of treewidth O(n^(1/2 - ε)) for some ε > 0 admits a polynomial-time sublinear-space algorithm for Lex-DFS. We can also show that planar graphs admit a polynomial-time algorithm with O(n^(1/2+ε))-bit working memory for Lex-DFS.

Graph Burning asks, given a graph G = (V,E) and an integer k, whether there exists (b₀,… ,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 arose by Kare and Reddy [IWOCA 2019] about 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. Although the parameterization by distance to split graphs cannot be handled with the clique-width argument, we show that this is also tractable by a reduction to a generalized problem with a smaller solution size.

A graph is d -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d . d -orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the \(d\) - Orientable Deletion problem: given a graph \(G=(V,E)\) , delete the minimum number of vertices to make G d -orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: We show that the problem is W[2]-hard and \(\log n\) -inapproximable with respect to k , the number of deleted vertices. This closes the gap in the problem’s approximability. We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by \(d+k\) , but W[1]-hard by d and W[2]-hard by k alone. We show that, under the SETH, for all \(d,\epsilon\) , the problem does not admit a \(O^*((d+2-\epsilon )^{\text {tw}})\) -time algorithm where \(\text {tw}\) is the graph’s treewidth, resolving as a special case an open problem on the complexity of PseudoForest Deletion . We show that the problem is W[1]-hard parameterized by the input graph’s clique-width. Complementing this, we provide an algorithm running in time \(O^*(d^{O(d\cdot \text {cw})})\) , showing that the problem is FPT by \(d+\text {cw}\) , and improving the previously best known algorithm for this case.

Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in \(O\left (n \log n\right )\) time and space. Our goal in this paper is to reduce the space consumption while keeping the time complexity small. For \(\sqrt {n} \le s \le n\) , we present algorithms that use \(O\left (s \log n\right )\) bits and \(O\left (\frac {1}{s} \cdot n^{2} \cdot \log n\right )\) time for computing the length of a longest increasing subsequence, and \(O\left (\frac {1}{s} \cdot n^{2} \cdot \log ^{2} n\right )\) time for finding an actual subsequence. We also show that the time complexity of our algorithms is optimal up to polylogarithmic factors in the framework of sequential access algorithms with the prescribed amount of space.

We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the c-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set c-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed c >= 1 on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time (n^{O(c)}) algorithm for all fixed values of c, except c=1, for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that c-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by c and the length of the solution, as well as a tight ETH-based lower bound for both parameters.

Algorithmic meta-theorems, stating that graph properties expressible in some particular logic can be decided efficiently in graph classes having some specific structural properties, are now standard in sequential graph algorithms. One of the most classic examples is Courcelle's theorem: all properties expressible in Monadic Second-Order logic (MSO) are decidable in linear time in graphs of bounded treewidth. We provide here a distributed version of Courcelle's theorem, in the standard CONGEST model for distributed computing: For any MSO formula $φ$ and any constant $k$, there is a CONGEST algorithm that, given an input communication network $G$ of treewidth at most $k$ and of diameter $D$, decides if $G$ satisfies property $φ$ in $\tilde O(D)$ rounds. Simple examples show that the dependency on $D$ is unavoidable. Also, if we drop the assumption of bounded treewidth, deciding MSO properties such as 3-colorability are known to require $\tildeΩ(n^2)$ rounds in the CONGEST model. Our results extend to optimization problems (e.g., computing a maximum size independent set, or a minimum dominating set) and counting (e.g. triangle counting). As usual, the $\tilde{O}$ notation hides polylogarithmic factors in $n$; here it also hides a constant factor depending on $k$ and on the MSO formula $φ$. We also give a distributed algorithm producing a linear approximation for treewidth: For any $k$, it decides that the treewidth of the input network $G$ is larger than $k$ or computes a tree decomposition of width $O(k)$ and depth $O(\log n)$, in $\tilde O(k^{O(k)} D)$ rounds in CONGEST. Our algorithms make use of the low-congestion shortcuts framework introduced by Ghaffari and Haeupler [SODA 2016], and our main technical tool is an $\tilde O(k^4 D)$ algorithm for computing $(s,t)$-vertex separators of size at most $k+1$ in graphs of treewidth at most $k$.

In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called k-length interval graphs were considered in which the number of different lengths of intervals is limited by k. Even after decades of research, no insight into their structure is known and the complexity of recognition is open even for $$k=2$$ . We propose generalizations of proper interval graphs called k-nested interval graphs in which there are no chains of $$k+1$$ intervals nested in each other. It is easy to see that k-nested interval graphs are a superclass of k-length interval graphs. We give a linear-time recognition algorithm for k-nested interval graphs. This algorithm adds a missing piece to Gajarský et al. [FOCS 2015] to show that testing FO properties on interval graphs is FPT with respect to the nesting k and the length of the formula, while the problem is W[2]-hard when parameterized just by the length of the formula. We show that a generalization of recognition called partial representation extension is NP-hard for k-length interval graphs, even when $$k=2$$ , while Klavík et al. show that it is polynomial-time solvable for k-nested interval graphs.

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3^k n k^{O(1)}) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. [MFCS 2015] who gave a (nonlinear) 7.56^k n^{O(1)}-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.

It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.

The problem MaxW-Light (MaxW-Heavy) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, Max 0-Light is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MaxW-Heavy can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MaxW-Light, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54–87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k . We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d . In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed k ≥8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for k ≤3 the problem becomes polynomially time solvable.