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

Signed Double Roman Domination on Cubic Graphs

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Iurlano, Enrico Zec, Tatjana Djukanovic, Marko Raidl, Günther R. Algorithms and Complexity Group TU Wien Favoritenstraße 9/1921 Vienna1040 Austria Faculty of Natural Sciences and Mathematics University of Banja Luka Mladena Stojanovića 2 Banja Luka78000 Bosnia and Herzegovina

The signed double Roman domination problem is a combinatorial optimization problem on a graph asking to assign a label from {±1, 2, 3} to each vertex feasibly, such that the total sum of assigned labels is minimized. Here feasibility is given whenever (i) vertices labeled ±1 have at least one neighbor with label in {2, 3};(ii) each vertex labeled −1 has one 3-labeled neighbor or at least two 2-labeled neighbors;and (iii) the sum of labels over the closed neighborhood of any vertex is positive. The cumulative weight of an optimal labeling is called signed double Roman domination number (SDRDN). In this work, we first consider the problem on general cubic graphs of order n for which we present a sharp n/2 + Θ(1) lower bound for the SDRDN by means of the discharging method. Moreover, we derive a new best upper bound. Observing that we are often able to minimize the SDRDN over the class of cubic graphs of a fixed order, we then study in this context generalized Petersen graphs for independent interest, for which we propose a constraint programming guided proof. We then use these insights to determine the SDRDNs of subcubic 2 × m grid graphs, among other *** Codes 05C78, 05C35, 90C27 © 2023, CC BY.

关键词： Graphic methods

The complexity of Temporal Vertex Cover in Small-Degree Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Hamm, Thekla Klobas, Nina Mertzios, George B. Spirakis, Paul G. Algorithms and Complexity Group TU Wien Vienna Austria Department of Computer Science Durham University United Kingdom Department of Computer Science University of Liverpool United Kingdom Computer Engineering & Informatics Department University of Patras Greece

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or ∆-TVC for time-windows of a fixed-length ∆) have been established as natural extensions of the classic problem Vertex Cover on static graphs with connections to areas such as surveillance in sensor networks. In this paper, we initiate a systematic study of the complexity of TVC and ∆-TVC on sparse graphs. Our main result shows that for every ∆ ≥ 2, ∆-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between ∆-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present some fixed-parameter and approximation algorithms. Copyright © 2022, The Authors. All rights reserved.

关键词： Approximation algorithms

Tight complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Focke, Jacob Marx, Dániel Inerney, Fionn Mc Neuen, Daniel Sankar, Govind S. Schepper, Philipp Wellnitz, Philip CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria School of Computing Science Simon Fraser University Canada Duke University United States Max Planck Institute for Informatics SIC Germany

For a well-studied family of domination-type problems, in bounded-treewidth graphs, we investigate whether it is possible to find faster algorithms. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u) ∩ S| ∈ σ for every u ∈ S, and |N(v) ∩ S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies common problems like Independent Set, Dominating Set, Independent Dominating Set, and many others. In an accompanying paper, it is proven that, for all pairs of finite or cofinite sets (σ, ρ), there is an algorithm that counts (σ, ρ)-sets in time (cσ,ρ)tw · nO(1) (if a tree decomposition of width tw is given in the input). Here, cσ,ρ is a constant with an intricate dependency on σ and ρ. Despite this intricacy, we show that the algorithms in the accompanying paper are most likely optimal, i.e., for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any Ε > 0, a (cσ,ρ − Ε)tw · nO(1)-algorithm counting the number of (σ, ρ)-sets would violate the Counting Strong Exponential-Time Hypothesis (#SETH). For finite sets σ and ρ, our lower bounds also extend to the decision version, showing that those algorithms are optimal in this setting as well. Copyright © 2023, The Authors. All rights reserved.

关键词： Trees (mathematics)

On the complexity Landscape of Connected f-Factor Problems

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Ganian, R. Narayanaswamy, N.S. Ordyniak, S. Rahul, C.S. Ramanujan, M.S. Algorithms and Complexity Group TU Wien Vienna Austria Indian Institute of Technology Madras Chennai India Department of Computer Science University of Sheffield Sheffield United Kingdom Faculty of Mathematics Informatics and Mechanics University of Warsaw Poland

Let G be an undirected simple graph having n vertices and let f be a function defined to be f : V (G) → {0, . . ., n − 1}. An f-factor of G is a spanning subgraph H such that dH(v) = f(v) for every vertex v ∈ V (G). The subgraph H is called a connected f-factor if, in addition, H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize HAMILTONIAN CYCLE and hence is NP-complete. In fact, the CONNECTED f-FACTOR problem remains NP-complete even when we restrict f(v) to be at least n∊ for each vertex v and ∊ n3 for every vertex *** this paper, we extend this line of work and obtain new complexity results based on restrictions on the function f. In particular, we show that when f(v) is restricted to be at least (lognn)c , the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c ≤ 1. Furthermore, we show that when c > 1, the problem is NP-intermediate. Copyright © 2018, The Authors. All rights reserved.

关键词： Polynomial approximation

Upper and lower bounds for finding connected motifs in vertex-colored graphs

学校读者我要写书评

暂无评论

Upper and lower bounds for finding connected motifs in verte...

作者： Fellows, Michael R. Fertin, Guillaume Hermelin, Danny Vialette, Stéphane University of Newcastle Callaghan NSW 2308 Australia UMR CNRS 6241 Université de Nantes 2 rue de la Houssinière 44322 Nantes Cedex 3 France Algorithms and Complexity Group Max Planck Institute for Informatics Campus E1 4 66123 Saarbrücken Germany LIGM CNRS Université Paris-Est 5 Bd Descartes 77454 Marne-la-Vallée France

We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices whose multiset of colors equals the motif. This problem is a natural graph-theoretic pattern matching variant where we are not interested in the actual structure of the occurrence of the pattern, we only require it to preserve the very basic topological requirement of connectedness. We give two positive results and three negative results that together give an extensive picture of tractable and intractable instances of the problem. © 2010 Elsevier Inc. All rights reserved.

关键词： Graph theory

Space-Efficient Parameterized algorithms on Graphs of Low Shrubdepth

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bergougnoux, Benjamin Chekan, Vera Ganian, Robert Kanté, Mamadou Moustapha Mnich, Matthias Oum, Sang-Il Pilipczuk, Michal van Leeuwen, Erik Jan Institute of Informatics University of Warsaw Poland Humboldt-Universität zu Berlin Germany Algorithms and Complexity Group TU Wien Vienna Austria Université Clermont Auvergne Clermont Auvergne INP LIMOS CNRS Clermont-Ferrand France Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany Daejeon Korea Republic of Department of Mathematical Sciences KAIST Daejeon Korea Republic of Dept. Information and Computing Sciences Utrecht University Netherlands

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, Independent Set can be solved in time 2O(dk) · nO(1) using O(dk2 log n) space;Max Cut can be solved in time nO(dk) using O(dk log n) space;and Dominating Set can be solved in time 2O(dk) · nO(1) using nO(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial. Copyright © 2023, The Authors. All rights reserved.

关键词： Dynamic programming

Shrub-depth: Capturing Height of Dense Graphs

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Ganian, Robert Hliněný, Petr Nešetřil, Jaroslav Obdržálek, Jan de Mendez, Patrice Ossona Algorithms and Complexity Group TU Wien Vienna Austria Faculty of Informatics Masaryk University Brno Czech Republic Praha Czech Republic CNRS UMR 8557 École des Hautes Études en Sciences Sociales Paris France

The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say;one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower ω levels of the MSO1 transduction hierarchy of simple *** Codes 03B70, 05C75, 68R10 © 2017, CC BY.

关键词： Graphic methods

Tight complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Focke, Jacob Marx, Dániel Mc Inerney, Fionn Neuen, Daniel Sankar, Govind S. Schepper, Philipp Wellnitz, Philip CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria School of Computing Science Simon Fraser University Canada Duke University United States Max Planck Institute for Informatics SIC Germany

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u) ∩S| ∈ σ for every u ∈ S, and |N(v) ∩S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value cσ,ρ such that there is an algorithm that counts (σ, ρ)sets in time ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite;rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining cσ,ρ, we say that (σ, ρ) is m-structured if there is a pair (α, β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • cσ,ρ = stop + rtop + 2 if (σ, ρ) is not m-structured for any m ≥ 2, • cσ,ρ = max{stop, rtop}+ 2 if (σ, ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise, we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the Exact Independent Dominating Set problem (also known as Perfect Code) corresponding to σ = algorithms and ρ = algorithms, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw · nO(1). Despite the unusually delicate definition of cσ,ρ, an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any Ε > 0, a (cσ,ρ−Ε)tw ·nO(1)-algorithm counting the number of (σ, ρ)-sets would violate the C

关键词： Trees (mathematics)

Gerrymandering on graphs: Computational complexity and parameterized algorithms

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Gupta, Sushmita Jain, Pallavi Panolan, Fahad Roy, Sanjukta Saurabh, Saket Institute of Mathematical Science HBNI India Indian Institute of Technology Jodhpur India Indian Institute of Technology Hyderabad India Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Science HBNI India University of Bergen Norway

The practice of partitioning a region into areas to favor a particular candidate or a party in an election has been known to exist for the last two centuries. This practice is commonly known as gerrymandering. Recently, the problem has also attracted a lot of attention from complexity theory perspective. In particular, Cohen-Zemach et al. [AAMAS 2018] proposed a graph theoretic version of gerrymandering problem and initiated an algorithmic study around this, which was continued by Ito et al. [AAMAS 2019]. In this paper we continue this line of investigation and resolve an open problem in the literature, as well as move the algorithmic frontier forward by studying this problem in the realm of parameterized complexity. Our contributions in this article are two-fold, conceptual and computational. We first resolve the open question posed by Ito et al. [AAMAS 2019] about the computational complexity of gerrymandering when the input graph is a path. Next, we propose a generalization of the model studied in [AAMAS 2019], where the input consists of a graph on n vertices representing the set of voters, a set of m candidates C, a weight function wv : C → Z+ for each voter v ∈ V (G) representing the preference of the voter over the candidates, a distinguished candidate p ∈ C, and a positive integer k. The objective is to decide if it is possible to partition the vertex set into k districts (i.e., pairwise disjoint connected sets) such that the candidate p wins more districts than any other candidate. There are several natural parameters associated with the problem: the number of districts the vertex set needs to be partitioned (k), the number of voters (n), and the number of candidates (m). The problem is known to be NP-complete even if k = 2, m = 2, and G is either a complete bipartite graph (in fact K2,n, a complete bipartite graphs with one side of size 2 and the other of size n) or a complete graph. This hardness result implies that we cannot hope to have an algorithm wit

关键词： Graph theory