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

parameterized complexity of fair deletion problems

DISCRETE APPLIED MATHEMATICS 2020年 278卷 51-61页

作者： Masarik, Tomas Toufar, Tomas Charles Univ Prague Fac Math & Phys Dept Appl Math Malostranske Namesti 25 Prague Czech Republic Univ Warsaw Fac Math Informat & Mech Stefana Banacha 2 Warsaw Poland Charles Univ Prague Comp Sci Inst Fac Math & Phys Malostranske Namesti 25 Prague Czech Republic

Edge deletion problems are those where the goal is to find a subset of edges such that after its removal the graph satisfies the given graph property. Typically, we want to minimize the number of elements removed. In fair deletion problems, the objective is changed, so the maximum number of deletions in a neighborhood of a single vertex is minimized. We study the parameterized complexity of fair deletion problems concerning the structural parameters such as the tree-width, the path-width, the tree-depth, the size of minimum feedback vertex set, the neighborhood diversity, and the size of minimum vertex cover of graph G. We prove the W[1]-hardness of the fair FO vertex-deletion problem with respect to the combined size of the tree-depth and the minimum feedback vertex set number. Moreover, we show that there is no algorithm for fair FO vertex-deletion problem running in time n(o)((3)root k), where n is the size of the graph and k is the sum of the mentioned parameters, provided that the Exponential Time Hypothesis holds. On the other hand, we present an FPT algorithm for the fair MSO edge-deletion problem parameterized by the size of minimum vertex cover and an FPT algorithm for the fair MSO vertex-deletion problem parameterized by the neighborhood diversity. (C) 2019 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Fair problems Metatheorems Tree-depth Vertex cover Neighborhood diversity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of finding a spanning tree with minimum reload cost diameter

引用

NETWORKS 2020年第3期75卷 259-277页

作者： Baste, Julien Gozupek, Didem Paul, Christophe Sau, Ignasi Shalom, Mordechai Thilikos, Dimitrios M. Univ Montpellier LIRMM Montpellier France Gebze Tech Univ Dept Comp Engn Kocaeli Turkey Univ Montpellier LIRMM CNRS Montpellier France TelHai Coll Qiryat Shemona Israel Bogazici Univ Dept Ind Engn Istanbul Turkey Natl & Kapodistrian Univ Athens Dept Math Athens Greece

We study the minimum diameter spanning tree problem under the reload cost model (Diameter-Tree for short) introduced by Wirth and Steffan. In this problem, given an undirected edge-colored graph G, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of G of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the Diameter-Tree problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree Delta of the input graph. We prove that Diameter-Tree is para-NP-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove Diameter-Tree to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan proved that the problem can be solved in polynomial time on graphs with Delta = 3, and Galbiati proved that it is NP-hard if Delta = 4. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if Delta = 3, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that Diameter-Tree is in XP and W[1]-hard parameterized by the treewidth plus Delta.

关键词： dynamic programming FPT algorithm minimum diameter spanning tree parameterized complexity reload cost problems treewidth

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Learning First-Order Logic 22

On the Parameterized Complexity of Learning First-Order Logi...

引用

41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： van Bergerem, Steffen Grohe, Martin Ritzert, Martin Rhein Westfal TH Aachen Aachen Germany Aarhus Univ Aarhus Denmark

ISBN: (纸本)9781450392600

We analyse the complexity of learning first-order queries in a model-theoretic framework for supervised learning introduced by (Grohe and Turan, TOCS 2004). Previous research on the complexity of learning in this framework focussed on the question of when learning is possible in time sublinear in the background structure. Here we study the parameterized complexity of the learning problem. We have two main results. The first is a hardness result, showing that learning first-order queries is at least as hard as the corresponding model-checking problem, which implies that on general structures it is hard for the parameterized complexity class AW[*]. Our second main contribution is a fixed-parameter tractable agnostic PAC learning algorithm for first-order queries over sparse relational data (more precisely, over nowhere dense background structures).

关键词： first-order query learning agnostic probably approximately correct learning nowhere dense graph parameterized complexity fixed-parameter tractable Boolean classification supervised learning first-order logic

来源：评论

学校读者我要写书评

暂无评论

A survey on the parameterized complexity of reconfiguration problems

引用

COMPUTER SCIENCE REVIEW 2024年 53卷

作者： Bousquet, Nicolas Mouawad, Amer E. Nishimura, Naomi Siebertz, Sebastian Univ Claude Bernard Lyon 1 Lyon France Amer Univ Beirut Beirut Lebanon Univ Waterloo Waterloo ON Canada Univ Bremen Bremen Germany

A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices of the graph. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k , whether it is possible to transform one into the other by a sequence of token slides (along edges of the graph) or token jumps (between arbitrary vertices of the graph) such that each intermediate set remains a feasible solution of size k . Many algorithmic questions present themselves in the form of reconfiguration problems: Given the description of an initial system state and the description of a target state, is it possible to transform the system from its initial state into the target one while preserving certain properties of the system in the process? Such questions have received a substantial amount of attention under the so-called combinatorial reconfiguration framework. We consider reconfiguration variants of three fundamental underlying graph vertex-subset problems, namely INDEPENDENT SET, , DOMINATING SET, , and CONNECTED DOMINATING SET. . We survey both older and more recent work on the parameterized complexity of all three problems when parameterized by the number of tokens k . The emphasis will be on positive results and the most common techniques for the design of fixed-parameter tractable algorithms.

关键词： Combinatorial reconfiguration parameterized complexity Independent set Dominating set Connected dominating set Sparse graphs

来源：评论

学校读者我要写书评

暂无评论

On Girth and the parameterized complexity of Token Sliding and Token Jumping

引用

ALGORITHMICA 2021年第9期83卷 2914-2951页

作者： Bartier, Valentin Bousquet, Nicolas Dallard, Clement Lomer, Kyle Mouawad, Amer E. Univ Grenoble Alpes CNRS Grenoble INP G SCOP Grenoble France Univ Claude Bernard Lyon 1 Univ Lyon CNRS LIRIS Lyon France Univ Primorska FAMNIT Koper Slovenia Amer Univ Beirut Dept Comp Sci Beirut Lebanon

In the Token Jumping problem we are given a graph G = (V, E) and two independent sets S and T of G, each of size k >= 1. The goal is to determine whether there exists a sequence of k-sized independent sets in G, < S-0, S-1,., Sl >, such that for every i, S i = k, S i is an independent set, S = S-0, S-l = T, and vertical bar S-i Delta Si+1 vertical bar = 2. In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixed-parameter tractable on C-4-free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on {C-3, C-4}-free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant p = 4, both problems are W[1]hard on {C-4,., C-p}-free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.

关键词： Combinatorial reconfiguration Independent set Token jumping Token sliding parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Geometric Covering Problems Having Conflicts

引用

ALGORITHMICA 2020年第1期82卷 1-19页

作者： Banik, Aritra Panolan, Fahad Raman, Venkatesh Sahlot, Vibha Saurabh, Saket Natl Inst Sci Educ & Res Bhubaneswar Odisha India Univ Bergen Dept Informat Bergen Norway HBNI Inst Math Sci Chennai Tamil Nadu India Indian Inst Technol Jodhpur Rajasthan India

The input for the Geometric Coverage problem consists of a pair sigma=(P,R), where P is a set of points in R-d and R is a set of subsets of P defined by the intersection of P with some geometric objects in R-d. Motivated by what are called choice problems in geometry, we consider a variation of the Geometric Coverage problem where there are conflicts on the covering objects that precludes some objects from being part of the solution if some others are in the solution. As our first contribution, we propose two natural models in which the conflict relations are given: (a) by a graph on the covering objects, and (b) by a representable matroid on the covering objects. Our main result is that as long as the conflict graph has bounded arboricity there is a parameterized reduction to the conflict-free version. As a consequence, we have the following results when the conflict graph has bounded arboricity. (1) If the Geometric Coverage problem is fixed parameter tractable (FPT), then so is the conflict free version. (2) If the Geometric Coverage problem admits a factor alpha-approximation, then the conflict free version admits a factor alpha-approximation algorithm running in FPT time. As a corollary to our main result we get a plethora of approximation algorithms that run in FPT time. Our other results include an FPT algorithm and a hardness result for conflict-free version of Covering Points by Intervals. The FPT algorithm is for the case when the conflicts are given by a representable matroid. We prove that conflict-free version of Covering Points by Intervals does not admit an FPT algorithm, unless FPT =W[1], for the family of conflict graphs for which the Independent Set problem is W[1]-hard.

关键词： Conflict problems Geometric Coverage parameterized complexity Matroids

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the synthesis of Boolean nets with restricted place environments

引用

INTERNATIONAL JOURNAL OF CARDIOLOGY 2021年 343卷 36-69页

作者： Tredup, Ronny Erofeev, Evgeny Univ Rostock Inst Informat Theoret Informat Albert Einstein Str 22 D-18059 Rostock Germany Carl von Ossietzky Univ Oldenburg Dept Informat D-26111 Oldenburg Germany

Though constructing a sequential system model may be technically uncomplicated and rather 'straightforward', its result is often cumbersome and difficult to analyze since all possible interleavings of system's actions have to be present. This naturally raises the interest to the possibility of automatic synthesis of models that are able to grasp behavioral parallelism of the system. Boolean Petri nets are a classical formalism that enjoys generic concepts of concurrency, synchronization and conflict, and allows to obtain a concise yet expressive system representation. Let tau be a Boolean type of nets. The problem of tau-synthesis consists in deciding whether a given transition system A is isomorphic to the reachability graph of a Boolean Petri net N of type tau (a tau-net, for short). In case of a positive decision, N should be constructed. Another instance of the synthesis problem takes the dependencies of places into account: A place p of a tau-net depends on a transition t if p can influence t, that is, a marking of p can inhibit the firing of t, or if p can be influenced by t, that is, the firing of t can change a marking of p. The problem tau-synthesis of Boolean nets with restricted dependencies (tau-SOBNWRD) consists in deciding for a given transition system A and natural number d whether there exists a Boolean Petri net N of type tau such that, firstly, the reachability graph of N and A are isomorphic and, secondly, every place p of N depends on at most d transitions. For many Boolean types that allow independence, the (unrestricted) tau-synthesis problem is NP-complete, and for all of them r-SOBNWRD inherits the NP-completeness. In this paper, we enhance our understanding of tau-SOBNWRD from a parameterized point of view: We show for 27 of the 128 thinkable Boolean types that allow independence that tau-SOBNWRD parameterized by d is W [1]-hard, and for 75 of them that the problem is W[2]-hard. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Petri net Transition system Synthesis parameterized complexity PETRI NETS SYSTEMS

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of s-club cluster deletion problems

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期969卷

作者： Montecchiani, Fabrizio Ortali, Giacomo Piselli, Tommaso Tappini, Alessandra Univ Perugia Dept Engn Perugia Italy

We study the parameterized complexity of the s-CLUB CLUSTER EDGE DELETION (s-CLUB CLUSTER VERTEX DELETION) problem: Given a graph G and two integers s > 2 and k > 1, is it possible to remove at most k edges (vertices) from G such that each connected component of the resulting graph has diameter at most s? Both s-CLUB CLUSTER EDGE DELETION and s -CLUB CLUSTER VERTEX DELETION problems are known to be NP-hard already when s = 2. We prove that they admit a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph. The proof is based on a unified algorithm that solves the more general problem in which both edges and vertices can be removed from the input graph to obtain a set of disjoint components with bounded diameter. Our approach can also be exploited to solve a related problem, namely s-CLUB COVER, which asks whether it is possible to cover the vertices of a graph with at most d different s-clubs, for some fixed d > 1 and s > 2.& COPY;2023 Elsevier B.V. All rights reserved.

关键词： Cluster deletion problems parameterized complexity s-Club

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the Maximum Exposure Problem

引用

INFORMATION PROCESSING LETTERS 2023年 180卷

作者： Raman, Remi John, J. S. Shahin Subashini, R. Methirumangalath, Subhasree Natl Inst Technol Calicut India

We investigate the parameterized complexity of the Maximum Exposure Problem (MEP). Given a range space (R, P) where R is the set of ranges containing a set P of points and an integer k, MEP asks for k ranges, which on removal results in the maximum number of exposed points. A point p is said to be exposed when p is not contained in any of the ranges in R. The problem is known to be NP-hard. In this paper, we give fixed-parameter tractable results of MEP with respect to different parameterizations.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Maximum Exposure Problem Computational Geometry parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the acyclic matching problem

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期958卷

作者： Hajebi, Sahab Javadi, Ramin Isfahan Univ Technol Dept Math Sci POB 84156-83111 Esfahan Iran Inst Res Fundamental Sci IPM Sch Math POB 19395-5746 Tehran Iran

A matching is a set of edges in a graph with no common endpoint. A matching M is called acyclic if the induced subgraph on the endpoints of the edges in M is acyclic. Given a graph G and an integer k, Acyclic Matching problem seeks for an acyclic matching of size k in G. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs of maximum degree three and arbitrarily large girth. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter k. On the other hand, the problem is fixed parameter tractable with respect to the parameters treewidth, modular-width and (k, c4), where c4 is the number of cycles with length 4 of the input graph. We also prove that the problem is fixed parameter tractable with respect to the parameter k for the line graphs and every proper minor-closed class of graphs (including planar graphs). (c) 2023 Elsevier B.V. All rights reserved.

关键词： Acyclic matching Induced matching Computational complexity parameterized complexity Treewidth Modular-width

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：