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

Solving Projected Model Counting by Utilizing Treewidth and its Limits

ARTIFICIAL INTELLIGENCE 2023年 314卷

作者： Fichte, Johannes K. Hecher, Markus Morak, Michael Thier, Patrick Woltran, Stefan TU Wien Database & Artificial Intelligence Grp Favoritenstr 9-11 A-1040 Vienna Austria Univ Klagenfurt Dept Artificial Intelligence & Cybersecur Univ Str 65-67 A-9020 Klagenfurt Am Worthersee Austria

In this paper, we introduce a novel algorithm to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projection variables, where multiple solutions that are identical when restricted to the projection variables count as only one solution. Inspired by the observation that the so-called "treewidth" is one of the most prominent structural parameters, our algorithm utilizes small treewidth of the primal graph of the input instance. More precisely, it runs in time O(22k+4n2) where k is the treewidth and n is the input size of the instance. In other words, we obtain that the problem PMC is fixed-parameter tractable when parameterized by treewidth. Further, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for PMC, yielding asymptotically tight runtime bounds of our algorithm. While the algorithm above serves as a first theoretical upper bound and although it might be quite appealing for small values of k, unsurprisingly a naive implementation adhering to this runtime bound suffers already from instances of relatively small width. Therefore, we turn our attention to several measures in order to resolve this issue towards exploiting treewidth in practice: We present a technique called nested dynamic programming, where different levels of abstractions of the primal graph are used to (recursively) compute and refine tree decompositions of a given instance. Further, we integrate the concept of hybrid solving, where subproblems hidden by the abstraction are solved by classical search-based solvers, which leads to an interleaving of parameterized and classical solving. Finally, we provide a nested dynamic programming algorithm and an implementation that relies on database technology for PMC and a prominent special case of PMC, namely model counting (#SAT). Experiments indicate that the advancements are promising, allowing us to solve instanc

关键词： Tree decompositions High treewidth Lower bounds Exponential time hypothesis Graph problems Boolean logic Counting Projected model counting Nested dynamic programming Hybrid solving parameterized algorithms parameterized complexity Computational complexity Database management systems

来源：评论

学校读者我要写书评

暂无评论

On the complexity of Finding Large Odd Induced Subgraphs and Odd Colorings

引用

ALGORITHMICA 2021年第8期83卷 2351-2373页

作者： Belmonte, Remy Sau, Ignasi Univ Electrocommun Chofu Tokyo Japan Univ Montpellier CNRS LIRMM Montpellier France

We study the complexity of the problems of finding, given a graph G, a largest induced subgraph of G with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition V(G). We call these parameters (G) and chi(odd)(G), respectively. We prove that deciding whether chi(odd)(G) <= q is polynomial-time solvable if q = 2, and NP-complete otherwise. We provide algorithms in time 2O(rw) center dot nO(1) and 2O(q center dot rw) center dot nO(1) to compute chi(odd)(G) and to decide whether chi(odd)(G) = q on n-vertex graphs of rank-width at most rw, respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters.

关键词： Odd subgraph Odd coloring Rank-width parameterized complexity Single-exponential algorithm Exponential time hypothesis

来源：评论

学校读者我要写书评

暂无评论

Balanced stable marriage: How close is close enough?

引用

THEORETICAL COMPUTER SCIENCE 2021年 883卷 19-43页

作者： Gupta, Sushmita Roy, Sanjukta Saurabh, Saket Zehavi, Meirav HBNI Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel

BALANCED STABLE MARRIAGE (BSM) is a central optimization version of the classic STABLE Marriage (SM) problem. We study BSM from the viewpoint of parameterized complexity. Informally, the input of BSM consists of n men, n women, and an integer k. Each person a has a (sub)set of acceptable partners, A(a), whom a ranks strictly;we use p(a)(b) to denote the position of b is an element of A(a) in a's preference list. The objective is to decide whether there exists a stable matching mu such that balance (mu) (sic) max{Sigma((m,w)is an element of mu)p(m)(w), Sigma((m,w)is an element of mu)p(w)(m)} <= k. In SM, all stable matchings match the same set of agents, A* which can be computed in polynomial time. As balance(mu) = vertical bar A*vertical bar/2 for any stable matching mu, BSM is trivially fixed-parameter tractable (FPT) with respect to k. Thus, a natural question is whether BSM is FPT with respect to k - vertical bar A*vertical bar/2. With this viewpoint in mind, we draw a line between tractability and intractability in relation to the target value. This line separates additional natural parameterizations higher/lower than ours (e.g., we automatically resolve the parameterization k - vertical bar A*vertical bar/2). The two extreme stable matchings are the man-optimal mu(M) and the woman-optimal mu(W). Let O-M = Sigma((m, w)is an element of mu M)p(m)(w), and O-W = Sigma((m,w)is an element of mu W)p(w)(m). In this work, we prove that BSM parameterized by t = k - min{O-M, O-W} admits (1) a kernel where the number of people is linear in t, and (2) a parameterized algorithm whose running time is single exponential in t. BSM parameterized by t = k - max{O-M, O-W} is W[1]-hard. (C) 2021 Published by Elsevier B.V.

关键词： balanced stable marriage parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

Incidence, a scoring positional game on graphs

引用

DISCRETE MATHEMATICS 2024年第8期347卷

作者： Bagan, Guillaume Deschamps, Quentin Duchene, Eric Durain, Bastien Effantin, Brice Gledel, Valentin Oijid, Nacim Parreau, Aline Univ Lyon 1 Univ Lyon LIRIS CNRS 5205UMR F-69621 Lyon France Ecole Normale Super Lyon F-69364 Lyon 07 France Umea Univ Dept Math & Math Stat Umea Sweden

Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the MakerBreaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins, and if no one manages to do it, the game ends by a draw. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on INCIDENCE, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of INCIDENCE is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Positional game Scoring game Graphs Milnor's universe parameterized complexity Hypergraphs

来源：评论

学校读者我要写书评

暂无评论

Streaming deletion problems parameterized by vertex cover

引用

THEORETICAL COMPUTER SCIENCE 2023年 979卷

作者： Oostveen, Jelle J. van Leeuwen, Erik Jan Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands

Streaming is a model where an input graph is provided one edge at a time, instead of being able to inspect it at will. In this work, we take a parameterized approach by assuming a vertex cover of the graph is given, building on work of Bishnu et al. [COCOON 2020]. We show the further potency of combining this parameter with the Adjacency List streaming model to obtain results for vertex deletion problems. This includes kernels, parameterized algorithms, and lower bounds for the problems of TI-FREE DELETION, H-FREE DELETION, and the more specific forms of CLUSTER VERTEX DELETION and ODD CYCLE TRANSVERSAL. We focus on the complexity in terms of the number of passes over the input stream, and the memory used. This leads to a pass/memory trade-off, where a different algorithm might be favourable depending on the context and instance. We also discuss implications for parameterized complexity in the non-streaming setting.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Graph streaming parameterized complexity Vertex cover Vertex deletion

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for BICLUSTER EDITING and FLIP CONSENSUS TREE

引用

THEORETICAL COMPUTER SCIENCE 2023年 953卷

作者： Tsur, Dekel Ben Gurion Univ Negev Beer Sheva Israel

In the BICLUSTER EDITING (resp., FLIP CONSENSUS TREE) problem the input is a bipartite graph G = (V1, V2, E) and an integer k, and the goal is to decide whether there is a set F c V1 X V2 such that the graph (V1, V2, EAF) does not contain an induced path on four vertices (resp., an induced path on five vertices whose endpoints are in V2). In this paper we give algorithms for BICLUSTER EDITING and FLIP CONSENSUS TREE whose running times are O *(2.22k) and O(3.24k), respectively. This improves over the O *(2.636k)-time algorithm for BICLUSTER EDITING of Tsur [IPL 2021] and the O*(3.68k)-time algorithm for FLIP CONSENSUS TREE of Komusiewicz and Uhlmann [Algorithmica 2014].(c) 2023 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized complexity Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

Deletion to scattered graph classes I-Case of finite number of graph classes

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年第1期138卷

作者： Jacob, Ashwin de Kroon, Jari J. H. Majumdar, Diptapriyo Raman, Venkatesh Ben Gurion Univ Negev Beer Sheva Israel Eindhoven Univ Technol Eindhoven Netherlands Indraprastha Inst Informat Technol Delhi New Delhi India HBNI Inst Math Sci Chennai India

Graph-deletion problems involve deleting a small number of vertices so that the resulting graph belong to a given hereditary graph class. We initiate a study of a natural variation of the problem of deletion to scattered graph classes. We want to delete at most k vertices so that each connected component of the resulting graph belongs to one of the constant number of graph classes. As our main result, we show that this problem is non-uniformly fixed-parameter tractable (FPT) when the deletion problem corresponding to each of the constant number of graph classes is known to be FPT and the properties that a graph belongs to these classes are expressible in Counting Monodic Second Order (CMSO) logic. While this is shown using some black box theorems in parameterized complexity, we give a faster FPT algorithm when each of the graph classes has a finite forbidden set. & COPY;2023 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Fixed parameter tractability Scattered graph classes Important separators

来源：评论

学校读者我要写书评

暂无评论

Faster deterministic algorithm for Cactus Vertex Deletion

引用

INFORMATION PROCESSING LETTERS 2023年 179卷

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the CACTUS VERTEX DELETION (resp., EVEN CYCLE TRANSVERSAL) problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices whose removal from G results in a graph in which every edge belongs to at most one cycle (resp., a graph without even cycles). In this paper we give deterministic O *(13.69k)-time algorithms for CACTUS VERTEX DELETION and EVEN CYCLE TRANSVERSAL.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Algorithms Graph algorithms parameterized complexity Branching algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Computational Difficulty of the Terminal Connection Problem*

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2023年第1期57卷 3-3页

作者： de Melo, Alexsander A. de Figueiredo, Celina M. H. Souza, Ueverton S. Fed Univ Rio Janeiro Rio De Janeiro Brazil Fluminense Fed Univ Niteroi Brazil

A connection tree of a graph G for a terminal set W is a tree subgraph T of G such that leaves(T) subset of W subset of V(T). A non-terminal vertex is called linker if its degree in T is exactly 2, and it is called router if its degree in T is at least 3. The Terminal connection problem (TCP) asks whether G admits a connection tree for W with at most l linkers and at most r routers, while the Steiner tree problem asks whether G admits a connection tree for W with at most k non-terminal vertices. We prove that, if r >= 1 is fixed, then TCP is polynomial-time solvable when restricted to split graphs. This result separates the complexity of TCP from the complexity of Steiner tree, which is known to be NP-complete on split graphs. Additionally, we prove that TCP is NP-complete on strongly chordal graphs, even if r >= 0 is fixed, whereas Steiner tree is known to be polynomial-time solvable. We also prove that, when parameterized by clique-width, TCP is W[1]-hard, whereas STeiner tree is known to be in FPT. On the other hand, agreeing with the complexity of Steiner tree, we prove that TCP is linear-time solvable when restricted to cographs (i.e. graphs of clique-width 2). Finally, we prove that, even if either l >= 0 or r >= 0 is fixed, TCP remains NP-complete on graphs of maximum degree 3.

关键词： Computational difficulty of problems parameterized complexity terminal vertices connection tree steiner tree split graphs strongly chordal graphs cographs bounded degree

来源：评论

学校读者我要写书评

暂无评论

Interference-free walks in time: temporally disjoint paths

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2023年第1期37卷 1-1页

作者： Klobas, Nina Mertzios, George B. Molter, Hendrik Niedermeier, Rolf Zschoche, Philipp Univ Durham Dept Comp Sci Upper Mountjoy CampusStockton Rd Durham DH1 3LE England Ben Gurion Univ Negev Dept Ind Engn & Management David Ben Gurion Blvd IL-84105 Beer Sheva Israel TU Berlin Fac 4 Algorithm & Computat Complex Ernst Reuter Pl 7 D-10587 Berlin Germany

We investigate the computational complexity of finding temporally disjoint paths and walks in temporal graphs. There, the edge set changes over discrete time steps. Temporal paths and walks use edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never visit the same vertex at the same time;otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. At one extreme, we show that on general graphs the problem is computationally hard. The path version is NP-hard even if we want to find only two temporally disjoint paths. The walk version is W-hard (Klobas in IJCAI 4090-4096, 2021) when parameterized by the number of walks. However, it is polynomial-time solvable for any constant number of walks. At the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counter-intuitively, we find NP-hardness in general but also identify natural tractable cases.

关键词： Temporal graph Temporal path NP-complete problem parameterized complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：