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

56th Annual ACM Symposium on theory of Computing (STOC)

作者： Cavallaro, Dario Giuliano Kawarabayashi, Ken-ichi Kreutzer, Stephan Tech Univ Berlin Berlin Germany Natl Inst Informat Tokyo Japan Univ Tokyo Tokyo Japan

ISBN: (纸本)9798400703836

Disjoint paths problems are among the most prominent problems in combinatorial optimisation. The edge- as well as the Vertex-Disjoint Paths problem are NP-complete, both on directed and undirected graphs. But on undirected graphs, Robertson and Seymour developed an algorithm for both problems that runs in cubic time for every fixed number p of terminal pairs, i.e. they proved that the problem is fixed-parameter tractable on undirected graphs. This is in sharp contrast to the situation on directed graphs, where Fortune, Hopcroft, and Wyllie proved that both problems are NP-complete already for p = 2 terminal pairs. In this paper, we study the Edge-Disjoint Paths problem (EDPP) on Eulerian digraphs, a problem that has received significant attention in the literature. Marx proved that the Eulerian EDPP is NP-complete even on structurally very simple Eulerian digraphs. On the positive side, polynomial time algorithms are known only for very restricted cases, such as p <= 3 or where the demand graph is a union of two stars. The question for which values of p the Edge-Disjoint Paths problem can be solved in polynomial time on Eulerian digraphs has already been raised by Frank, Ibaraki, and Nagamochi almost 30 years ago. But despite considerable effort, the complexity of the problem is still wide open and is considered to be the main open problem in this area. In this paper, we solve this long-open problem by showing that the Edge-Disjoint Paths problem is fixed-parameter tractable on Eulerian digraphs in general (parameterized by the number of terminal pairs). The algorithm itself is reasonably simple but the proof of its correctness requires a deep structural analysis of Eulerian digraphs.

关键词： Eulerian Digraphs Edge-Disjoint Paths Problem Directed graphs graph structure theory Fixed Parameter Tractability

来源：评论

学校读者我要写书评

暂无评论

Packing Even Directed Circuits Quarter-Integrally 2024

Packing Even Directed Circuits Quarter-Integrally

引用

56th Annual ACM Symposium on theory of Computing (STOC)

作者： Gorsky, Maximilian Kawarabayashi, Ken-ichi Kreutzer, Stephan Wiederrecht, Sebastian Tech Univ Berlin Berlin Germany Natl Inst Informat Tokyo Japan Univ Tokyo Tokyo Japan Inst for Basic Sci Korea Daejeon South Korea

ISBN: (纸本)9798400703836

We prove the existence of a computable function f:N -> N such that for every integer k and every digraph D, either D contains a collection C of k directed cycles of even length such that no vertex of D belongs to more than four cycles in C, or there exists a set S subset of V(D) of size at most f(k) such that D-S has no directed cycle of even length. Moreover, we provide an algorithm that finds one of the two outcomes of this statement in time g(k)n(O(1)) for some computable function g: N -> N. Our result unites two deep fields of research from the algorithmic theory for digraphs: The study of the Erdos-Posa property of digraphs and the study of the Even Dicycle Problem. The latter is the decision problem which asks if a given digraph contains an even dicycle and can be traced back to a question of Polya from 1913. It remained open until a polynomial time algorithm was finally found by Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004;announced jointly at STOC 1997). The Even Dicycle Problem is equivalent to the recognition problem of Pfaffian bipartite graphs and has applications even beyond discrete mathematics and theoretical computer science. On the other hand, Youngers Conjecture (1973), states that dicycles have the Erdos-Posa property. The conjecture was proven more than two decades later by Reed, Robertson, Seymour, and Thomas (Combinatorica 1996) and opened the path for structural digraph theory as well as the algorithmic study of the directed feedback vertex set problem. Our approach builds upon the techniques used to resolve both problems and combines them into a powerful structural theorem that yields further algorithmic applications for other prominent problems.

关键词： Even Dicycles Erdos-Posa property Directed graphs graph structure theory Matching theory Fixed Parameter Tractability

来源：评论

学校读者我要写书评

暂无评论

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

引用

ALGORITHMICA 2022年第2期84卷 482-509页

作者： Lokshtanov, Daniel Mouawad, Amer E. Panolan, Fahad Siebertz, Sebastian Univ Calif Santa Barbara Santa Barbara CA 93106 USA Amer Univ Beirut Dept Comp Sci Beirut Lebanon IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Univ Bremen Bremen Germany

In a reconfiguration version of a decision problem Q the input is an instance of Q and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the CONNECTED DOMINATING SET RECONFIGURATION problem (CDS- R). It was shown in previous work that the DOMINATING SET RECONFIGURATION problem (DS- R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K-d(,d) as a subgraph, for some constant d >= 1. We show that the additional connectivity constraint makes the problem much harder, namely, that CDS- R is W[1]-hard parameterized by k + l, the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS- R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs.

关键词： Reconfiguration Parameterized complexity Connected dominating set graph structure theory

来源：评论

学校读者我要写书评

暂无评论

Polynomial Kernels and Wideness Properties of Nowhere Dense graph Classes

引用

ACM TRANSACTIONS ON ALGORITHMS 2019年第2期15卷 24-24页

作者： Kreutzer, Stephan Rabinovich, Roman Siebertz, Sebastian Tech Univ Berlin Inst Softwaretech & Theoret Informat Lehrstuhl Log & Semant TEL 7-3Ernst Reuter Pl 7 D-10587 Berlin Germany Humboldt Univ Johann von Neumann Haus Inst Informat Algorithm Engn Rudower Chausse 25 D-12489 Berlin Germany

Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this article, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. A powerfulmethod in parameterized complexity theory is to compute a problem kernel in a pre-computation step, that is, to reduce the input instance in polynomial time to a sub-instance of size bounded in the parameter only (independently of the input graph size). Our new tools allow us to obtain for every fixed radius r is an element of N a polynomial kernel for the distance-r dominating set problem on nowhere dense classes of graphs. This result is particularly interesting, as it implies that for every class C of graphs that is closed under taking subgraphs, the distance-r dominating set problem admits a kernel on C for every value of r if, and only if, it already admits a polynomial kernel for every value of r (under the standard assumption of parameterized complexity theory that FPT not equal W[2]).

关键词： graph structure theory nowhere denseness uniform quasi-wideness stability theory

来源：评论

学校读者我要写书评

暂无评论

The Directed Grid Theorem 15

The Directed Grid Theorem

引用

47th Annual ACM Symposium on theory of Computing (STOC) held as part of the Federated Computing Research Conference

作者： Kawarabayashi, Ken-ichi Kreutzer, Stephan Natl Inst Informat Chiyoda Ku 2-1-2 Hitotsubashi Tokyo Japan Tech Univ Berlin Sekr TEL 7-3Ernst Reuter Pl 7 D-10587 Berlin Germany

ISBN: (纸本)9781450335362

The grid theorem, originally proved in 1986 by Robertson and Seymour in graph Minors V, is one of the most central results in the study of graph minors. It has found numerous applications in algorithmic graph structure theory, for instance in bidimensionality theory, and it is the basis for several other structure theorems developed in the graph minors project. In the mid-90s, Reed and Johnson, Robertson, Seymour and Thomas (see [34, 21]), independently, conjectured an analogous theorem for directed graphs, i.e. the existence of a function f : N -> N such that every digraph of directed tree width at least f(k) contains a directed grid of order k. In an unpublished manuscript from 2001, Johnson, Robertson, Seymour and Thomas give a proof of this conjecture for planar digraphs. But for over a decade, this was the most general case proved for the conjecture. Only very recently, this result has been extended to all classes of digraphs excluding a fixed undirected graph as a minor (see [26]). In this paper, nearly two decades after the conjecture was made, we are finally able to confirm the Reed, Johnson, Robertson, Seymour and Thomas conjecture in full generality. As consequence of our results we are able to improve results in Reed et al. in 1996 [36] (see also [33]) on disjoint cycles of length at least 1 and in [24] on quarter-integral disjoint paths. We expect many more algorithmic results to follow from the grid theorem.

关键词： Directed graph Tree Width Grid Minor graph structure theory

来源：评论

学校读者我要写书评

暂无评论

Rao's degree sequence conjecture

引用

JOURNAL OF COMBINATORIAL theory SERIES B 2014年第1期105卷 44-92页

作者： Chudnovsky, Maria Seymour, Paul Columbia Univ New York NY 10027 USA Princeton Univ Princeton NJ 08544 USA

Let us say two (simple) graphs G, G' are degree-equivalent if they have the same vertex set, and for every vertex, its degrees in G and in G' are equal. In the early 1980's, S.B. Rao made the conjecture that in any infinite set of graphs, there exist two of them, say G and H, such that H is isomorphic to an induced subgraph of some graph that is degree-equivalent to G. We prove this conjecture. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Well-quasi-ordering Induced subgraph graph structure theory

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for the Complexity of Monadic Second-Order Logic

Lower Bounds for the Complexity of Monadic Second-Order Logi...

引用

25th Annual IEEE Symposium on Logic in Computer Science (LICS)

作者： Kreutzer, Stephan Tazari, Siamak Univ Oxford Oxford OX1 2JD England Humboldt Univ Berlin Germany

ISBN: (纸本)9780769541143

Courcelle's famous theorem from 1990 states that any property of graphs definable in monadic second-order logic (MSO2) can be decided in linear time on any class of graphs of bounded tree-width, or in other words, MSO2 is fixed-parameter tractable in linear time on any such class of graphs. From a logical perspective, Courcelle's theorem establishes a sufficient condition, or an upper bound, for tractability of MSO2-model checking. Whereas such upper bounds on the complexity of logics have received significant attention in the literature, almost nothing is known about corresponding lower bounds. In this paper we establish a strong lower bound for the complexity of monadic second-order logic. In particular, we show that if C is any class of graphs which is closed under taking sub-graphs and whose tree-width is not bounded by a poly-logarithmic function (in fact, log(c) n for some small c suffices) then MSO2-model checking is intractable on C (under a suitable assumption from complexity theory).

关键词： Courcelle theorem Finite Model theory graph structure theory MSO2-model checking Monadic Second-Order Logic Parameterized Complexity Parameterized Intractability Treewidth bounded tree-width complexity theory computational complexity formal logic formal verification linear time monadic second-order logic poly-logarithmic function trees (mathematics)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：