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

A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths

NETWORKS 2019年第1期73卷 23-37页

作者： Bazgan, Cristina Fluschnik, Till Nichterlein, Andre Niedermeier, Rolf Stahlberg, Maximilian PSL Res Univ Univ Paris Dauphine CNRS LAMSADE Paris France Tech Univ Berlin Inst Softwaretech & Theoret Informat Berlin Germany

We study the NP-hard shortest path most vital edges problem arising in the context of analyzing network robustness. For an undirected graph with positive integer edge lengths and two designated vertices s and t, the goal is to delete as few edges as possible in order to increase the length of the (new) shortest st-path as much as possible. This scenario has been studied from the viewpoint of parameterized complexity and approximation algorithms. We contribute to this line of research by providing refined computational tractability as well as hardness results. We achieve this by a systematic investigation of various problem-specific parameters and their influence on the computational complexity. Charting the border between tractability and intractability, we also identify numerous challenges for future research.

关键词： approximation algorithms interdiction problems length-bounded cuts NP-hardness parameterized complexity special graph classes

来源：评论

学校读者我要写书评

暂无评论

HITTING MINORS ON BOUNDED TREEWIDTH GRAPHS. IV. AN OPTIMAL ALGORITHM

引用

SIAM JOURNAL ON COMPUTING 2023年第4期52卷 865-912页

作者： Baste, Julien Sau, Ignasi Thilikos, Dimitrios M. Univ Lille CRIStAL Ctr Rech Informat Signal & Automatique Lil CNRSUMR 9189 Cent Lille F-59000 Lille France Univ Montpellier LIRMM CNRS Montpellier France

For a fixed finite collection of graphs F, the F-M-Deletion problem is as follows: given an n-vertex input graph G, find the minimum number of vertices that intersect all minor models in G of the graphs in F. by Courcelle's Theorem, this problem can be solved in time f(F)(tw) center dot n(O(1)), where tw is the treewidth of G for some function f(F) depending on F. In a recent series of articles, we have initiated the program of optimizing asymptotically the function f(F). Here we provide an algorithm showing that f(F) (tw) = 2(O(*** tw)) for every collection F. Prior to this work, the best known function f(F) was double-exponential in tw. In particular, our algorithm vastly extends the results of Jansen, Lokshtanov, and Saurabh [Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2014, pp. 1802-1811] for the particular case F = {K-5, K-3,K-3} and of Kociumaka and Pilipczuk [Algorithmica, 81 (2019), pp. 3655-3691] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [Inform. Comput., 256 (2017), pp. 62-82]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections F [J. Baste, I. Sau, and D. M. Thilikos, Theoret. Comput. Sci., 814 (2020), pp. 135-152] and general lower bounds [J. Baste, I. Sau, and D. M. Thilikos, J. Comput. Syst. Sci., 109 (2020), pp. 56-77], our algorithm yields the following complexity dichotomy when F = {H} contains a single connected graph H, assuming the Exponential Time Hypothesis: f(H)(tw) = 2(Theta(tw)) if H is a contraction of the chir or the bammer, and f(H)(tw) = 2(Theta(*** tw)) otherwise.

关键词： parameterized complexity graph minors treewidth dynamic programming hitting minors irrelevant vertex

来源：评论

学校读者我要写书评

暂无评论

The complexity of finding small separators in temporal graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年 107卷 72-92页

作者： Zschoche, Philipp Fluschnik, Till Molter, Hendrik Niedermeier, Rolf TU Berlin Algorithm & Computat Complex Fac 4 Berlin Germany

Temporal graphs have time-stamped edges. Building on previous work, we study the problem of finding a small vertex set (the separator) whose removal destroys all temporal paths between two designated terminal vertices. Herein, we consider two models of temporal paths: those that pass through arbitrarily many edges per time step (non-strict) and those that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-completeness versus polynomial-time solvability) for both problem variants. Moreover, we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. Finally, we introduce the notion of a temporal core (vertices whose incident edges change over time) and prove that the non-strict variant is fixed-parameter tractable when parameterized by the temporal core size, while the strict variant remains NP-complete, even for constant-size temporal cores. (C) 2019 Elsevier Inc. All rights reserved.

关键词： (Non-)strict temporal paths Temporal core Single-source shortest paths problem Single-source shortest strict temporal path Node multiway cut Length-bounded cuts parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Simultaneous Feedback Edge Set: A parameterized Perspective

引用

ALGORITHMICA 2021年第2期83卷 753-774页

作者： Agrawal, Akanksha Panolan, Fahad Saurabh, Saket Zehavi, Meirav Univ Bergen Dept Informat Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel IIT Hyderabad Dept Comp Sci & Engn Sangareddy India HBNI Inst Math Sci Chennai Tamil Nadu India

Agrawal et al. (ACM Trans Comput Theory 10(4):18:1-18:25, 2018. https://doi. org/10.1145/3265027) studied a simultaneous variant of the classic FEEDBACK Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). Here, we consider the edge variant of the problem, namely, Simultaneous Feedback Edge SET (SIM-FES). In this problem, the input is an n-vertex graph G, a positive integer k, and a coloring function col: E(G) -> 2([alpha]), and the objective is to check whether there is an edge subset S of cardinality k in G such that for each i is an element of [alpha], G(i) - S is acyclic. Unlike the vertex variant of the problem, when alpha = 1, the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for alpha = 3, Sim-FES is NP-hard, and does not admit an algorithm of running time 2(o(k))n(O(1)) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time 2(omega k alpha+alpha log k)n(O(1)) where omega is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when alpha = 2. We also give a kernel for Sim-FES with (k alpha)(O(alpha)) vertices. Finally, we consider a "dual" version of the problem called Maximum Simultaneous Acyclic Subgraph and give an FPT algorithm with running time 2(omega q alpha) n(O(1)), where q is the number of edges in the output subgraph.

关键词： parameterized complexity Feedback edge set alpha-matroid parity

来源：评论

学校读者我要写书评

暂无评论

Structural Parameterizations of Undirected Feedback Vertex Set: FPT Algorithms and Kernelization

引用

ALGORITHMICA 2018年第9期80卷 2683-2724页

作者： Majumdar, Diptapriyo Raman, Venkatesh HBNI Inst Math Sci Madras Tamil Nadu India

A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the input. In particular, we consider parameterizations where the parameter is (instead of the solution size), the distance to a class of graphs where the problem is polynomial time solvable, and sometimes smaller than the solution size. Here, by distance to a class of graphs, we mean the minimum number of vertices whose removal results in a graph in the class. Such a set of vertices is also called the 'deletion set'. In this paper, we show that FVS is fixed-parameter tractable by an time algorithm, but is unlikely to have polynomial kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper. We also show that an algorithm with running time is not possible unless SETH fails. When parameterized by k, the number of vertices, whose deletion results in a split graph, we give an time algorithm. When parameterized by k, the number of vertices whose deletion results in a cluster graph (a disjoint union of cliques), we give an algorithm. When parameterized by k, the number of vertices, whose deletion results in a pseudo-forest, FVS has an vertices kernel improving from the previously known bound. When parameterized by the number k of vertices, whose deletion results in a mock-d-forest, we give a kernel with vertices. We also prove a lower bound of size (under complexity theoretic assumptions). Mock-forest is a graph where each vertex is contained in at most one cycle. Mock-d-forest for a constant d is a mock-forest where each component has at most d cycles.

关键词： parameterized complexity Kernelization Feedback vertex set Structural parameterization W-hardness

来源：评论

学校读者我要写书评

暂无评论

Turing kernelization for finding long paths and cycles in restricted graph classes

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 85卷 18-37页

作者： Jansen, Bart M. P. Eindhoven Univ Technol NL-5600 MB Eindhoven Netherlands

The k-PATH problem asks whether a given undirected graph has a (simple) path of length k. We prove that k-PATH has polynomial-size Turing kernels when restricted to planar graphs, graphs of bounded degree, claw-free graphs, or to K-3,K-t-minor-free graphs. This means that there is an algorithm that, given a k-PATH instance (G, k) belonging to one of these graph classes, computes its answer in polynomial time when given access to an oracle that solves k-PATH instances of size polynomial in k in a single step. Our techniques also apply to k-CYCLE, which asks for a cycle of length at least k. (C) 2016 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Turing kernelization k-PATH Preprocessing

来源：评论

学校读者我要写书评

暂无评论

The complexity of Finding Effectors

引用

THEORY OF COMPUTING SYSTEMS 2017年第2期60卷 253-279页

作者： Bulteau, Laurent Fafianie, Stefan Froese, Vincent Niedermeier, Rolf Talmon, Nimrod Univ Paris Est Marne La Vallee CNRS UMR 8049 IGM LabInfo Marne La Vallee France Univ Bonn Inst Informat Bonn Germany Weizmann Inst Sci Rehovot Israel TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

The NP-hard Effectors problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation processes in social networks. In the corresponding model the arcs carry probabilities and there is a probabilistic diffusion process activating nodes by neighboring activated nodes with probabilities as specified by the arcs. The point is to explain a given network activation state as well as possible by using a minimum number of "effector nodes";these are selected before the activation process starts. We correct, complement, and extend previous work from the data mining community by a more thorough computational complexity analysis of Effectors, identifying both tractable and intractable cases. To this end, we also exploit a parameterization measuring the "degree of randomness" (the number of 'really' probabilistic arcs) which might prove useful for analyzing other probabilistic network diffusion problems as well.

关键词： Probabilistic information propagation Influence maximization etwork activation Social networks Exact algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover

引用

THEORETICAL COMPUTER SCIENCE 2012年 452卷 39-46页

作者： Damaschke, Peter Molokov, Leonid Chalmers Univ Technol Dept Comp Sci & Engn S-41296 Gothenburg Sweden

We study a novel generalization of the VERTEX COVER problem which is motivated by, e.g., error correction (data cleaning) prior to inference of chemical mixtures by their observable reaction products. We focus on the important case of deciding on one of two candidate substances. This problem has nice graph-theoretic formulations situated between VERTEX COVER and 3-HITTING SET. In order to characterize its parameterized complexity we devise parameter-preserving reductions, and we show that some minimum solution can be computed faster than by solving 3-HITTING SET in general. More explicitly, we introduce the UNION EDITING problem: In a hypergraph with red and blue vertices, edit the colors so that the red set becomes exactly the union of some hyperedges. The case of degree 2 is equivalent to STAR EDITING: in a graph with red and blue edges, edit the colors so that the red set becomes exactly the union of some stars, i.e., vertices with all their incident edges. Our time bound is O*(1.84(c)) where c denotes the total number of recolored edges. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Vertex cover Hitting set Graph editing Error correction parameterized complexity Problem kernel

来源：评论

学校读者我要写书评

暂无评论

Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight complexity Bounds

引用

ACM TRANSACTIONS ON ALGORITHMS 2024年第2期20卷 1-32页

作者： Focke, Jacob Marx, Daniel Rzazewski, Pawel CISPA Helmholtz Ctr Informat Secur Stuhlsatzenhaus 5 Saarbucken Germany Warsaw Univ Technol Fac Math & Informat Sci Koszykowa 75 Warsaw Poland Warsaw Inst Informat Banacha 2 PL-02097 Warsaw Poland

The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs G, H, and lists L(v) subset of V (H) for every v is an element of V (G), a list homomorphism is a function f : V (G) -> V (H) that preserves the edges (i.e., uv is an element of E(G) implies f (u)f (v) is an element of E(H)) and respects the lists (i.e., f (v) is an element of L(v)). Standard techniques show that if G is given with a tree decomposition of width t, then the number of list homomorphisms can be counted in time vertical bar V(H)vertical bar(t) center dot n(O(1)). Our main result is determining, for every fixed graph H, how much the base |V(H)| in the running time can be improved. For a connected graph H, we define irr(H) in the following way: if H has a loop or is nonbipartite, then irr(H) is the maximum size of a set S subset of V (H) where any two vertices have different neighborhoods;if H is bipartite, then irr(H) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected H, we define irr(H) as the maximum of irr(C) over every connected component C of H. It follows from earlier results that if irr(H) = 1, then the problem of counting list homomorphisms to H is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph H, the number of list homomorphisms from (G, L) to H

关键词： Graph homomorphism list homomorphism counting complexity parameterized complexity tight bounds treewidth

来源：评论

学校读者我要写书评

暂无评论

SUBEXPONENTIAL parameterized ALGORITHMS FOR PLANAR AND APEX-MINOR-FREE GRAPHS VIA LOW

引用

SIAM JOURNAL ON COMPUTING 2022年第6期51卷 1866-1930页

作者： Fomin, Fedor, V Lokshtanov, Daniel Marx, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA CISPA Helmholtz Ctr Informat Secur Saarland Informat Campus D-66123 Saarbrucken Germany Univ Warsaw Inst Informat PL-02097 Warsaw Poland Inst Math Sci Chennai 600113 India

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: A induces a subgraph of G of treewidth O( k log k), and for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2\scrO ( k log2 k) . n\scrO (1)) - 1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, usually with running time bound 2\scrO ( k log2 k)n\scrO (1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host LOCAL SEARCH, and SUBGRAPH ISOMORPHISM, among others. Up to this point, it was open whether these problems could be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

关键词： parameterized complexity subexponential algorithms treewidth planar graphs subgraph isomorphism

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：