The class XNLP consists of (parameterized) problems that can be solved nondeterministically 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 consi...
详细信息
ISBN:
(纸本)9783031754081;9783031754098
The class XNLP consists of (parameterized) problems that can be solved nondeterministically 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 XNLP-hardness 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.
A stable cutset in a graph G is a set S subset of V (G) such that vertices of S are pairwise non-adjacent and such that G - S is disconnected, i.e., it is both stable (or independent) set and a cutset (or separator). ...
详细信息
ISBN:
(纸本)9783031754081;9783031754098
A stable cutset in a graph G is a set S subset of V (G) such that vertices of S are pairwise non-adjacent and such that G - S is disconnected, i.e., it is both stable (or independent) set and a cutset (or separator). Unlike general cutsets, it is NP-complete to determine whether a given graph G has any stable cutset. Recently, Rauch et al. [FCT 2023] gave a number of fixed-parameter tractable (FPT) algorithms, time f(k) . vertical bar V(G)vertical bar(c), for STABLE CUTSET under a variety of parameters k such as the size of a (given) dominating set, the size of an odd cycle transversal, or the deletion distance to P-5-free graphs. Earlier works imply FPT algorithms relative to clique-width and relative to solution size. We complement these findings by giving the first results on the existence of polynomial kernelizations for STABLE CUTSET, i.e., efficient pre-processing algorithms that return an equivalent instance of size polynomial in the parameter value. Under the standard assumption that NP not subset of coNP/poly, we show that no polynomial kernelization is possible relative to the deletion distance to a single path, generalizing deletion distance to various graph classes, nor by the size of a (given) dominating set. We also show that under the same assumption no polynomial kernelization is possible relative to solution size, i.e., given (G, k) answering whether there is a stable cutset of size at most k. On the positive side, we show polynomial kernelizations for parameterization by modulators to a single clique, to a cluster or a co-cluster graph, and by twin cover.
Dominating sets in graphs are often used to model monitoring problems, by posting guards on the vertices of the dominating set. If an (unguarded) vertex is attacked, at least one guard can then react by moving there. ...
详细信息
ISBN:
(纸本)9783031754081;9783031754098
Dominating sets in graphs are often used to model monitoring problems, by posting guards on the vertices of the dominating set. If an (unguarded) vertex is attacked, at least one guard can then react by moving there. This yields a new set of guards, which may not be dominating anymore. A dominating set is eternal if one can endlessly resist to attacks. From the attacker's perspective, if we are given a non-eternal dominating set, the question is to determine how fast can we provoke an attack that cannot be handled by a neighboring guard. We investigate this question from a computational complexity point of view, by showing that this question is PSPACE-hard, even for graph classes where finding a minimum eternal dominating set is in P. We then complement this result by giving polynomial time algorithms for cographs and trees, and showing a connection with treedepth for the latter. We also investigate the problem from a parameterized complexity perspective, mainly considering two parameters: the number of guards and the number of steps.
For an introductory single lecture into parameterized complexity classes, it appears to be necessary to introduce different problems to capture the (most important) different levels of the W-hierarchy. This puts an ad...
详细信息
It is entirely interesting, and profoundly important to science, that efforts to communicate science have often led scientists to new perspectives on their own work and their scientific fields and specialties. This tw...
详细信息
Identifying and mitigating the spread of fake information is a challenging issue that has become dominant with the rise of social media. We consider a generalization of the Domination problem that can be used to detec...
详细信息
Probabilistic databases (PDBs) provide users with a principled way to query data that is incomplete or imprecise. In this work, we study computing expected multiplicities of query results over probabilistic databases ...
详细信息
Probabilistic databases (PDBs) provide users with a principled way to query data that is incomplete or imprecise. In this work, we study computing expected multiplicities of query results over probabilistic databases under bag semantics which has PTIME data complexity. However, does this imply that bag probabilistic databases are practical? We strive to answer this question from both a theoretical as well as a systems perspective. We employ concepts from fine-grained complexity to demonstrate that exact bag probabilistic query processing is fundamentally less efficient than deterministic bag query evaluation, but that fast approximations are possible by sampling monomials from a circuit representation of a result tuple's lineage. A remaining issue, however, is that constructing such circuits, while in PTIME, can nonetheless have significant overhead. To avoid this cost, we utilize approximate query processing techniques to directly sample monomials without materializing lineage upfront. Our implementation in FastPDB provides accurate anytime approximation of probabilistic query answers and scales to datasets orders of magnitude larger than competing methods.
The modification problems toward subclasses of claw-free graphs have been investigated a lot in recent years. Proper Helly circular-arc graph is an important subclass of claw-free graphs. In this paper, we give an O(k...
详细信息
One of the most studied problem in theoretical computer science, Vertex Cover , has been recently considered in the temporal graph framework. Here we study a Vertex Cover variant, called k- TimelineCover . Given a tem...
详细信息
One of the most studied problem in theoretical computer science, Vertex Cover , has been recently considered in the temporal graph framework. Here we study a Vertex Cover variant, called k- TimelineCover . Given a temporal graph k- TimelineCover asks to define an interval for each vertex so that for every temporal edge existing in a timestamp t , at least one of the endpoints has an interval that includes t . The goal is to decide whether it is possible to cover every temporal edge while using vertex intervals of total span at most k . k- TimelineCover has been shown to be NP-hard, but its parameterized complexity has not been fully understood when parameterizing by the span of the solution. We settle this open problem by giving an FPT algorithm that combines two techniques, a modified form of iterative compression and a reduction to Digraph Pair Cut .
We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D and a...
详细信息
We study possible winner problems related to the uncovered set and the Banks set on partial tournaments from the viewpoint of parameterized complexity. We first study a problem where given a partial tournament D and a subset X of vertices, we are asked to add some arcs to D such that all vertices in X are included in the uncovered set. We focus on two parameterizations: parameterized by |X| and parameterized by the number of arcs to be added. In addition, we study a parameterized variant of the problem which is to determine whether all vertices of X can be included in the uncovered set by reversing at most k arcs. Finally, we study some parameterizations of a possible winner problem on partial tournaments, where we are given a partial tournament D and a distinguished vertex p, and asked whether D has a maximal transitive subtournament with p being the 0-indegree vertex. These parameterized problems are related to the Banks set. We achieve results, -hardness results as well as results along with a kernelization lower bound for the problems studied in this paper.
暂无评论