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

34th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA)

作者： Golovach, Petr A. Stamoulis, Giannos Thilikos, Dimitrios M. Univ Bergen Dept Informat Bergen Norway Univ Montpellier CNRS LIRMM Montpellier France

ISBN: (纸本)9781611977554

The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (FOL) with the extra atomic predicate dp(k)(x(1), y(1),..., x(k), y(k)), expressing the existence of internally vertex-disjoint paths between x(i) and y(i), for i epsilon {1,..., k}. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every proper minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the scattered disjoint paths logic, FOL+SDP, where we further consider the atomic predicate s-sdp k (x(1), y(1,)..., x(k), y(k)), demanding that the disjoint paths are within distance bigger than some fixed value s. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus.

关键词： algorithmic meta-theorems Model-checking First-order logic Disjoint paths Hadwiger number Graph minors Irrelevant vertex technique

来源：评论

学校读者我要写书评

暂无评论

An algorithmic meta-Theorem for Graph Modification to Planarity and FOL

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2022年第3-4期14卷 13-13页

作者： Fomin, Fedor, V Golovach, Petr A. Stamoulis, Giannos Thilikos, Dimitrios M. Univ Bergen Dept Informat Thormohlensgate St Bergen Norway Univ Montpellier CNRS LIRMM Montpellier France

In general, a graph modification problem is defined by a graph modification operation boxed times and a target graph property P. Typically, the modification operation boxed times may be vertex deletion, edge deletion, edge contraction, or edge addition and the question is, given a graph Gand an integer k, whether it is possible to transform Gto a graph in Pafter applying the operation boxed times ktimes on G. This problem has been extensively studied for particular instantiations of boxed times and P. In this article, we consider the general property P-phi of being planar and, additionally, being a model of some First-Order Logic (FOL) sentence phi(an FOL-sentence). We call the corresponding meta-problem Graph boxed times-Modification to Planarity and fand prove the following algorithmic meta-theorem: there exists a function f : N-2. Nsuch that, for every boxed times and every FOL-sentence phi, the Graph boxed times-Modification to Planarity and phi solvable in f (k,|phi|) center dot n(2) time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surfaceembeddability (that are not FOL-expressible) and the second is the use of Gaifman's locality theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.

关键词： Graph modification problems algorithmic meta-theorems First-Order Logic irrelevant vertex technique planar graphs

来源：评论

学校读者我要写书评

暂无评论

Model-Checking on Ordered Structures

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2020年第2期21卷 11-11页

作者： Eickmeyer, Kord van den Heuvel, Jan Kawarabayashi, Ken-ichi Kreutzer, Stephan de Mendez, Patrice Ossona Pilipczuk, Michal Quiroz, Daniel A. Rabinovich, Roman Siebertz, Sebastian Tech Univ Darmstadt Dept Math Schlossgartenstr 7 D-64289 Darmstadt Germany London Sch Econ & Polit Sci Dept Math Houghton St London WC2A 2AE England Natl Inst Informat Hitotsubashi 2-1-2 Tokyo 1018430 Japan Tech Univ Berlin Log & Semant Ernst Reuter Pl 7 D-10587 Berlin Germany CNRS UMR 8557 Ctr Anal & Math Sociales 54 Blvd Raspail F-75006 Paris France Charles Univ Prague Comp Sci Inst IUUK Malostranske Nam 25 Prague 11800 Czech Republic Univ Warsaw Inst Informat Stefana Banacha 2 PL-02097 Warsaw Poland Univ Chile Dept Ingn Matemat Av Beauchef 851 Santiago 851 Chile Univ Chile Ctr Modelamiento Matemat Av Beauchef 851 Santiago 851 Chile Univ Bremen Bremen Germany Humboldt Univ Inst Informat Unter Linden 6 D-10099 Berlin Germany

We study the model-checking problem for first- and monadic second-order logic on finite relational structures. The problem of verifying whether a formula of these logics is true on a given structure is considered intractable in general, but it does become tractable on interesting classes of structures, such as on classes whose Gaifman graphs have bounded treewidth. In this article, we continue this line of research and study model-checking for first- and monadic second-order logic in the presence of an ordering on the input structure. We do so in two settings: the general ordered case, where the input structures are equipped with a fixed order or successor relation, and the order-invariant case, where the formulas may resort to an ordering, but their truth must be independent of the particular choice of order. In the first setting we show very strong intractability results for most interesting classes of structures. In contrast, in the order-invariant case we obtain tractability results for order-invariant monadic second-order formulas on the same classes of graphs as in the unordered case. For first-order logic, we obtain tractability of successor-invariant formulas on classes whose Gaifman graphs have bounded expansion. Furthermore, we show that model-checking for order-invariant first-order formulas is tractable on coloured posets of bounded width.

关键词： Model checking order-invariance successor-invariance algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

Computations by fly-automata beyond monadic second-order logic

引用

THEORETICAL COMPUTER SCIENCE 2016年 619卷 32-67页

作者： Courcelle, Bruno Durand, Irene CNRS LaBRI 351 Cours Liberat F-33405 Talence France Bordeaux Univ 351 Cours Liberat F-33405 Talence France

The validity of a monadic-second order (MS) expressible property can be checked in linear time on graphs of bounded tree-width or clique-width given with appropriate decompositions. This result is proved by constructing from the MS sentence expressing the property and an integer that bounds the tree-width or clique-width of the input graph, a finite automaton intended to run bottom-up on the algebraic term representing a decomposition of the input graph. As we cannot construct practically the transition tables of these automata because they are huge, we use fly-automata whose states and transitions are computed "on the fly", only when needed for a particular input. Furthermore, we allow infinite sets of states and we equip automata with output functions. Thus, they can check properties that are not MS expressible and compute values, for example, the number of p-colorings of a graph. We obtain XP and FPT graph algorithms, parameterized by tree width or clique-width. We show how to construct easily such algorithms by combining predefined automata for basic functions and properties. These combinations reflect the structure of the MS formula that specifies the property to check or the function to compute. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Monadic second-order logic Graph algorithms Infinite automata Parameterized algorithms Tree-width Clique-width Dynamic programming Model-checking Data complexity algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry

引用

ANNALS OF PURE AND APPLIED LOGIC 2016年第11期167卷 1093-1122页

作者： Hill, Cameron Donnay

Using finite directed systems defined from "primitive" extension and amalgamation operations, we define an abstract notion of hierarchical decomposition that applies to a large family of classes of finite structures (tame classes). We prove that for any such class C that is uniformly hierarchical - in the sense that cofinally-many members of C have decompositions according to a functorial "program" - the theory T-C of the generic structure is rosy. Conversely, we also show that for any tame class C, if T-C is rosy, then C is uniformly hierarchical. Thus, the project of stratifying the complexity of computationally hard problems through parametrizing "width" notions - an important current in Finite Model Theory and Descriptive Complexity Theory - has a second face in Geometric Model Theory. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Rosy theories Finite structures Fraisse classes Coordinatization Hierarchical decomposition algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

引用

ACM TRANSACTIONS ON ALGORITHMS 2016年第2期12卷 21-21页

作者： Kim, Eun Jung Langer, Alexander Paul, Christophe Reidl, Felix Rossmanith, Peter Sau, Ignasi Sikdar, Somnath CNRS LAMSADE Paris Paris France Rhein Westfal TH Aachen LuF Theoret Informat D-52056 Aachen Germany CNRS LIRMM Montpellier Montpellier France LIRMM 161 Rue Ada F-34095 Montpellier 05 France

We present a linear-time algorithm to compute a decomposition scheme for graphs G that have a set X subset of V(G), called a treewidth-modulator, such that the treewidth of G-X is bounded by a constant. Our decomposition, called a protrusion decomposition, is the cornerstone in obtaining the following two main results. Our first result is that any parameterized graph problem (with parameter k) that has a finite integer index and such that YES-instances have a treewidth-modulator of size O(k) admits a linear kernel on the class of H-topological-minor-free graphs, for any fixed graph H. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus and H-minor-free graphs. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n-vertex graph G and a non-negative integer k, PLANAR-F-DELETION asks whether G has a set X subset of V(G) such that vertical bar X vertical bar <= k and G-X is H-minor-free for every H epsilon F. As our second application, we present the first single-exponential algorithm to solve PLANAR-F-DELETION. Namely, our algorithm runs in time 2())(O(k) . n(2), which is asymptotically optimal with respect to k. So far, single-exponential algorithms were only known for special cases of the family F.

关键词： Parameterized complexity algorithmic meta-theorems sparse graphs graph minors hitting minors

来源：评论

学校读者我要写书评

暂无评论

FO Model Checking on Posets of Bounded Width 56

FO Model Checking on Posets of Bounded Width

引用

56th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Gajarsky, Jakub Hlineny, Petr Lokshtanov, Daniel Obdrzalek, Jan Ordyniak, Sebastian Ramanujan, M. S. Saurabh, Saket Masaryk Univ Fac Informat Brno Czech Republic Univ Bergen Bergen Norway Inst Math Sci Chennai Tamil Nadu India TU Wien Vienna Austria

ISBN: (纸本)9781467381918

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC' 14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [CSL-LICS' 14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula phi, and determines whether phi holds on P in time f(phi, w) . n(2).

关键词： first-order logic partially ordered sets parameterized complexity algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

KERNELIZING MSO PROPERTIES OF TREES OF FIXED HEIGHT, AND SOME CONSEQUENCES

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2015年第1期11卷

作者： Gajarsky, Jakub Hlineny, Petr Masaryk Univ Fac Informat Brno Czech Republic

Fix an integer h >= 1. In the universe of coloured trees of height at most h, we prove that for any graph decision problem defined by an MSO1 formula with r quantifiers, there exists a set of kernels, each of size bounded by an elementary function of r and the number of colours. This yields two noteworthy consequences. Consider any graph class 9 having a one-dimensional MSO1 interpretation in the universe of coloured trees of height h (equivalently, 9 being a class of shrub-depth h). First, 9 admits an MSO1 model checking algorithm whose runtime has an elementary dependence on the formula size. Second, on 9 the expressive powers of FO and MSO1 coincide (which extends a 2012 result of Elberfeld, Grohe, and Tantau).

关键词： MSO logic Model checking Courcelle's theorem algorithmic meta-theorems tree-depth shrub-depth

来源：评论

学校读者我要写书评

暂无评论

FO Model Checking on Posets of Bounded Width

FO Model Checking on Posets of Bounded Width

引用

IEEE Annual Symposium on Foundations of Computer Science

作者： Jakub Gajarsky Petr Hlineny Daniel Lokshtanov Jan Obdrzalek Sebastian Ordyniak M. S. Ramanujan Saket Saurabh Faculty of Informatics Masaryk University University of Bergen The Institute of Mathematical Sciences

ISBN: (纸本)9781467381925

Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures - culminating in the FPT-algorithm by Grohe, Kreutzer and Siebertz for FO model checking of nowhere dense classes of graphs [STOC'14], with dense structures starting to attract attention only recently. Bova, Ganian and Szeider [CSL-LICS'14] initiated the study of the complexity of FO model checking on partially ordered sets (posets). Bova, Ganian and Szeider showed that model checking existential FO logic is fixed-parameter tractable (FPT) on posets of bounded width, where the width of a poset is the size of the largest antichain in the poset. The existence of an FPT algorithm for general FO model checking on posets of bounded width, however, remained open. We resolve this question in the positive by giving an algorithm that takes as its input an n-element poset P of width w and an FO logic formula φ, and determines whether φ holds on P in time f(φ, w) · n~2.

关键词： First-order logic Partially ordered sets Parameterized complexity algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

MODEL CHECKING LOWER BOUNDS FOR SIMPLE GRAPHS

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2014年第1期10卷

作者： Lampis, Michael Kyoto Univ RIMS Kyoto 6068501 Japan

A well-known result by Frick and Grohe shows that deciding FO logic on trees involves a parameter dependence that is a tower of exponentials. Though this lower bound is tight for Courcelle's theorem, it has been evaded by a series of recent meta-theorems for other graph classes. Here we provide some additional non-elementary lower bound results, which are in some sense stronger. Our goal is to explain common traits in these recent meta-theorems and identify barriers to further progress. More specifically, first, we show that on the class of threshold graphs, and therefore also on any union and complement-closed class, there is no model-checking algorithm with elementary parameter dependence even for FO logic. Second, we show that there is no model-checking algorithm with elementary parameter dependence for MSO logic even restricted to paths (or equivalently to unary strings), unless E=NE. As a corollary, we resolve an open problem on the complexity of MSO model-checking on graphs of bounded max-leaf number. Finally, we look at MSO on the class of colored trees of depth d. We show that, assuming the ETH, for every fixed d >= 1 at least d + 1 levels of exponentiation are necessary for this problem, thus showing that the (d + 1)-fold exponential algorithm recently given by Gajarsky and Hlineny is essentially optimal.

关键词： MSO logic Model checking Courcelle's theorem algorithmic meta-theorems Parameterized Complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：