检索结果-内蒙古大学图书馆

29th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fomin, Fedor V. Golovach, Petr A. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Sci Labs Durham DH1 3LE England

ISBN: (纸本)9783939897354

Cai and Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs. For a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about a connected k-EDGE subgraph with all vertices of odd degrees, the problem known as k-Edge CONNECTED ODD SUBGRAPH;and a connected k-vertex induced subgraph with all vertices of even degrees, the problem known as k-VERTEX EULERIAN SUBGRAPH. We resolve both open problems and thus complete the characterization of even/odd subgraph problems from parameterized complexity perspective. We show that k-EDGE CONNECTED ODD SUBGRAPH is FPT and that k-VERTEX EULERIAN SUBGRAPH IS W[1]-hard. Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges.

关键词： parameterized complexity Euler graph even graph odd graph treewidth

来源：评论

学校读者我要写书评

暂无评论

W-Hardness of the k-Center Problem parameterized by the Skeleton Dimension 1

引用

26th International Computing and Combinatorics Conference (COCOON)

作者： Blum, Johannes Univ Konstanz Constance Germany

ISBN: (数字)9783030581503

ISBN: (纸本)9783030581503;9783030581497

In the k-CENTER problem, we are given a graph G = (V, E) with positive edge weights and an integer k and the goal is to select k center vertices C subset of V such that the maximum distance from any vertex to the closest center vertex is minimized. On general graphs, the problem is NP-hard and cannot be approximated within a factor less than 2. Typical applications of the k-CENTER problem can be found in logistics or urban planning and hence, it is natural to study the problem on transportation networks. Such networks are often characterized as graphs that are (almost) planar or have low doubling dimension, highway dimension or skeleton dimension. It was shown by Feldmann and Marx that k-CENTER is W[1]-hard on planar graphs of constant doubling dimension when parameterized by the number of centers k, the highway dimension hd and the pathwidth pw [11]. We extend their result and show that even if we additionally parameterize by the skeleton dimension kappa, the k-CENTER problem remains W[1]-hard. Moreover, we prove that under the Exponential Time Hypothesis there is no exact algorithm for k-CENTER that has runtime f (k, hd, pw, kappa) center dot vertical bar V vertical bar(o(pw+kappa+root k+hd) ts+ k+hd)) for any computable function f .

关键词： k-Center Skeleton dimension parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

A parameterized Perspective on Attacking and Defending Elections 31st

A Parameterized Perspective on Attacking and Defending Elect...

引用

31st International Workshop on Combinatorial Algorithms (IWOCA)

作者： Gowda, Kishen N. Misra, Neeldhara Patel, Vraj Indian Inst Technol Gandhinagar India

ISBN: (纸本)9783030489656;9783030489663

We consider the problem of protecting and manipulating elections by recounting and changing ballots, respectively. Our setting involves a plurality-based election held across multiple districts, and the problem formulations are based on the model proposed recently by [Elkind et al., IJCAI 2019]. It turns out that both of the manipulation and protection problems are NP-complete even in fairly simple settings. We study these problems from a parameterized perspective with the goal of establishing a more detailed complexity landscape. The parameters we consider include the number voters, and the budgets of the attacker and the defender. While we observe fixed-parameter tractability when parameterizing by number of voters, our main contribution is a demonstration of parameterized hardness when working with the budgets of the attacker and the defender.

关键词： Elections W-hardness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for locating-dominating sets ⁎

引用

Procedia Computer Science 2021年 195卷 68-76页

作者： Márcia R. Cappelle Guilherme C.M. Gomes Vinicius F. dos Santos Instituto de Informática Universidade Federal de Goiás Goiânia-GO Brazil Departamento de Ciência da Computação Universidade Federal de Minas Gerais Belo Horizonte Brazil

A locating-dominating set D of a graph G is a dominating set of G where each vertex not in D has a unique neighborhood in D, and the Locating-Dominating Set problem asks if G contains such a dominating set of bounded size. This problem is known to be NP-hard even on restricted graph classes, such as interval graphs, split graphs, and planar bipartite subcubic graphs. On the other hand, it is known to be solvable in polynomial time for some graph classes, such as trees and, more generally, graphs of bounded cliquewidth. While these results have numerous implications on the parameterized complexity of the problem, little is known in terms of kernelization under structural parameterizations. In this work, we begin filling this gap in the literature. Our first result shows that Locating-Dominating Set is W[1]-hard when parameterized by the size of a minimum clique cover. We present an exponential kernel for the distance to cluster parameterization and show that, unless NP ⊆ coNP/poly, no polynomial kernel exists for Locating-Dominating Set when parameterized by vertex cover nor when parameterized by distance to clique. We then turn our attention to parameters not bounded by either of the previous two, and exhibit a linear kernel when parameterizing by the max leaf number; in this context, we leave the parameterization by feedback edge set as the primary open problem in our study.

关键词： parameterized complexity kernelization distance to cluster cross-composition vertex cover distance to clique minimum clique cover max leaf number

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for QBFs of Bounded Treewidth 20

Lower Bounds for QBFs of Bounded Treewidth

引用

35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Fichte, Johannes K. Hecher, Markus Pfandler, Andreas Tech Univ Dresden Dresden Germany TU Wien Vienna Austria

ISBN: (纸本)9781450371049

The problem of deciding the validity (QSAT) of quantified Boolean formulas (QBF) is a vivid research area in both theory and practice. In the field of parameterized algorithmics, the well-studied graph measure treewidth turned out to be a successful parameter. A well-known result by Chen [9] is that QSAT when parameterized by the treewidth of the primal graph and the quantifier rank of the input formula is fixed-parameter tractable. More precisely, the runtime of such an algorithm is polynomial in the formula size and exponential in the treewidth, where the exponential function in the treewidth is a tower, whose height is the quantifier rank. A natural question is whether one can significantly improve these results and decrease the tower while assuming the Exponential Time Hypothesis (ETH). In the last years, there has been a growing interest in the quest of establishing lower bounds under ETH, showing mostly problem-specific lower bounds up to the third level of the polynomial hierarchy. Still, an important question is to settle this as general as possible and to cover the whole polynomial hierarchy. In this work, we show lower bounds based on the ETH for arbitrary QBFs parameterized by treewidth and quantifier rank. More formally, we establish lower bounds for QSAT and treewidth, namely, that under ETH there cannot be an algorithm that solves QSAT of quantifier rank i in runtime significantly better than i-fold exponential in the treewidth and polynomial in the input size. In doing so, we provide a reduction technique to compress treewidth that encodes dynamic programming on arbitrary tree decompositions. Further, we describe a general methodology for a more fine-grained analysis of problems parameterized by treewidth that are at higher levels of the polynomial hierarchy. Finally, we illustrate the usefulness of our results by discussing various applications of our results to problems that are located higher on the polynomial hierarchy, in particular, various prob

关键词： parameterized complexity ETH Lower Bounds Quantified Boolean Formulas Treewidth Pathwidth

来源：评论

学校读者我要写书评

暂无评论

Efficient parameterized Algorithms for Computing All-Pairs Shortest Paths 37

Efficient Parameterized Algorithms for Computing All-Pairs S...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Kratsch, Stefan Nelles, Florian Humboldt Univ Berlin Germany

ISBN: (纸本)9783959771405

Computing all-pairs shortest paths is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster algorithms for it than the O(n(3)) time algorithm due to Floyd and Warshall (1962). Somewhat faster algorithms exist for the vertex-weighted version if fast matrix multiplication may be used. Yuster (SODA 2009) gave an algorithm running in time O(n(2.842)) , but no combinatorial, truly subcubic algorithm is known. Motivated by the recent framework of efficient parameterized algorithms (or "FPT in P"), we investigate the influence of the graph parameters clique-width (cw) and modular-width (mw) on the running times of algorithms for solving ALL-PAIRS SHORTEST PATHS. We obtain efficient (and combinatorial) parameterized algorithms on non-negative vertex-weighted graphs of times O(cw(2) n(2)), resp. O(mw(2) n(2)). If fast matrix multiplication is allowed then the latter can be improved to O( mw(1.842) n + n(2)) using the algorithm of Yuster as a black box. The algorithm relative to modular-width is adaptive, meaning that the running time matches the best unparameterized algorithm for parameter value mw equal to n, and they outperform them already for mw is an element of O(n(1-epsilon)) for any epsilon > 0.

关键词： All-pairs shortest Paths efficient parameterized Algorithms parameterized complexity Clique-width Modular-width

来源：评论

学校读者我要写书评

暂无评论

Solving Connectivity Problems parameterized by Treedepth in Single-Exponential Time and Polynomial Space 37

Solving Connectivity Problems Parameterized by Treedepth in ...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Hegerfeld, Falko Kratsch, Stefan Humboldt Univ Berlin Germany

ISBN: (纸本)9783959771405

A breakthrough result of Cygan et al. (FOCS 2011) showed that connectivity problems parameterized by treewidth can be solved much faster than the previously best known time O* (2O((tw log tw))) Using their inspired Cut&Count technique, they obtained O* (alpha(tw)) time algorithms for many such problems. Moreover, they proved these running times to be optimal assuming the Strong Exponential-Time Hypothesis. Unfortunately, like other dynamic programming algorithms on tree decompositions, these algorithms also require exponential space, and this is widely believed to be unavoidable. In contrast, for the slightly larger parameter called treedepth, there are already several examples of matching the time bounds obtained for treewidth, but using only polynomial space. Nevertheless, this has remained open for connectivity problems. In the present work, we close this knowledge gap by applying the Cut&Count technique to graphs of small treedepth. While the general idea is unchanged, we have to design novel procedures for counting consistently cut solution candidates using only polynomial space. Concretely, we obtain time O* (3(d)) and polynomial space for CONNECTED VERTEX COVER, FEEDBACK VERTEX SET, and STEINER TREE on graphs of treedepth d. Similarly, we obtain time O* (4(d)) and polynomial space for CONNECTED DOMINATING SET and CONNECTED ODD CYCLE TRANSVERSAL.

关键词： parameterized complexity Connectivity Treedepth Cut&Count Polynomial Space

来源：评论

学校读者我要写书评

暂无评论

complexity and Approximability of parameterized MAX-CSPs

引用

ALGORITHMICA 2017年第1期79卷 230-250页

作者： Dell, Holger Kim, Eun Jung Lampis, Michael Mitsou, Valia Moemke, Tobias Saarland Univ Saarbrucken Germany Cluster Excellence Saarbrucken Germany Univ Paris 09 Paris France Hungarian Acad Sci SZTAKI Budapest Hungary

We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity;the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable-constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types , , , and , and with various parameters k, and we attempt to fully classify them into the following three cases:The exact optimum can be computed in time. It is -hard to compute the exact optimum, but there is a randomized approximation scheme (), which computes a -approximation in time . There is no unless .

关键词： Constraint satisfaction problems parameterized complexity Approximation Clique width Neighborhood diversity

来源：评论

学校读者我要写书评

暂无评论

parameterized Algorithms for Directed Modular Width 6th

Parameterized Algorithms for Directed Modular Width

引用

6th International Conference on Algorithms and Discrete Applied Mathematics

作者： Steiner, Raphael Wiederrecht, Sebastian Tech Univ Berlin Berlin Germany

ISBN: (纸本)9783030392185;9783030392192

Many well-known NP-hard algorithmic problems on directed graphs resist efficient parameterizations with most known width measures for directed graphs, such as directed treewidth, DAG-width, Kelly-width and many others. While these focus on measuring how close a digraph is to an oriented tree resp. a directed acyclic graph, in this paper, we investigate directed modular width as a parameter, which is closer to the concept of clique-width. We investigate applications of modular decompositions of directed graphs to a wide range of algorithmic problems and derive FPT algorithms for several well-known digraph-specific NP-hard problems, namely minimum (weight) directed feedback vertex set, minimum (weight) directed dominating set, digraph colouring, directed Hamiltonian path/cycle, partitioning into paths, (capacitated) vertex-disjoint directed paths, and the directed subgraph homeomorphism problem. The latter yields a polynomial-time algorithm for detecting topological minors in digraphs of bounded directed modular width. Finally we illustrate that other structural digraph parameters, such as directed pathwidth and cycle-rank can be computed efficiently using directed modular width as a parameter.

关键词： parameterized complexity Fixed-parameter-tractability Width measures Modular decomposition Integer Linear Programming

来源：评论

学校读者我要写书评

暂无评论

Minimum Conflict Free Colouring parameterized by Treewidth 6th

Minimum Conflict Free Colouring Parameterized by Treewidth

引用

6th International Conference on Algorithms and Discrete Applied Mathematics

作者： Ashok, Pradeesha Bhargava, Rathin Gupta, Naman Khalid, Mohammad Yadav, Dolly Int Inst Informat Technol Bangalore Bangalore Karnataka India Indian Inst Sci Educ & Res Mohali Mohali India

ISBN: (纸本)9783030392185;9783030392192

Conflict free q-Colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the MINIMUM CONFLICT FREE Q-COLOURING problem. Given a graph G and a fixed constant q, MINIMUM CONFLICT FREE Q-Colouring is to find a Conflict free q-Colouring of G that minimises the number of coloured vertices. We study the MINIMUM CONFLICT FREE Q-COLOURING problem parameterized by the treewidth of G. We give an FPT algorithm for this problem and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH).

关键词： Conflict free colouring of graphs parameterized complexity FPT algorithms Treewidth Exponential Time Hypothesis Strong Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：