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

TIGHT BOUNDS FOR PLANAR STRONGLY CONNECTED STEINER SUBGRAPH WITH FIXED NUMBER OF TERMINALS (AND EXTENSIONS)

SIAM JOURNAL ON COMPUTING 2020年第2期49卷 318-364页

作者： Chitnis, Rajesh H. Feldmann, Andreas E. Hajiaghayi, Mohammadtaghi Marx, Daniel Univ Birmingham Dept Comp Sci Birmingham B15 2TT W Midlands England Charles Univ Prague Dept Appl Math Prague 11800 Czech Republic Univ Maryland Dept Comp Sci College Pk MD 20742 USA Max Planck Inst Informat Saarbrucken Saarland Germany

Given a vertex-weighted directed graph G = (V, E) and a set T = {t(1), t(2), ..., t(k)} of k terminals, the objective of the STRONGLY CONNECTED STEINER SUBGRAPH (SCSS) problem is to find a vertex set H subset of V of minimum weight such that G[H] contains a t(i) -> t(j) path for each i not equal j. The prob- lem is NP-hard, but Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543-561] gave a novel n(O(k)) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a 2(O(k)).n(O(root k)) algorithm for planar SCSS, which is an improvement of a factor of O(root k) in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k).n(o(root k)) algorithm for any computable function f, unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is O(root k), and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, preprint, https://***/abs/1707.06808] . To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our 2(O(k)).n(O(root k)) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the n(O(k)) algorithm of Feldman and R

关键词： strongly connected Steiner subgraph fpt algorithms directed Steiner network exponential time hypothesis planar graphs

来源：评论

学校读者我要写书评

暂无评论

On the Parameterized Complexity of Maximum Degree Contraction Problem

引用

ALGORITHMICA 2022年第2期84卷 405-435页

作者： Saurabh, Saket Tale, Prafullkumar Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

In the MAXIMUM DEGREE CONTRACTION problem, the input is a graph G on n vertices, and integers k, d, and the objective is to check whether G can be transformed into a graph of maximum degree at most d, using at most k edge contractions. A simple brute-force algorithm that checks all possible sets of edges for a solution runs in time n(O(k)). As our first result, we prove that this algorithm is asymptotically optimal, upto constants in the exponents, under Exponential Time Hypothesis (ETH). Belmonte, Golovach, van't Hof, and Paulusma studied the problem in the realm of parameterized complexity and proved, among other things, that it admits an fpt algorithm running in time (d + k)(2k) . n(O(1)) = 2(O(k log(k+d))) . n(O(1)), and remains NP-hard for every constant d >= 2 (Acta Informatica (2014)). We present a different fpt algorithm that runs in time 2(O(dk)) . n(O(1)). In particular, our algorithm runs in time 2(O(k)) . n(O(1)), for every fixed d. In the same article, the authors asked whether the problem admits a polynomial kernel, when parameterized by k + d. We answer this question in the negative and prove that it does not admit a polynomial compression unless NP subset of coNP/poly.

关键词： Graph contraction Maximum degree contraction Parameterized complexity fpt algorithms No-poly Kernel ETH-lower bound

来源：评论

学校读者我要写书评

暂无评论

Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time

引用

ACM TRANSACTIONS ON algorithms 2017年第4期13卷 1–26页

作者： Bjorklund, Andreas Kaski, Petteri Kowalik, Lukasz Lund Univ Dept Comp Sci LTH Box 118 SE-22100 Lund Sweden Aalto Univ HIIT Dept Informat & Comp Sci Aalto Finland Univ Warsaw Inst Informat Banacha 2 PL-02097 Warsaw Poland Aalto Univ Dept Comp Sci POB 15400 FI-00076 Aalto Finland

Vassilevska and Williams (STOC'09) showed how to count simple paths on k vertices and matchings on k/2 edges in ann-vertex graph in time n(k/2+O(1)). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP'09), and Bjorklund et al. (ESA'09), via n(st/2+O(1))-time algorithms for counting t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element universe. Shortly afterwards, Alon and Gutner (TALG'10) showed that these problems have Omega(n(left perpendicular st/2 left perpendicular)) and Omega(n(left perpendicular k/2 left perpendicular)) lower bounds when counting by color coding. Here, we show that one can do better-we show that the "meet-in-the-middle" exponent st/2 can be beaten and give an algorithm that counts in time n(0.45470382st+O(1)) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth p << k in an n-vertex graph in n(0.45470382k+2p+O(1)) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. We also give improved bounds for counting t-tuples of disjoint s-sets for s = 2, 3, 4. Our algorithms use fast matrix multiplication. We show an argument that this is necessary to go below the meet-in-the-middle barrier.

关键词： fpt algorithms counting packings counting paths counting matchings counting low pathwidth graphs matrix multiplication meet in the middle

来源：评论

学校读者我要写书评

暂无评论

Beyond Classes of Graphs with "Few" Minimal Separators: fpt Results Through Potential Maximal Cliques

引用

ALGORITHMICA 2019年第3期81卷 986-1005页

作者： Liedloff, Mathieu Montealegre, Pedro Todinca, Ioan Univ Orleans INSA Ctr Val Loire LIFO EA 4022 Orleans France Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile

Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentH-Packing, etc. Fomin et al. (SIAM J Comput 44(1):54-87, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input.

关键词： fpt algorithms Treewidth Potential maximal cliques

来源：评论

学校读者我要写书评

暂无评论

A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands

引用

ALGORITHMICA 2017年第4期77卷 1216-1239页

作者： Chitnis, Rajesh Esfandiari, Hossein Hajiaghayi, MohammadTaghi Khandekar, Rohit Kortsarz, Guy Seddighin, Saeed Weizmann Inst Sci Rehovot Israel Univ Maryland Dept Comp Sci College Pk MD 20742 USA KCG Holdings Inc Jersey City NJ USA Rutgers Univ Camden Dept Comp Sci Camden NJ USA

Given an edge-weighted directed graph G = (V, E) on n vertices and a set T = {t(1), t(2), ... , t(p)} of p terminals, the objective of the STRONGLY CONNECTED STEINER SUBGRAPH (p-SCSS) problem is to find an edge set H subset of E of minimum weight such that G[H] contains an t(i) -> t(j) path for each 1 <= i not equal j <= p. The p-SCSS problem is NP-hard, but Feldman and Ruhl [FOCS '99;SICOMP '06] gave a novel n(O(p)) time algorithm. In this paper, we investigate the computational complexity of a variant of 2-SCSS where we have demands for the number of paths between each terminal pair. Formally, the 2-SCSS-(k(1), k(2)) problem is defined as follows: given an edge-weighted directed graph G = (V, E) with weight function omega : E -> R->= 0, two terminal vertices s, t, and integers k(1), k(2);the objective is to find a set of k(1) paths F-1, F-2, ... , F-k1 from s -> t and k(2) paths B-1, B-2, ... , B-k2 from t -> s such that Sigma(omega(e) . phi(e))(e is an element of E) is minimized, where phi(e) = max {vertical bar{i is an element of [k(1)] : e is an element of F-i}vertical bar, vertical bar{j is an element of [k(2)] : e is an element of B-j}vertical bar}. For each k >= 1, we show the following: The 2-SCSS-(k, 1) problem can be solved in time n(O(k)). A matching lower bound for our algorithm: the 2-SCSS-(k, 1) problem does not have an f (k) . n(o(k)) time algorithm for any computable function f, unless the Exponential Time Hypothesis fails. Our algorithm for 2-SCSS-(k, 1) relies on a structural result regarding an optimal solution followed by using the idea of a "token game" similar to that of Feldman and Ruhl. We show with an example that the structural result does not hold for the 2-SCSS-(k(1), k(2)) problem if min{k(1), k(2)} >= 2. Therefore 2-SCSS-(k, 1) is the most general problem one can attempt to solve with our techniques. To obtain the lower bound matching the algorithm, we reduce from a special variant of the Grid Tiling problem introduced by Marx [FOCS '0

关键词： fpt algorithms Directed graphs Strongly connected Steiner subgraph Exponential time hypothesis

来源：评论

学校读者我要写书评

暂无评论

Contracting Graphs to Paths and Trees

引用

ALGORITHMICA 2014年第1期68卷 109-132页

作者： Heggernes, Pinar van 't Hof, Pim Leveque, Benjamin Lokshtanov, Daniel Paul, Christophe Univ Bergen Dept Informat N-5020 Bergen Norway Univ Montpellier 2 CNRS LIRMM Montpellier France Univ Calif San Diego Dept Comp Sci & Engn San Diego CA 92103 USA

Vertex deletion and edge deletion problems play a central role in parameterized complexity. Examples include classical problems like Feedback Vertex Set, Odd Cycle Transversal, and Chordal Deletion. The study of analogous edge contraction problems has so far been left largely unexplored from a parameterized perspective. We consider two basic problems of this type: Tree Contraction and Path Contraction. These two problems take as input an undirected graph G on n vertices and an integer k, and the task is to determine whether we can obtain a tree or a path, respectively, by a sequence of at most k edge contractions in G. For Tree Contraction, we present a randomized 4 (k) n (O(1)) time polynomial-space algorithm, as well as a deterministic 4.98 (k) n (O(1)) time algorithm, based on a variant of the color coding technique of Alon, Yuster and Zwick. We also present a deterministic 2 (k+o(k))+n (O(1)) time algorithm for Path Contraction. Furthermore, we show that Path Contraction has a kernel with at most 5k+3 vertices, while Tree Contraction does not have a polynomial kernel unless NP aS dagger coNP/poly. We find the latter result surprising because of the connection between Tree Contraction and Feedback Vertex Set, which is known to have a kernel with 4k (2) vertices.

关键词： Graph modification problems Edge contractions Tree Contraction Path Contraction fpt algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

Domination and Cut Problems on Chordal Graphs with Bounded Leafage

引用

ALGORITHMICA 2024年第5期86卷 1428-1474页

作者： Galby, Esther Marx, Daniel Schepper, Philipp Sharma, Roohani Tale, Prafullkumar Hamburg Univ Technol Hamburg Germany CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Indian Inst Sci Educ & Res Pune Pune India

The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2(O(l2)) center dot n(O(1)). We present a conceptually much simpler algorithm that runs in time 2(O(l)) center dot n(O(1)). We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple n(O(l))-time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in n(O(1))-time.

关键词： Chordal graphs Leafage fpt algorithms Dominating set MultiCut with undeletable terminals Multiway cut with undeletable terminals

来源：评论

学校读者我要写书评

暂无评论

The MAXIMUM COLORFUL ARBORESCENCE problem: How (computationally) hard can it be?

引用

THEORETICAL COMPUTER SCIENCE 2021年 852卷 104-120页

作者： Fertin, Guillaume Fradin, Julien Jean, Geraldine Univ Nantes CNRS LS2N F-44000 Nantes France

Given a vertex-colored arc-weighted directed acyclic graph G, the MAXIMUM COLORFUL SUBTREE problem (or MCS) aims at finding an arborescence of maximum weight in G, in which no color appears more than once. The problem was originally introduced in [1] in the context of de novo identification of metabolites by tandem mass spectrometry. However, a thorough analysis of the initial motivation shows that the formal definition of MCS should be amended, since the input graph G actually possesses extra properties, which have been unexploited so far. This leads us to describe in this paper a more precise model that we call MAXIMUM COLORFUL ARBORESCENCE (MCA), which we extensively study in terms of algorithmic complexity. In particular, we show that exploiting the implied Color Hierarchy Graph of the input graph G can lead to exact polynomial algorithms and approximation algorithms. We also develop Fixed-Parameter Tractable (fpt) algorithms for the problem parameterized by the "dual parameter" l(C), defined as the minimum number of vertices of G which are not kept in the solution. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Complexity fpt algorithms Approximation algorithms Maximum colorful arborescence Tandem mass spectrometry

来源：评论

学校读者我要写书评

暂无评论

Structural parameterization for minimum conflict-free colouring

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 239-253页

作者： Ashok, Pradeesha Bhargava, Rathin Gupta, Naman Khalid, Mohammad Yadav, Dolly Int Inst Informat Technol Bangalore Bangalore Karnataka India Indian Inst Sci Educ & Res Mohali Ajitgarh India

Conflict-free q-colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the Minimum Conflict-free q-Colouring problem. Given a graph G and a fixed constant q, Minimum Conflict-free q-Colouring is to find a conflict-free q-colouring of G that minimizes the number of coloured vertices. We study the parameterized complexity of the Minimum Conflict-free q-Colouring problem when parameterized by structural parameters like treewidth and vertex cover of G. We give an fpt algorithm for Minimum Conflict-free q-Colouring parameterized by treewidth and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH). Using standard kernelization lower bound techniques, it is easy to see that Minimum Conflict-free q-Colouring parameterized by treewidth does not admit polynomial kernels. We extend this result for a larger parameter namely the vertex cover of G, when q > 1. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Conflict -free colouring of graphs Parameterized complexity fpt algorithms Treewidth Exponential Time Hypothesis Strong Exponential Time Hypothesis Vertex cover Kernelization

来源：评论

学校读者我要写书评

暂无评论

An fpt Algorithm for Planar Multicuts with Sources and Sinks on the Outer Face

引用

ALGORITHMICA 2019年第1期81卷 224-237页

作者： Bentz, Cedric CNAM 292 Rue St Martin F-75003 Paris France CEDRIC Lab 292 Rue St Martin F-75003 Paris France

Given a list of k source-sink pairs in an edge-weighted graph G, the minimum multicut problem consists in selecting a set of edges of minimum total weight in G, such that removing these edges leaves no path from each source to its corresponding sink. To the best of our knowledge, no non-trivial fpt result for special cases of this problem, which is APX-hard in general graphs for any fixed k3, is known with respect to k only. When the graph G is planar, this problem is known to be polynomial-time solvable if k=O(1), but cannot be fpt with respect to k under the Exponential Time Hypothesis. In this paper, we show that, if G is planar and in addition all sources and sinks lie on the outer face, then this problem does admit an fpt algorithm when parameterized by k (although it remains APX-hard when k is part of the input, even in stars). To do this, we provide a new characterization of optimal solutions in this case, and then use it to design a divide-and-conquer approach: namely, some edges that are part of any such solution actually define an optimal solution for a polynomial-time solvable multiterminal variant of the problem on some of the sources and sinks (which can be identified thanks to a reduced enumeration phase). Removing these edges from the graph cuts it into several smaller instances, which can then be solved recursively.

关键词： Multicuts Planar graphs fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：