A Fixed-Parameter Approach to 2-Layer Planarization

A bipartite graph is biplanar if the vertices can be placed on two parallel lines (layers) in the plane such that there are no edge crossings when edges are drawn as line segments between the layers. In this paper we study the 2-Layer Planarization problem: Can k edges be deleted from a given graph G so that the remaining graph is biplanar? This problem is NP-complete, and remains so if the permutation of the vertices in one layer is fixed (the 1-Layer Planarization problem). We prove that these problems are fixed-parameter tractable by giving linear-time algorithms for their solution (for fixed k). In particular, we solve the 2-Layer Planarization problem in O(k · 6^k + |G|) time and the 1-Layer Planarization problem in O(3^k · |G|) time. We also show that there are polynomial-time constant-approximation algorithms for both problems.     

Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems

CLOSEST STRING is one of the core problems in the field of consensus word analysis with particular importance for computational biology. Given k strings of the same length and a nonnegative integer d , find a ``center string' s such that none of the given strings has the Hamming distance greater than d from s . CLOSEST STRING is NP-complete. In biological applications, however, d is usually very small. We show how to solve CLOSEST STRING in linear time for fixed d —the exponential growth in d is bounded by O(d ^d ) . We extend this result to the closely related problems d -MISMATCH and DISTINGUISHING STRING SELECTION. Moreover, we also show that CLOSEST STRING is solvable in linear time when k is fixed and d is arbitrary. In summary, this means that CLOSEST STRING is fixed-parameter tractable with respect to parameter d and with respect to parameter k . Finally, the practical usefulness of our findings is substantiated by some experimental results.     

Isomorphism for Graphs of Bounded Distance Width

In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth. GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable' polynomial time algorithms can be established. We introduce some new and natural graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve GRAPH ISOMORPHISM in O(n ² ) time for graphs with bounded rooted path distance width, and in O(n ³ ) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(n ^k+1 ) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters. Received February 18, 1997; revised February 23, 1998.     

Parameterized complexity of firefighting

The Firefighter problem is to place firefighters on the vertices of a graph to prevent a fire with known starting point from lighting up the entire graph. In each time step, a firefighter may be placed on an unburned vertex, permanently protecting it, and the fire spreads to all neighboring unprotected vertices of burning vertices. The goal is to let as few vertices burn as possible. In this paper, we consider a generalization of this problem, where at each time step b?1$b?1$ firefighters can be deployed. Our results answer several open questions raised by Cai et al. [8]. We show that this problem is W[1]-hard when parameterized by the number of saved vertices, protected vertices, and burned vertices. We also investigate several combined parameterizations for which the problem is fixed-parameter tractable. Some of our algorithms improve on previously known algorithms. We also establish lower bounds to polynomial kernelization.     

Parameterized algorithm for eternal vertex cover

In this paper we initiate the study of a “dynamic” variant of the classical Vertex Cover problem, the Eternal Vertex Cover problem introduced by Klostermeyer and Mynhardt, from the perspective of parameterized algorithms. This problem consists in placing a minimum number of guards on the vertices of a graph such that these guards can protect the graph from any sequence of attacks on its edges. In response to an attack, each guard is allowed either to stay in his vertex, or to move to a neighboring vertex. However, at least one guard has to fix the attacked edge by moving along it. The other guards may move to reconfigure and prepare for the next attack. Thus at every step the vertices occupied by guards form a vertex cover. We show that the problem admits a kernel of size k⁴(k+1)+2k, which shows that the problem is fixed parameter tractable when parameterized by the number of available guards k. Finally, we also provide an algorithm with running time O(²O(k²)+nm) for Eternal Vertex Cover, where n is the number of vertices and m the number of edges of the input graph. In passing we also observe that Eternal Vertex Cover is NP-hard, yet it has a polynomial time 2-approximation algorithm.     

Graph separators: a parameterized view

Graph separation is a well-known tool to make (hard) graph problems accessible to a divide-and-conquer approach. We show how to use graph separator theorems in combination with (linear) problem kernels in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select&verify graph problems and derive from that a prospective way to easily check whether a planar graph problem will allow for a fixed parameter algorithm of running time for constant c. One of the main contributions of the paper is to exactly compute the base c of the exponential term and its dependence on the various parameters specified by the employed separator theorem and the underlying graph problem. We discuss several strategies to improve on the involved constant c.     

Error Compensation in Leaf Power Problems

The k-Leaf Power recognition problem is a particular case of graph power problems: For a given graph it asks whether there exists an unrooted tree—the k-leaf root—with leaves one-to-one labeled by the graph vertices and where the leaves have distance at most k iff their corresponding vertices in the graph are connected by an edge. Here we study "error correction" versions of k-Leaf Power recognition—that is, adding or deleting at most l edges to generate a graph that has a k-leaf root. We provide several NP-completeness results in this context, and we show that the NP-complete Closest 3-Leaf Power problem (the error correction version of 3-Leaf Power) is fixed-parameter tractable with respect to the number of edge modifications or vertex deletions in the given graph. Thus, we provide the seemingly first nontrivial positive algorithmic results in the field of error compensation for leaf power problems with k > 2. To this end, as a result of independent interest, we develop a forbidden subgraph characterization of graphs with 3-leaf roots.     

Convex recolorings of strings and trees: Definitions, hardness results and algorithms

A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex colorings of trees arise in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree.When a coloring of a tree is not convex, it is desirable to know “how far” it is from a convex one, and what are the convex colorings which are “closest” to it. In this paper we study a natural definition of this distance—the recoloring distance, which is the minimal number of color changes at the vertices needed to make the coloring convex. We show that finding this distance is NP-hard even for a colored string (a path), and for some other interesting variants of the problem. In the positive side, we present algorithms for computing the recoloring distance under some natural generalizations of this concept: the first generalization is the uniform weighted model, where each vertex has a weight which is the cost of changing its color. The other is the non-uniform model, in which the cost of coloring a vertex v by a color d is an arbitrary non-negative number cost(v,d). Our first algorithms find optimal convex recolorings of strings and bounded degree trees under the non-uniform model in time which, for any fixed number of colors, is linear in the input size. Next we improve these algorithm for the uniform model to run in time which is linear in the input size for a fixed number of bad colors, which are colors which violate convexity in some natural sense. Finally, we generalize the above result to hold for trees of unbounded degree.     

Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs

Abstract. We present an algorithm that constructively produces a solution to the k -DOMINATING SET problem for planar graphs in time O(c^ \sqrt k n) , where c=4^ 6\sqrt 34 . To obtain this result, we show that the treewidth of a planar graph with domination number γ (G) is O(\sqrt \rule 0pt 4pt \smash γ (G) ) , and that such a tree decomposition can be found in O(\sqrt \rule 0pt 4pt \smash γ (G) n) time. The same technique can be used to show that the k -FACE COVER problem (find a size k set of faces that cover all vertices of a given plane graph) can be solved in O(c ₁ ^ \sqrt k n) time, where c ₁ =3^ 36\sqrt 34 and k is the size of the face cover set. Similar results can be obtained in the planar case for some variants of k -DOMINATING SET, e.g., k -INDEPENDENT DOMINATING SET and k -WEIGHTED DOMINATING SET.     

Computing small partial coverings

We study the generalization of covering problems such as the set cover problem to partial covering problems. Here we only want to cover a given number k of elements rather than all elements. For instance, in the k-partial (weighted) set cover problem, we wish to compute a minimum weight collection of sets that covers at least k elements. As a main result, we show that the k-partial set cover problem and its special cases like the k-partial vertex cover problem are all fixed parameter tractable (with parameter k). As a second example, we consider the minimum weight k-partial t-restricted cycle cover problem.     

Rotation distance is fixed-parameter tractable

Rotation distance between trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In the case of ordered rooted trees, we show that the rotation distance between two ordered trees is fixed-parameter tractable, in the parameter, k, the rotation distance. The proof relies on the kernelization of the initial trees to trees with size bounded by 5k.     

Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization

We give an O(^k · n²) fixed parameter tractable algorithm for the 1-Sided Crossing Minimization. The constant in the running time is the golden ratio = (1+5)/2 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.     

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K_1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K_i,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph K_i,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of K_i,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K_1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.     

A note on width-parameterized SAT: An exact machine-model characterization

We characterize the complexity of SAT instances with path-decompositions of width w(n). Although pathwidth is the most restrictive among the studied width-parameterizations of SAT, the most time-efficient algorithms known for such SAT instances run in time ²Ω(w(n)), even when the path-decomposition is given in the input. We wish to better understand the decision complexity of SAT instances of width ω(logn). We provide an exact correspondence between SATpw[w(n)], the problem of SAT instances with given path decomposition of width w(n), and NL[r(n)], the class of problems decided by logspace Turing Machines with at most r(n) passes over the nondeterministic tape. In particular, we show that SATpw[w(n)] is hard for under log-space reductions. When is closed under logspace reductions, which is the case for the most interesting w(n)'s, we show that SATpw[w(n)] is also complete.     

Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors

We present a fixed-parameter algorithm that constructively solves the $k$-dominating set problem on any class of graphs excluding a single-crossing graph (a graph that can be drawn in the plane with at most one crossing) as a minor in $O(4^{9.55\sqrt{k}}n^{O(1)})$ time. Examples of such graph classes are the $K_{3,3}$-minor-free graphs and the $K_{5}$-minor-free graphs. As a consequence, we extend our results to several other problems such as vertex cover, edge dominating set, independent set, clique-transversal set, kernels in digraphs, feedback vertex set, and a collection of vertex-removal problems. Our work generalizes and extends the recent results of exponential speedup in designing fixed-parameter algorithms on planar graphs due to Alber et al. to other (nonplanar) classes of graphs.     

Improving a fixed parameter tractability time bound for the shadow problem

Consider a forest of k trees and n nodes together with a (partial) function σ mapping leaves of the trees to non-root nodes of other trees. Define the shadow of a leaf ? to be the subtree rooted at σ(?). The shadow problem asks whether there is a set S of leaves exactly one from each tree such that none of these leaves lies in the shadow of another leaf in S. This graph theoretical problem as shown in Franco et al. (Discrete Appl. Math. 96 (1999) 89) is equivalent to the falsifiability problem for pure implicational Boolean formulas over n variables with k occurences of the constant false as introduced in: Heusch J. Wiedermann, P. Hajek (Eds.), Proceedings of the Twentieth International Symposium on Mathematical Foundations of Computer Science (MFCS’95), Prague, Czech Republic, Lecture Notes in Computer Science, Vol. 969, Springer, Berlin, 1995, pp. 221-226, where its NP-completeness is shown for arbitrary values of k and a time bound of O(n^k) for fixed k was obtained. In Franco et al. (1999) this bound is improved to O(n²k^k) showing the problem's fixed parameter tractability (Congr. Numer. 87 (1992) 161). In this paper the bound O(n³3^k) is achieved by dynamic programming techniques thus significantly improving the fixed parameter part.     

On the parameterized complexity of d-dimensional point set pattern matching

Deciding whether two n-point sets A,B∈Rd are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT.When |A|=m<|B|=n, the problem becomes that of deciding whether A is congruent to a subset of B and is known to be NP-complete. We show that point subset congruence, with d as a parameter, is W[1]-hard, and that it cannot be solved in O(mno(d))-time, unless SNP⊂DTIME(²o(n)). This shows that, unless FPT=W[1], the problem of finding an isometry of A that minimizes its directed Hausdorff distance, or its Earth Mover's Distance, to B, is not in FPT.     

音频水印算法复杂性评估

数字水印技术具有鲁棒性、透明性、复杂性等特性,大部分文献对水印评估的阐述都是集中在鲁棒性上,实际上复杂性评估在数字水印评估领域也是非常重要的.因此,主要是针对数字音频水印算法嵌入函数的复杂性进行评估.给出了基本方案评估的概念,选取了两种典型的音频水印算法,应用此方案评估标准对算法进行评估,并同时论述了应用到基本方案上的嵌入参数和音频检验集.给出了两种算法复杂性评估的结果并将结果进行比较.     

Ising图模型概率推理的参数化复杂性

Ising图模型概率推理的主要工作是通过变量求和来计算配分函数和边缘概率分布。传统计算复杂性理论证明Ising图模型精确概率推理是NP难的,并且Ising图模型近似概率推理是NP难的。研究了Ising图模型精确概率推理和Ising均值场近似概率推理的参数化复杂性。首先证明了不同参数的Ising图模型概率推理的参数化复杂性定理,指出基于变量个数或图模型树宽的参数化概率推理问题是固定参数可处理的。然后证明了Ising均值场的参数化复杂性定理,指出基于自由分布树宽、迭代次数和变量个数的参数化Icing均值场是固定参数可处理的;进一步,当Ising图模型参数满足Ising均值场迭代式压缩条件时,基于自由分布树宽和迭代次数的参数化Ising均值场是固定参数可处理的。