Diameter-the task of computing the length of a longest shortest path-is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no O(n(1.99))-time algorithm even in sparse graphs (Roditt...
详细信息
Diameter-the task of computing the length of a longest shortest path-is a fundamental graph problem. Assuming the Strong Exponential Time Hypothesis, there is no O(n(1.99))-time algorithm even in sparse graphs (Roditty L, Williams, VV in Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the 45th Symposium on Theory of Computing Conference (STOC '13), pp 515-524. ACM, 2013). To circumvent this lower bound, we investigate which parameters allow for running times of the form f (k) (n + m) where k is the respective parameter and f is a computable function. To this end, we systematically explore a hierarchy of structural graph parameters.
Time-evolving or temporal graphs gain more and more popularity when exploring complex networks. In this context, the multistage view on computational problems is among the most natural frameworks. Roughly speaking, he...
详细信息
Time-evolving or temporal graphs gain more and more popularity when exploring complex networks. In this context, the multistage view on computational problems is among the most natural frameworks. Roughly speaking, herein one studies the different (time) layers of a temporal graph (effectively meaning that the edge set may change over time, but the vertex set remains unchanged), and one searches for a solution of a given graph problem for each layer. The twist in the multistage setting is that the solutions found must not differ too much between subsequent layers. We relax on this already established notion by introducing a global instead of the local budget view studied so far. More specifically, we allow for few disruptive changes between subsequent layers but request that overall, that is, summing over all layers, the degree of change is moderate. Studying several classical graph problems (both NP-hard and polynomial-time solvable ones) from a parameterized complexity angle, we encounter both fixed-parameter tractability and parameterized hardness results. Surprisingly, we find that sometimes the global multistage versions of NP-hard problems such as VERTEX COVER turn out to be computationally more tractable than the ones of polynomial-time solvable problems such as MATCHING. In addition to time complexity, we also analyze the space efficiency of our algorithms. (C) 2021 Elsevier B.V. All rights reserved.
The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of...
详细信息
The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration. We provide both positive results (new enumerative kernelizations, "subcubic" parameterized solving algorithms) as well as negative results (presumable uselessness in terms of "faster" parameterized algorithms of certain parameters such as graph diameter). To this end, we introduce new and extend previous concepts. (C) 2019 Elsevier Inc. All rights reserved.
For a string w, a factorisation is any tuple (u(1), u(2), ..., u(k)) of strings that satisfies w = u(1).u(2) ... u(k). A factorisation is called equality-free if each two factors are different, its size is the number ...
详细信息
For a string w, a factorisation is any tuple (u(1), u(2), ..., u(k)) of strings that satisfies w = u(1).u(2) ... u(k). A factorisation is called equality-free if each two factors are different, its size is the number of factors (counting each occurrence of repeating factors) and its width is the maximum length of any factor. To decide, for a string w and a number m, whether w has an equality-free factorisation with a size of at least (or a width of at most) m are NP-complete problems. We further investigate the complexity of these problems and we also study the converse problems of computing a factorisation that is to a large extent not equality-free, i.e., a factorisation of size at least (or width at most) m such that the total number of different factors does not exceed a given bound k. (C) 2016 Elsevier B.V. All rights reserved.
The Closest Substring Problem is to decide, for given strings s(1),...,s(k) of length at most l and numbersm andd, whether there is a length-m string s and length-m substrings s(i)' of s(i), such that s has a Hamm...
详细信息
The Closest Substring Problem is to decide, for given strings s(1),...,s(k) of length at most l and numbersm andd, whether there is a length-m string s and length-m substrings s(i)' of s(i), such that s has a Hamming distance of at most d from each s(i)'. If we instead require the sum of all the Hamming distances between s and each s(i)' to be bounded by d, then it is called the Consensus Patterns Problem. We contribute to the parameterised complexity analysis of these classical NP-hard string problems by investigating the parameter (l - m), i.e., the length difference between input and solution strings. For most combinations of (l - m) and one of the classical parameters (m, l, k, or d), we obtain fixed-parameter tractability. However, even for constant (l - m) and constant alphabet size, both problems remain NP-hard. While this follows from known results with respect to the Closest Substring, we need a new reduction in the case of the Consensus Patterns. As a by-product of this reduction, we obtain an exact exponential-time algorithm for both problems, which is based on an alphabet reduction.
We extend previous studies on "explaining" a nonnegative integer vector by sums of few homogeneous segments, that is, vectors where all nonzero entries are equal and consecutive. We study two NP-complete var...
详细信息
We extend previous studies on "explaining" a nonnegative integer vector by sums of few homogeneous segments, that is, vectors where all nonzero entries are equal and consecutive. We study two NP-complete variants which are motivated by radiation therapy and database applications. In VECTOR POSITIVE EXPLANATION, the segments may have only positive integer entries;in VECTOR EXPLANATION, the segments may have arbitrary integer entries. Considering several natural parameterizations such as the maximum vector entry y and the maximum difference 8 between consecutive vector entries, we obtain a refined picture of the computational (in-)tractability of these problems. For example, we show that VEcrox EXPLANATION is fixed-parameter tractable with respect to delta, and that, unless NP subset of coNP/poly, there is no polynomial kernelization for VECTOR POSITIVE EXPLANATION with respect to the parameter gamma. We also identify relevant special cases where VECTOR POSITIVE EXPLANATION is algorithmically harder than VECTOR EXPLANATION. (C) 2015 Elsevier Inc. All rights reserved.
The NP-hard Interval Constrained Coloring (ICC) problem appears in the interpretation of experimental data in biochemistry dealing with protein fragments. Given a set of m integer intervals in the range 1 to n and a s...
详细信息
The NP-hard Interval Constrained Coloring (ICC) problem appears in the interpretation of experimental data in biochemistry dealing with protein fragments. Given a set of m integer intervals in the range 1 to n and a set of m associated multisets of colors (specifying for each interval the colors to be used for its elements), one asks whether there is a "consistent" coloring for all integer points from {1,..., n} that complies with the constraints specified by the color multisets. We thoroughly analyze a known NP-hardness proof for ICC. In this way, we identify numerous parameters that naturally occur in ICC and strongly influence its practical solvability. Accordingly, we present several positive (fixed-parameter) tractability results exploiting various parameterizations. We substantiate the usefulness of this "multivariate algorithmics approach" by presenting experimental results with real-world data. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论