We investigate machine models similar to Turing machines that are augmented with the operations of a first-order structure $\mathcal{R}$, and we show that under weak conditions on $\mathcal{R}$, the complexity class $Σ_k \mathcal{R}$ may be characterized in four equivalent ways: (1) by polynomial-time algorithms implemented on $\mathcal{R}$-machines together with witness strings, (2) by the $Σ_k\mathcal{R}$-complete problem $Σ_k\text{SAT}(\mathcal{R})$, (3) by the $k$th existential fragment of second-order metafinite logic over $\mathcal{R}$ via descriptive complexity, and (4) via oracles. By characterizing $Σ_k\mathcal{R}$ in these four ways, we extend previous work and embed it in one coherent framework. In addition, we derive similar results for $\exists_k \mathcal{R}$, the constant-free Boolean part of $Σ_k\mathcal{R}$, by showing that $\exists_k\mathcal{R}$ may be characterized in four analogous ways. Some conditions on $\mathcal{R}$ must be assumed in order to achieve the above quaternity because there are infinite-vocabulary structures for which $\text{NP}(\mathcal{R}) = Σ_1 \mathcal{R}$ does not have a complete problem. Surprisingly, even in these cases, we show that $\text{NP}(\mathcal{R})$ does have a characterization in terms of existential second-order metafinite logic, suggesting that descriptive complexity theory is well suited to working with infinite-vocabulary structures, such as real vector spaces.

The induced matching width of a tree decomposition of a graph \(G\) is the cardinality of a largest induced matching \(M\) of \(G\), such that there exists a bag that intersects every edge in \(M\). The induced matching treewidth of \(G\), denoted by tree-\(\mu(G)\), is the minimum induced matching width of a tree decomposition of \(G\). The parameter tree-\(\mu\) was introduced by Yolov [SODA ’18], who showed that, for example, Maximum-Weight Independent Set can be solved in polynomial-time on graphs of bounded tree-\(\mu\). Lima, Milanič, Muršič, Okrasa, Rzążewski, and Šorgel [ESA ’24] conjectured that this algorithm can be generalized to a meta-problem called Maximum-Weight Induced Subgraph of Bounded Treewidth, where we are given a vertex-weighted graph \(G\), an integer \(w\), and a \(\mathsf{CMSO_2}\)-sentence \(\Phi\), and are asked to find a maximum-weight set \(X \subseteq V(G)\) so that \(G[X]\) has treewidth at most \(w\) and satisfies \(\Phi\). They proved the conjecture for some special cases, such as for the problem Maximum-Weight Induced Forest.

We study the trade-off between (average) spread and width in tree decompositions, answering several questions from Wood [arXiv:2509.01140]. The spread of a vertex v in a tree decomposition is the number of bags that contain v. Wood asked for which c > 0, there exists c' such that each graph G has a tree decomposition of width ctw(G) in which each vertex v has spread at most c'(d(v)+1). We show that c ≥ 2 is necessary and that c > 3 is sufficient. Moreover, we answer a second question fully by showing that near-optimal average spread can be achieved simultaneously with width O(tw(G)).

Abstract We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show that both problems are XL-complete when there is no limit on the number of moves, XNL-complete when a maximum length $$\ell $$ ℓ for the sequence is given in binary in the input, and XNLP-complete when $$\ell $$ ℓ is given in unary. The problems were known to be $$\textrm{W}[1]$$ W [ 1 ] - and $$\textrm{W}[2]$$ W [ 2 ] -hard respectively when $$\ell $$ ℓ is also a parameter. We complete the picture by showing membership in those classes. Moreover, we show that for all the variants that we consider, token sliding and token jumping are equivalent under pl-reductions. We introduce partitioned variants of token jumping and token sliding, and give pl-reductions between the four variants that have precise control over the number of tokens and the length of the reconfiguration sequence.

The class XNLP consists of (parameterized) problems that can be solved non-deterministically in f ( k ) n O ( 1 ) time and g ( k ) log n space, where n is the size of the input instance and k the parameter. The class XALP consists of problems that can be solved in the above time and space with access to an additional stack. These two classes are a “natural home” for many standard graph problems and their generalizations. In this paper, we show the hardness of several problems on planar graphs, parameterized by outerplanarity, treewidth and pathwidth, thus strengthening several existing results. In particular, we show XALP-completeness of the following problems parameterized by outerplanarity: All-or-Nothing Flow , Target Outdegree Orientation , Capacitated (Red–Blue) Dominating Set , Target Set Selection etc. We also show the XNLP-completeness of Scattered Set parameterized by pathwidth and XALP-completeness parameterized by treewidth and outerplanarity.

In the field of parameterized complexity, we study algorithms for and the complexity of problems where one part of the input is a parameter that is assumed to be small. In this talk, a survey will be given of several central notions from parameterized complexity, and discuss some recent developments, including the classes XNLP and XALP. These topics will be illustrated with examples from results on graph layout and graph drawing.

In this paper, we give new and faster deterministic algorithms to count the number of k-paths and trees in host graphs of bounded treewidth. Our algorithms use time that is single-exponential in the treewidth, and employ the determinant method from [Hans L. Bodlaender et al., 2015]. Modifications of the algorithms count in single-exponential time the number of k-paths between specified end-points, the number of k-cycles, and the number of trees with k vertices that are a subgraph of the host graph.

Abstract In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna (ACM Trans Comput Theory 9:1–36, 2018), that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, ( q -)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, Capacitated Vertex Cover and Bipartite Bandwidth.

We study Steiner Forest on H -subgraph-free graphs, that is, graphs that do not contain some fixed graph H as a (not necessarily induced) subgraph. In contrast to the related Steiner Tree problem, Steiner Forest falls outside a recent framework that completely characterizes the complexity of many problems on H -subgraph-free graphs. Hence, the complexity of Steiner Forest on H -subgraph-free graphs remained open. Our main results are four polynomial-time algorithms for different excluded graphs H that are central to further understand its complexity. We also study the complexity of Steiner Forest for graphs with a small c -deletion set, that is, a small set X of vertices such that each connected component of G − X has size at most c . For this parameter, we give two algorithms that we later employ as subroutines (including a faster algorithm when c = 1 , that is, the vertex cover number) and exhibit a dichotomy theorem.

Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log⁡(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloring and Precoloring Extension with pathwidth as parameter, Scheduling of Jobs with Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidth and variants of Weighted CNF-Satisfiability. In particular, this implies that all these problems are W[t]-hard for all t.

We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: i) Binary CSP parameterized by the vertex cover number is $\mathrm{W}[3]$-complete. More generally, for every positive integer $d$, Binary CSP parameterized by the size of a modulator to a treedepth-d graph is $\mathrm{W}[2d+1]$-complete. This provides a new family of natural problems that are complete for odd levels of the W-hierarchy. ii) We introduce a new complexity class XSLP, defined so that Binary CSP parameterized by treedepth is complete for this class. We provide two equivalent characterizations of XSLP: the first one relates XSLP to a model of an alternating Turing machine with certain restrictions on conondeterminism and space complexity, while the second one links XSLP to the problem of model-checking first-order logic with suitably restricted universal quantification. Interestingly, the proof of the machine characterization of XSLP uses the concept of universal trees, which are prominently featured in the recent work on parity games iii) We describe a new complexity hierarchy sandwiched between the W-hierarchy and the A-hierarchy: For every odd $t$, we introduce a parameterized complexity class $\mathrm{S}[t]$ with $\mathrm{W}[t]\subseteq \mathrm{S}[t]\subseteq \mathrm{A}[t]$, defined using a parameter that interpolates between the vertex cover number and the treedepth. We expect that many of the studied classes will be useful in the future for pinpointing the complexity of various structural parameterizations of graph problems.

In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.

The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Path problem, have been considered. Therefore, we investigate the parameterised complexity of the general Integer Multicommodity Flow problem. We show that the decision version of this problem on directed graphs for a constant number of commodities, when the capacities are given in unary, is XNLP-complete with pathwidth as parameter and XALP-complete with treewidth as parameter. When the capacities are given in binary, the problem is NP-complete even for graphs of pathwidth at most 13. We give related results for undirected graphs. These results imply that the problem is unlikely to be fixed-parameter tractable by these parameters. In contrast, we show that the problem does become fixed-parameter tractable when weighted tree partition width (a variant of tree partition width for edge weighted graphs) is used as parameter.

Abstract In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized algorithms for treewidth and pathwidth. The lemma addresses a runtime bottleneck in those algorithms but so far it does not lead to asymptotically faster algorithms. However, we apply the lemma to show that the cutwidth and the modified cutwidth of series parallel digraphs can be computed in polynomial time.

Abstract. We study exact algorithms for Metric TSP in [Formula: see text]. In the early 1990s, algorithms with [Formula: see text] running time were presented for the planar case, and some years later an algorithm with [Formula: see text] running time was presented for any [Formula: see text]. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Metric TSP, except for a lower bound stating that the problem admits no [Formula: see text] algorithm unless ETH fails. In this paper we settle the complexity of Metric TSP, up to constant factors in the exponent and under ETH, by giving an algorithm with running time [Formula: see text].

We show that List Colouring can be solved on $n$-vertex trees by a deterministic Turing machine using $O(\log n)$ bits on the worktape. Given an $n$-vertex graph $G=(V,E)$ and a list $L(v)\subseteq\{1,\dots,n\}$ of available colours for each $v\in V$, a list colouring for $G$ is a proper colouring $c$ such that $c(v)\in L(v)$ for all $v$.

We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an $n$-vertex graph $G$ and an integer $k$, constructs a tree-partition of width $O(k^7)$ for $G$ or reports that $G$ has tree-partition-width more than $k$, in time $k^{O(1)}n^2$. We can improve slightly on the approximation factor by sacrificing the dependence on $k$, or on $n$. On the other hand, we show the problem of computing tree-partition-width exactly is XALP-complete, which implies that it is $W[t]$-hard for all $t$. We deduce XALP-completeness of the problem of computing the domino treewidth. Next, we adapt some known results on the parameter tree-partition-width and the topological minor relation, and use them to compare tree-partition-width to tree-cut width. Finally, for the related parameter weighted tree-partition-width, we give a similar approximation algorithm (with ratio now $O(k^{15})$) and show XALP-completeness for the special case where vertices and edges have weight 1.

In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, (q-)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.

In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in $f(k)n^{O(1)}$ time and $f(k)\log n$ space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on `tree-structured graphs' are complete for this class: we show that List Colouring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by $\log n$, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a `natural home' for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most $f(k)n^{O(1)}$ and use $f(k)\log n$ space. Moreover, we introduce `tree-shaped' variants of Weighted CNF-Satisfiability and Multicolour Clique that are XALP-complete.

Let XNLP be the class of parameterized prob-lems such that an instance of size$n$with parameter$k$can be solved nondeterministically in time$f$($k$) nO(1)and space f (k) log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[$t$]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.

Abstract Divisorial gonality and stable divisorial gonality are graph parameters, which have an origin in algebraic geometry. Divisorial gonality of a connected graph G can be defined with help of a chip firing game on G. The stable divisorial gonality of G is the minimum divisorial gonality over all subdivisions of edges of G. In this paper we prove that deciding whether a given connected graph has stable divisorial gonality at most a given integer k belongs to the class NP. Combined with the result that (stable) divisorial gonality is NP-hard by Gijswijt et al., we obtain that stable divisorial gonality is NP-complete. The proof consists of a partial certificate that can be verified by solving an Integer Linear Programming instance. As a corollary, we have that the total number of subdivisions needed for minimum stable divisorial gonality of a graph with m edges is bounded by mO(mn).

Abstract In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.

In this paper, we consider the parameterized complexity of the following scheduling problem. We must schedule a number of jobs on $m$ machines, where each job has unit length, and the graph of precedence constraints consists of a set of chains. Each precedence constraint is labelled with an integer that denotes the exact (or minimum) delay between the jobs. We study different cases; delays can be given in unary and in binary, and the case that we have a single machine is discussed separately. We consider the complexity of this problem parameterized by the number of chains, and by the thickness of the instance, which is the maximum number of chains whose intervals between release date and deadline overlap. We show that this scheduling problem with exact delays in unary is $W[t]$-hard for all $t$, when parameterized by the thickness, even when we have a single machine ($m = 1$). When parameterized by the number of chains, this problem is $W[1]$-complete when we have a single or a constant number of machines, and $W[2]$-complete when the number of machines is a variable. The problem with minimum delays, given in unary, parameterized by the number of chains (and as a simple corollary, also when parameterized by the thickness) is $W[1]$-hard for a single or a constant number of machines, and $W[2]$-hard when the number of machines is variable. With a dynamic programming algorithm, one can show membership in XP for exact and minimum delays in unary, for any number of machines, when parameterized by thickness or number of chains. For a single machine, with exact delays in binary, parameterized by the number of chains, membership in XP can be shown with branching and solving a system of difference constraints. For all other cases for delays in binary, membership in XP is open.

We give an algorithmic and lower bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to intersection graphs of similarly-sized fat objects, yielding algorithms with running time $2^{O(n^{1-1/d})}$ for any fixed dimension $d\ge 2$ for many well-known graph problems, including Independent Set, $r$-Dominating Set for constant $r$, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms are representation-agnostic, i.e., they work on the graph itself and do not require the geometric representation. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into $d$-dimensional grids, and it allows us to derive matching $2^{\Omega(n^{1-1/d})}$ lower bounds under the exponential time hypothesis even in the much more restricted class of $d$-dimensional induced grid graphs.

Based on analogies between algebraic curves and graphs, Baker and Norine introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. Various equivalent definitions of the gonality of an algebraic curve translate to different notions of gonality for graphs, called stable gonality and stable divisorial gonality. We consider so-called hyperelliptic graphs (multigraphs of gonality 2, in any meaning of graph gonality) and provide a safe and complete set of reduction rules for such multigraphs. This results in an algorithm to recognize hyperelliptic graphs in time O(m+nlog⁡n), where n is the number of vertices and m the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph G admits an involution σ such that the quotient G/〈σ〉 is a tree.

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

Let P be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let $$s\in P$$ be a given source node. Each node p can transmit information to all other nodes within unit distance, provided p is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source s can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem (in the latter, s must be able to reach every node within a specified number of hops), with the restriction that all points lie inside a strip of width w. We describe several algorithms for both the regular and the hop-bounded versions, and show that both problems are solvable in polynomial time in strips of small constant width. These results complement the hardness results in a companion paper (de Berg et al. in Algorithmica, 2017).

Let P be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let $$s\in P$$ be a given source node. Each node p can transmit information to all other nodes within unit distance, provided p is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source s can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem—in the latter s must be able to reach every node within a specified number of hops—where we also consider how the complexity depends on the width w of the strip. We prove the following two lower bounds. First, we show that the regular version of the problem is $${\mathsf {W[1]}}$$ -complete when parameterized by the solution size k. More precisely, we show that the problem does not admit an algorithm with running time $$f(k)n^{o(\sqrt{k})}$$ , unless ETH fails. The construction can also be used to show an $$f(w)n^{\varOmega (w)}$$ lower bound when we parameterize by the strip width w. Second, we prove that the hop-bounded version of the problem is NP-hard in strips of width 40. These results complement the algorithmic results in a companion paper (de Berg et al. in Algorithmica, submitted).

We study exact algorithms for Euclidean TSP in Rd. In the early 1990s algorithms with nO(√n)running time were presented for the planar case, and some years later an algorithm with nO(n1-1/d)running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2O(n1-1/d-ε) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2O(n1-1/d)algorithm and by showing that a 2o(n1-1/d)algorithm does not exist unless ETH fails.

We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2O(n1−1/d) for any fixed dimension d≥ 2 for many well known graph problems, including Independent Set, r-Dominating Set for constant r, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms work on the graph itself, i.e., do not require any geometric information. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques.

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.

We present a parallel algorithm for computing the treewidth of a graph on a GPU. We implement this algorithm in OpenCL, and experimentally evaluate its performance. Our algorithm is based on an O*(2^n)-time algorithm that explores the elimination orderings of the graph using a Held-Karp like dynamic programming approach. We use Bloom filters to detect duplicate solutions. GPU programming presents unique challenges and constraints, such as constraints on the use of memory and the need to limit branch divergence. We experiment with various optimizations to see if it is possible to work around these issues. We achieve a very large speed up (up to 77x) compared to running the same algorithm on the CPU.

We establish the complexity of several graph embedding problems: Subgraph Isomorphism, Graph Minor, Induced Subgraph and Induced Minor, when restricted to H-minor free graphs. In each of these problems, we are given a pattern graph P and a host graph G, and want to determine whether P is a subgraph (minor, induced subgraph or induced minor) of G. We show that, for any fixed graph H and epsilon > 0, if P is H-Minor Free and G has treewidth tw, (induced) subgraph can be solved 2^{O(k^{epsilon}*tw+k/log(k))}*n^{O(1)} time and (induced) minor can be solved in 2^{O(k^{epsilon}*tw+tw*log(tw)+k/log(k))}*n^{O(1)} time, where k = |V(P)|. We also show that this is optimal, in the sense that the existence of an algorithm for one of these problems running in 2^{o(n/log(n))} time would contradict the Exponential Time Hypothesis. This solves an open problem on the complexity of Subgraph Isomorphism for planar graphs. The key algorithmic insight is that dynamic programming approaches can be sped up by identifying isomorphic connected components in the pattern graph. This technique seems widely applicable, and it appears that there is a relatively unexplored class of problems that share a similar upper and lower bound.

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.

Recently, new techniques have been introduced to speed up dynamic programming algorithms on tree decompositions for connectivity problems: the 'Cut and Count' method and a method called the rank-based approach, based on representative sets and Gaussian elimination. These methods respectively give randomised and deterministic algorithms that are single exponential in the treewidth, and polynomial, respectively linear in the number of vertices. In this paper, we adapt these methods to branch decompositions yielding algorithms, both randomised and deterministic, that are in many cases faster than when tree decompositions would be used. In particular, we obtain the currently fastest randomised algorithms for several problems on planar graphs. When the involved weights are O(n^{O(1)}), we obtain faster randomised algorithms on planar graphs for Steiner Tree, Connected Dominating Set, Feedback Vertex Set and TSP, and a faster deterministic algorithm for TSP. When considering planar graphs with arbitrary real weights, we obtain faster deterministic algorithms for all four mentioned problems.

In a parameterized problem, every instance I comes with a positive integer k . The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of the instance I to a polynomial in k while preserving the answer. In this work, we give two meta-theorems on kernelization. The first theorem says that all problems expressible in counting monadic second-order logic and satisfying a coverability property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker coverability property admit a linear kernel on graphs of bounded genus. These theorems unify and extend all previously known kernelization results for planar graph problems.

In the Intervalizing Coloured Graphs problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses $2^{\mathcal {O}(n/\log n)}$ time. We also give an $\mathcal {O}^{\ast }(2^{n})$ algorithm for the case that the number of colors is not fixed.

We give an algorithm that for an input $n$-vertex graph $G$ and integer $k>0$, in time $2^{O(k)} n$, either outputs that the treewidth of $G$ is larger than $k$, or gives a tree decomposition of $G$ of width at most $5k+4$. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single exponential in $k$ and linear in $n$. Treewidth-based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single exponential in the treewidth and linear in the input size.

In this paper, we give a number of new exact algorithms and heuristics to compute linear boolean decompositions, and experimentally evaluate these algorithms. The experimental evaluation shows that significant improvements can be made with respect to running time without increasing the width of the generated decompositions. We also evaluated dynamic programming algorithms on linear boolean decompositions for several vertex subset problems. This evaluation shows that such algorithms are often much faster (up to several orders of magnitude) compared to theoretical worst case bounds.

One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in linear time for graphs of bounded treewidth, which is known as Courcelle's Theorem. These algorithms are constructed as finite state tree automata, and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e., every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. We prove this conjecture for k-outerplanar graphs, which are known to have treewidth at most 3k-1.

Many real-world Bayesian networks are expected to exhibit commonly known properties of monotonicity. Since monotonicity violations may be introduced despite careful engineering efforts, these properties need be verified before using a network in practice. We will show that the problem of verifying monotonicity in general has a prohibitively high computational complexity. We will argue however, that the runtime complexity involved can be substantially reduced by using a tailored algorithm which we coined provisional propagation. By means of this algorithm in fact, verifying monotonicity may become feasible for a range of real-world networks.

We introduce the framework of cross-composition for proving kernelization lower bounds. A classical problem $L$ \and/or-cross-composes into a parameterized problem $\mathcal{Q}$ if it is possible to efficiently construct an instance of $\mathcal{Q}$ with polynomially bounded parameter value that expresses the logical and or or of a sequence of instances of $L$. Building on work by Bodlaender et al. and using results of Fortnow and Santhanam, Dell and van Melkebeek, and Drucker, we show that if an NP-hard problem and/or-cross-composes into a parameterized problem $\mathcal{Q}$, then $\mathcal{Q}$ does not admit a polynomial kernel unless $\mbox{NP}\subseteq \mbox{coNP/poly}$ and the polynomial hierarchy collapses. Our technique generalizes and strengthens the techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (nonstandard) parameterizations, e.g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. We have similar lower bounds for Feedback Vertex Set and Odd Cycle Transversal under structural parameterizations. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of or-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size.

We give an algorithm that for an input n-vertex graph G and integer k > 0, in time O(ckn) either outputs that the tree width of G is larger than k, or gives a tree decomposition of G of width at most 5k + 4. This is the first algorithm providing a constant factor approximation for tree width which runs in time single-exponential in k and linear in n. Tree width based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the tree width and linear in the input size.

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G′,k′) in polynomial time with the guarantee that G′ has at most 2k′ vertices (and thus $\mathcal{O}((k')^{2})$ edges) with k′≤k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Θ(k 2) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number $\mathop{\mathrm{\mbox {\textsc{vc}}}}(G)$ since $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)\leq\mathop{\mathrm{\mbox{\textsc{vc}}}}(G)$ and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ : an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G′,X′,k′) such that |V(G′)|≤2k and $|V(G')| \in\mathcal{O}(|X'|^{3})$ . A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have a polynomial kernel when parameterized by the cardinality of a given vertex cover of the graph unless NP ⊆ coNP/poly and the polynomial hierarchy collapses to the third level.

We consider the Partition Into Triangles problem on bounded degree graphs. We show that this problem is polynomial-time solvable on graphs of maximum degree three by giving a linear-time algorithm. We also show that this problem becomes $\mathcal{NP}$ -complete on graphs of maximum degree four. Moreover, we show that there is no subexponential-time algorithm for this problem on graphs of maximum degree four unless the Exponential-Time Hypothesis fails. However, the Partition Into Triangles problem on graphs of maximum degree at most four is in many cases practically solvable as we give an algorithm for this problem that runs in $\mathcal{O}(1.02220^{n})$ time and linear space.

The notion of treewidth plays an important role in theoretical and practical studies of graph problems. It has been recognized that, especially in practical environments, when computing the treewidth of a graph it is invaluable to first apply an array of preprocessing rules that simplify and shrink it. This work seeks to prove rigorous performance guarantees for such preprocessing rules---known rules as well as more recent ones---by studying them in the framework of kernelization from parameterized complexity. It is known that the NP-complete problem of determining whether a given graph $G$ has treewidth at most $k$ admits no polynomial-time preprocessing algorithm that reduces any input instance to size polynomial in $k$, unless NP $\subseteq$ coNP/poly and the polynomial hierarchy collapses to its third level. In this paper we therefore consider structural graph measures larger than treewidth, and determine whether efficient preprocessing can shrink the instance size to a polynomial in such a parameter value. We prove that, given an instance $(G,k)$ of treewidth, we can efficiently reduce its size to $\mathcal{O}(\mathrm{\textsc{fvs}}(G)^4)$ vertices, where $\mathrm{\textsc{fvs}}(G)$ is the size of a minimum feedback vertex set in $G$. We can also prove a size reduction to $\mathcal{O}(\mathrm{\textsc{vc}}(G)^3)$ vertices, where $\mathrm{\textsc{vc}}(G)$ is the size of a minimum vertex cover. Phrased in the language of parameterized complexity, we show that Treewidth has a polynomial kernel when parameterized by the size of a given feedback vertex set, and also by the size of a vertex cover. In contrast we show that Treewidth parameterized by the vertex-deletion distance to a single clique and Weighted Treewidth parameterized by the size of a vertex cover do not admit polynomial kernelizations unless NP $\subseteq$ coNP/poly.

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.

An edge dominating set in a graph G=(V,E) is a subset of the edges D⊆E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is NP-hard. We present a faster exact exponential time algorithm for this problem. Our algorithm uses O(1.3226 n ) time and polynomial space. The algorithm combines an enumeration approach of minimal vertex covers in the input graph with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwisely. In each of these refinement steps, the worst cases in the measure and conquer analysis of the current algorithm are reconsidered and a new branching strategy is proposed on one of these worst cases. In this way a series of algorithms appears, each one slightly faster than the previous one, ending in the O(1.3226 n ) time algorithm. For each algorithm in the series, we also give a lower bound on its running time. We also show that the related problems: minimum weight edge dominating set, minimum maximal matching and minimum weight maximal matching can be solved in O(1.3226 n ) time and polynomial space using modifications of the algorithm for edge dominating set. In addition, we consider the matrix dominating set problem which we solve in O(1.3226 n+m ) time and polynomial space for n×m matrices, and the parametrised minimum weight maximal matching problem for which we obtain an O ∗(2.4179 k ) time and space algorithm.

In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply.

We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O *(2 n ). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the Traveling Salesman problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing Treewidth under the restriction that the space used is only polynomial and give a simple O *(4 n ) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, Treewidth can be computed in O *(2.9512 n ) time and polynomial space.

We introduce a new technique for proving kernelization lower bounds, called cross-composition. A classical problem L cross-composes into a parameterized problem $Q$ if an instance of Q with polynomially bounded parameter value can express the logical OR of a sequence of instances of L. Building on work by Bodlaender et al. (ICALP 2008) and using a result by Fortnow and Santhanam (STOC 2008) we show that if an NP-hard problem cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless the polynomial hierarchy collapses. Our technique generalizes and strengthens the recent techniques of using OR-composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (non-standard) parameterizations, e.g., Chromatic Number, Clique, and Weighted Feedback Vertex Set do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. We have similar lower bounds for Feedback Vertex Set.

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G',k') in polynomial time with the guarantee that G' has at most 2k' vertices (and thus O((k')^2) edges) with k' <= k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Theta(k^2) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size fvs(G) of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number vc(G) since fvs(G) <= vc(G) and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in fvs(G): an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G',X',k') such that |V(G')| <= 2k and |V(G')| <= O(|X'|^3). A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have a polynomial kernel when parameterized by the cardinality of a given vertex cover of the graph unless NP is in coNP/poly and the polynomial hierarchy collapses to the third level.

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) k n 4). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k 2).

To control possible spills in liquid or gas transporting pipe systems, the systems are usually equipped with shutoff valves. In case of an accidental leak, these valves separate the system into a number of pieces, limiting the spill effect. In this paper, we consider the problem, for a given edge-weighted network representing a pipe system and for a given number of valves, of placing the valves in the network in such a way that the maximum possible spill, i.e., the maximum total weight of a piece, is minimized. We show that the problem is NP-hard even if restricted to any of the following settings: (i) series-parallel graphs, and hence graphs of treewidth two; and (ii) all edge weights equal one. If the network is a simple path, a cycle, or a tree, the problem can be solved in polynomial time. We also give a pseudopolynomial-time algorithm and a fully polynomial-time approximation scheme for networks of bounded treewidth.

The Feedback Vertex Set problem on unweighted, undirected graphs is considered. Improving upon a result by Burrage et al. (Proceedings 2nd International Workshop on Parameterized and Exact Computation, pp. 192–202, 2006), we show that this problem has a kernel with O(k 3) vertices, i.e., there is a polynomial time algorithm, that given a graph G and an integer k, finds a graph G′ with O(k 3) vertices and integer k′≤k, such that G has a feedback vertex set of size at most k, if and only if G′ has a feedback vertex set of size at most k′. Moreover, the algorithm can be made constructive: if the reduced instance G′ has a feedback vertex set of size k′, then we can easily transform a minimum size feedback vertex set of G′ into a minimum size feedback vertex set of G. This kernelization algorithm can be used as the first step of an FPT algorithm for Feedback Vertex Set, but also as a preprocessing heuristic for Feedback Vertex Set.We also show that the related Loop Cutset problem also has a kernel of cubic size. The kernelization algorithms are experimentally evaluated, and we report on these experiments.

Polynomial time preprocessing to reduce instance size is one of the most commonly deployed heuristics to tackle computationally hard problems. In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, we can reduce the size of the instance I to a polynomial in k, while preserving the answer. In this paper, we show that all problems expressible in Counting Monadic Second Order Logic and satisfying a compactness property admit a polynomial kernel on graphs of bounded genus. Our second result is that all problems that have finite integer index and satisfy a weaker compactness condition admit a linear kernel on graphs of bounded genus. The study of kernels on planar graphs was initiated by a seminal paper of Alber, Fellows, and Niedermeier [J. ACM, 2004 ] who showed that Planar Dominating Set admits a linear kernel. Following this result, a multitude of problems have been shown to admit linear kernels on planar graphs by combining the ideas of Alber et al. with problem specific reduction rules. Our theorems unify and extend all previously known kernelization results for planar graph problems. Combining our theorems with the Erdos-Posa property we obtain various new results on linear kernels for a number of packing and covering problems.

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems, like Dominating Set and Independent Set. In this paper, we propose to use measure and conquer also as a tool in the design of algorithms. In an iterative process, we can obtain a series of branch and reduce algorithms. A mathematical analysis of an algorithm in the series with measure and conquer results in a quasiconvex programming problem. The solution by computer to this problem not only gives a bound on the running time, but also can give a new reduction rule, thus giving a new, possibly faster algorithm. This makes design by measure and conquer a form of computer aided algorithm design. When we apply the methodology to a Set Cover modelling of the Dominating Set problem, we obtain the currently fastest known exact algorithms for Dominating Set: an algorithm that uses $O(1.5134^n)$ time and polynomial space, and an algorithm that uses $O(1.5063^n)$ time.

In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph G is the maximum order of a bramble of G minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms often give excellent lower bounds, in particular when applied to (close to) planar graphs.

There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems, this is a useful approach for obtaining fixed-parameter tractable algorithms. Starting from trees and series-parallel graphs, we introduce the concepts of treewidth and tree decompositions, and illustrate the technique with the Weighted Independent Set problem as an example. The paper surveys some of the latest developments, putting an emphasis on applicability, on algorithms that exploit tree decompositions, and on algorithms that determine or approximate treewidth and find tree decompositions with optimal or close to optimal treewidth. Directions for further research and suggestions for further reading are also given.

Several sets of reductions rules are known for preprocessing a graph when computing its treewidth. In this paper we give reduction rules for a weighted variant of treewidth, motivated by the analysis of algorithms for probabilistic networks. We present two general reduction rules that are safe for weighted treewidth. They generalise many of the existing reduction rules for treewidth. Experimental results show that these reduction rules can significantly reduce the problem size for several instances of real-life probabilistic networks.

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give an subexponential time exact algorithm. For the special case of k-outerplanar graphs the running time becomes O(n3). We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.

It is shown that the problem of maintaining the topological order of the nodes of a directed acyclic graph while inserting m edges can be solved in O (min{ m 3/2 log n , m 3/2 + n 2 log n }) time, an improvement over the best known result of O ( mn ). In addition, we analyze the complexity of the same algorithm with respect to the treewidth k of the underlying undirected graph. We show that the algorithm runs in time O ( mk log 2 n ) for general k and that it can be implemented to run in O ( n log n ) time on trees, which is optimal. The algorithm also detects cycles in the input.

Currently, the most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a maximum clique size as small as possible. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.

A λ-coloring of a graph G is an assignment of colors from the integer set {0,…,λ} to the vertices of the graph G such that vertices at distance of at most two get different colors and adjacent vertices get colors which are at least two apart. The problem of finding λ-colorings with optimal or near-optimal λ arises in the context of radio frequency assignment. We show that the problem of finding the minimum λ for planar graphs, bipartite graphs, chordal graphs and split graphs is NP-complete. We also give approximation algorithms for λ-coloring and compute upper bounds on the best possible λ for outerplanar graphs, graphs of treewidth k, permutation and split graphs. Except in the case of split graphs, all the above bounds for λ are linear in Δ, the maximum degree of the graph. For split graphs, we give a bound of ½Δ1.5 + 2Δ and we show that there are split graphs G with λ(G) = Ω(Δ1.5). Similar results are also given for variations of the λ-coloring problem.

We describe the first parallel algorithm with optimal speedup for constructing minimum-width tree decompositions of graphs of bounded treewidth. On n-vertex input graphs, the algorithm works in O((log n) 2 ) time using O(n) operations on the EREW PRAM. We also give faster parallel algorithms with optimal speedup for the problem of deciding whether the treewidth of an input graph is bounded by a given constant and for a variety of problems on graphs of bounded treewidth, including all decision problems expressible in monadic second-order logic. On n-vertex input graphs, the algorithms use O(n) operations together with O(log n log * n) time on the EREW PRAM, or O(log n) time on the CRCW PRAM.

A vertex (edge) coloring $\phi:V\rightarrow \{1,2,\ldots ,t\}$ ($\phi':E\rightarrow \{1,2,\ldots,$ $t\}$) of a graph G=(V,E) is a vertex (edge) t-ranking if, for any two vertices (edges) of the same color, every path between them contains a vertex (edge) of larger color. The {\em vertex ranking number} $\chi_{r}(G)$ ({\em edge ranking number} $\chi_{r}'(G)$) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the {\sc Vertex Ranking} and {\sc Edge Ranking} problems. It is shown that $\chi_{r}(G)$ can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize the graphs where the vertex ranking number $\chi_{r}$ and the chromatic number $\chi$ coincide on all induced subgraphs, show that $\chi_{r}(G)=\chi (G)$ implies $\chi (G)=\omega (G)$ (largest clique size), and give a formula for $\chi_{r}'(K_n)$.

In this paper, we give for constant k a linear-time algorithm that, given a graph $G = (V,E)$, determines whether the treewidth of G is at most k and, if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at most some constant k.

Many computational problems in biology involve parameters for which a small range of values cover important applications. We argue that for many problems in this setting, parameterized computational complexity rather than NP-completeness is the appropriate tool for studying apparent intractability. At issue in the theory of parameterized complexity is whether a problem can be solved in time O(n alpha) for each fixed parameter value, where alpha is a constant independent of the parameter. In addition to surveying this complexity framework, we describe a new result for the Longest Common Subsequence problem. In particular, we show that the problem is hard for W[t] for all t when parameterized by the number of strings and the size of the alphabet. Lower bounds on the complexity of this basic combinatorial problem imply lower bounds on more general sequence alignment and consensus discovery problems. We also describe a number of open problems pertaining to the parameterized complexity of problems in computational biology where small parameter values are important.

In this paper, we show that the treewidth and pathwidth of a permutation graph can be computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and pathwidth are equal. These results make permutation graphs one of the few nontrivial graph classes for which, at the moment, treewidth is known to be computable in polynomial time. Our algorithm, which decides whether the treewidth (pathwidth) is at most some given integer k, can be implemented to run in $O( nk )$ time when the matching diagram is given. We show that this algorithm can easily be adapted to compute the pathwidth of a permutation graph in $O( nk )$ time, where k is the pathwidth.

The parameterized computational complexity of a collection of well-known problems including: BAND-WIDTH, PRECEDENCE CONSTRAINED MULTIPROCES-SOR SCHEDULING, LONGEST COMMON SUBSEQUENCE, DNA PHYSICAL MAPPING (or INTERNALIZING COL-ORED GRAPHS), PERFECT PHYLOGENY (or TRIANGU-LATING COLORED GRAPHS), COLORED CUTWIDTH, and FEASIBLE REGISTER ASSIGNMENT is explored.It is shown that these problems are hard for various levels of the W hierarchy.In the case of PRECEDENCE CONSTRAINED MULTIPROCESSOR SCHEDULING the results can be interpreted as providing substantial new complexity lower bounds on the outcome of [OPEN 8] of the Garey and Johnson list.

In this paper, we give, for constant k, a linear time algorithm, that given a graph G = (V, E), determines whether the treewidth of G is at most k, and if so, finds a treedecomposition of G with treewidth at most k.A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear time recognition algorithm.

It is shown that the pathwidth of a cograph equals its treewidth, and a linear time algorithm to determine the pathwidth of a cograph and build a corresponding path-decomposition is given.

The authors define a class of languages (called rectilinear) to describe coloured digitized maps and classify them on the basis of their level of succinct representation. The map compression problem is defined as the problem of finding for any given map a shortest description within a given language. For one dimensional maps, that a shortest description can be generated quickly for some languages, but for other languages the problem is NP-hard. A large number of linear time algorithms generate map descriptions whose length is at most twice the minimum.>