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

16th International Symposium on Algorithmic Game Theory (SAGT)

作者： Fraser, Andrew Lavallee, Brian Sullivan, Blair D. Univ Utah Salt Lake City UT 84112 USA

ISBN: (纸本)9783031432538;9783031432545

In a representative democracy, the electoral process involves partitioning geographical space into districts which each elect a single representative. These representatives craft and vote on legislation, incentivizing political parties to win as many districts as possible (ideally a plurality). Gerrymandering is the process by which district boundaries are manipulated to the advantage of a desired candidate or party. We study the parameterized complexity of Gerrymandering, a graph problem (as opposed to Euclidean space) formalized by Cohen-Zemach et al. (AAMAS 2018) and Ito et al. (AAMAS 2019) where districts partition vertices into connected subgraphs. We prove that Gerrymandering is W[2]-hard on trees (even when the depth is two) with respect to the number of districts k. Moreover, we show that Gerrymandering remains W[2]-hard in trees with l leaves with respect to the combined parameter k + l. In contrast, Gupta et al. (SAGT 2021) give an FPT algorithm for paths with respect to k. To complement our results and fill this gap, we provide an algorithm to solve Gerrymandering that is FPT in k when l is a fixed constant.

关键词： gerrymandering parameterized complexity graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Path Set Packing 17th

Parameterized Complexity of Path Set Packing

引用

17th International Conference and Workshops on Algorithms and Computation

作者： Aravind, N. R. Saxena, Roopam IIT Hyderabad Dept Comp Sci & Engn Hyderabad India

ISBN: (纸本)9783031270505;9783031270512

In PATH SET PACKING, the input is an undirected graph G, a collection P of simple paths in G, and a positive integer k. The problem is to decide whether there exist k edge-disjoint paths in P. We study the parameterized complexity of PATH SET PACKING with respect to both natural and structural parameters. We show that the problem is W[1]-hard with respect to vertex cover plus the maximum length of a path in P, and W[1]-hard with respect to pathwidth plus maximum degree plus solution size. These results answer an open question raised in [17]. On the positive side, we present an FPT algorithm parameterized by feedback vertex set plus maximum degree, and also provide an FPT algorithm parameterized by treewidth plus maximum degree plus maximum length of a path in P.

关键词： Path set packing Set packing parameterized complexity Fixed parameter tractability Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Broadcasting in Graphs 49th

Parameterized Complexity of Broadcasting in Graphs

引用

49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Fomin, Fedor V. Fraigniaud, Pierre Golovach, Petr A. Univ Bergen Dept Informat Bergen Norway Univ prime Paris Cite Inst Rech Informat Fondamentale Paris France CNRS Paris France

ISBN: (纸本)9783031433795;9783031433801

The task of the broadcast problem is, given a graph G and a source vertex s, to compute the minimum number of rounds required to disseminate a piece of information from s to all vertices in the graph. It is assumed that, at each round, an informed vertex can transmit the information to at most one of its neighbors. The broadcast problem is known to be NP-hard. We show that the problem is FPT when parametrized by the size k of a feedback edge set, or by the size k of a vertex cover, or by k = n- t, where t is the input deadline for the broadcast protocol to complete.

关键词： broadcasting telephone model parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Simultaneous Planarity 31st

Parameterized Complexity of Simultaneous Planarity

引用

31st International Symposium on Graph Drawing and Network Visualization (GD)

作者： Fink, Simon D. Pfretzschner, Matthias Rutter, Ignaz Univ Passau Fak Informat & Math Passau Germany

ISBN: (纸本)9783031492747;9783031492754

Given k input graphs G((1)),..., G((k)), where each pair G((i)), G((j)) with i not equal j shares the same graph G, the problem SIMULTANEOUS EMBEDDING WITH FIXED EDGES (SEFE) asks whether there exists a planar drawing for each input graph such that all drawings coincide on G. While SEFE is still open for the case of two input graphs, the problem is NP-complete for k >= 3 [18]. In this work, we explore the parameterized complexity of SEFE. We show that SEFE is FPT with respect to k plus the vertex cover number or the feedback edge set number of the union graph G(boolean OR) = G((1)) boolean OR center dot center dot center dot boolean OR G((k)). Regarding the shared graph G, we show that SEFE is NP-complete, even if G is a tree with maximum degree 4. Together with a known NP-hardness reduction [1], this allows us to conclude that several parameters of G, including the maximum degree, the maximum number of degree-1 neighbors, the vertex cover number, and the number of cutvertices are intractable. We also settle the tractability of all pairs of these parameters. We give FPT algorithms for the vertex cover number plus either of the first two parameters and for the number of cutvertices plus the maximum degree, whereas we prove all remaining combinations to be intractable.

关键词： Simultaneous Planarity SEFE parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Bend-Minimum Orthogonal Planarity

引用

ALGORITHMICA 2024年第10期86卷 3231-3251页

作者： Di Giacomo, Emilio Didimo, Walter Liotta, Giuseppe Montecchiani, Fabrizio Ortali, Giacomo Univ Perugia Dept Engn Perugia Italy

Computing planar orthogonal drawings with the minimum number of bends is one of the most studied topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia in SIAM J Comput 31(2):601-625, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number b of bends, the number k of vertices of degree at most two, and the treewidth tw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{tw}$$\end{document} of the input graph (Di Giacomo et al. in J Comput Syst Sci 125:129-148, 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by b+k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b+k$$\end{document}. As a consequence, rectilinear planarity testing lies in FPT parameterized by the number of vertices of degree at most two. We also prove that our choice of parameters is minimal, as deciding if an orthogonal drawing with at most b bends exists is already NP-hard when k is zero (i.e., the problem is para-NP-hard parameterized in k);hence, there is neither an FPT nor an XP algorithm parameterized only by the parameter k (unless P = NP). In addition, we prove that the problem is W[1]-hard parameterized by k+tw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{

关键词： Orthogonal drawings Bend minimization parameterized complexity FPT algorithms

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of SPARSEST CUT and SMALL-SET EXPANSION problems

引用

DISCRETE APPLIED MATHEMATICS 2024年 355卷 1-12页

作者： Javadi, Ramin Nikabadi, Amir Isfahan Univ Technol Dept Math Sci POB 84156-83111 Esfahan Iran Inst Res Fundamental Sci IPM Sch Math POB 19395-5746 Tehran Iran Univ Paris 09 Univ PSL CNRS LAMSADE F-75016 Paris France

We present a parameterized dichotomy for the k-SPARSEST CUT problem in weighted and unweighted versions. In particular, we show that the weighted k-SPARSEST CUT problem is NP-hard for every k >= 3 even on graphs with bounded vertex cover number. Also, the unweighted k-SPARSEST CUT problem is W[1]-hard when parameterized by the three combined parameters tree-depth, feedback vertex set number, and k. On the positive side, we show that the unweighted k-SPARSEST CUT problem is FPT when parameterized by the vertex cover number and k, and when k is fixed, it is FPT with respect to the treewidth. Moreover, we show that the generalized version kappa-SMALL-SET EXPANSION problem is FPT when parameterized by kappa and the maximum degree of the graph, though it is W[1]-hard for each of these parameters separately. (c) 2024 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Sparsest Cut Vertex cover Treewidth Small-set expansion

来源：评论

学校读者我要写书评

暂无评论

Contraction Decomposition in Unit Disk Graphs and Algorithmic Applications in parameterized complexity

引用

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

作者： Panolan, Fahad Saurabh, Saket Zehavi, Meirav Indian Inst Technol IIT Dept Comp Sci & Engn Hyderabad India HBNI Inst Math Sci Theoret Comp Sci Grp Chennai Tamil Nadu India Univ Bergen Algorithms Grp Bergen Norway Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

We give a new decomposition theorem in unit disk graphs ( UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and parameterized complexity. First, our new decomposition theorem shows that the class of UDGs admits an "almost" Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010], and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, and therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi (***/watch?v=2Bq2gy1N01w) regarding the existence of contraction decompositions for classes of graphs beyond H-minor free graphs though under a relaxation of the original formulation. Second, we present a "parameteric version" of our new decomposition theorem. We prove that there is an algorithm that, given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of O(k) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into O(k) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece that is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or sligh

关键词： parameterized complexity contraction decomposition unit disk graph Min bisection

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Compact Set Packing

引用

ALGORITHMICA 2024年第11期86卷 3579-3597页

作者： Gadekar, Ameet Bar Ilan Univ Dept Comp Sci Ramat Gan Israel

The Set Packing problem is, given a collection of sets S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {S}$$\end{document} over a ground set U, to find a maximum collection of sets that are pairwise disjoint. The problem is among the most fundamental NP-hard optimization problems that have been studied extensively in various computational regimes. The focus of this work is on parameterized complexity, parameterized Set Packing (PSP): Given parameter r is an element of N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r \in {\mathbb N}$$\end{document}, is there a collection S 'subset of S:|S '|=r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathcal {S}' \subseteq \mathcal {S}: |\mathcal {S}'| = r$$\end{document} such that the sets in S '\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {S}'$$\end{document} are pairwise disjoint? Unfortunately, the problem is not fixed parameter tractable unless W[1]=FPT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {W[1]} = \textsf {FPT} $$\end{document}, and, in fact, an "enumerative" running time of |S|Omega(r)

关键词： parameterized complexity Set packing

来源：评论

学校读者我要写书评

暂无评论

ON THE parameterized complexity OF DELETION TO H-FREE STRONG COMPONENTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第4期38卷 3079-3110页

作者： Neogi, Rian Ramanujan, M. S. Saurabh, Saket Sharma, Roohani Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada Univ Warwick Dept Comp Sci Warwick England HBNI Inst Math Sci Theoret Comp Sci Grp Mumbai Maharashtra India Univ Bergen Bergen Norway Univ Bergen Dept Informat Bergen Norway

Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received a lot of attention in parameterized complexity. In this paper, we initiate the study of a wide generalization of this problem called the H-free Strong Connected Component Deletion problem, where H is a finite family of digraphs. Here, one is given a digraph D and an integer k, and the objective is to decide whether there is a vertex set of size at most k whose deletion results in a digraph where every strongly connected component excludes graphs in family H as (not necessarily induced) subgraphs. When H comprises only the digraph with a single arc, then this problem is precisely the DFVS problem. Our main result is a proof that this problem is fixedparameter tractable parameterized by the size of the deletion set if H only contains rooted graphs or if H contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the results of Goke, Marx, and Mnich [Proceedings of the International Conference on Algorithms and complexity, Springer, 2019, pp. 249-261] for the 1-Out-Regular Vertex Deletion and Bounded Size Strong Component Vertex Deletion problems. Moreover, we design algorithms for the two above-mentioned problems, whose running times are better and that match with the best bounds for DFVS, without using the heavy machinery of shadow removal as is done by Goke, Marx, and Mnich [Proceedings of the International Conference on Algorithms and complexity, Springer, 2019, pp. 249-261].

关键词： directed feedback vertex set parameterized complexity deletion to H-free strong components important separators

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of non-hereditary relaxations of clique

引用

THEORETICAL COMPUTER SCIENCE 2024年 1003卷

作者： Baril, Ambroise Castillon, Antoine Oijid, Nacim Univ Lorraine CNRS LORIA Lorraine France Univ Lille CNRS Cent Lille UMR 9189CRIStAL F-59000 Lille France Univ Lyon 1 Univ Lyon LIRIS UMR CNRS 5205 F-69621 Lyon France

We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words, we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here three relaxations of C LIQUE : s -C LUB and s -C LIQUE , in which the relaxation is focused on the distances in respectively the cluster and the original graph, and y -C OMPLETE S UBGRAPH in which the relaxation is made on the minimal degree in the cluster. As these three problems are known to be NP -hard, we study here their parameterized complexities. We prove that s -C LUB and s -C LIQUE are NP -hard even restricted to graphs of degeneracy <= 3 whenever s >= 3 , and to graphs of degeneracy <= 2 whenever s >= 5 , which is a strictly stronger result than its W[1] -hardness parameterized by the degeneracy. Concerning y -C OMPLETE S UBGRAPH , we prove that it is W[1] -hard parameterized both by the degeneracy, implying the W[1] -hardness parameterized by the number of vertices in the y-complete-subgraph, and by the number of elements outside the y -complete subgraph.

关键词： Graphs complexity Clique parameterized complexity W[1]-hardness Para-NP hardness

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：