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

Recent advances in practical data reduction

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Abu-Khzam, Faisal Lamm, Sebastian Mnich, Matthias Noe, Alexander Schulz, Christian Strash, Darren Lebanese American University Lebanon Karlsruhe Institute of Technologie Germany Hamburg University of Technology Institute for Algorithms and Complexity Germany University of Vienna Austria Heidelberg University Germany

Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has resulted in an algorithmic toolbox that is by now well-established. However, these theoretical algorithmic ideas have received very little attention from the practical perspective. We survey recent trends in data reduction engineering results for selected problems. Moreover, we describe concrete techniques that may be useful for future implementations in the area and give open problems and research questions. Copyright © 2020, The Authors. All rights reserved.

关键词： Data reduction

Balanced Connected Subgraph Problem in Geometric Intersection Graphs 1

学校读者我要写书评

暂无评论

13th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2019

作者： Bhore, Sujoy Jana, Satyabrata Pandit, Supantha Roy, Sasanka Algorithms and Complexity Group TU Wien Vienna Austria Indian Statistical Institute Kolkata India Dhirubhai Ambani Institute of Information and Communication Technology GandhinagarGujarat India

ISBN: (数字)9783030364120

ISBN: (纸本)9783030364113

We study the (shortly,) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given agraph, where each vertex in V is colored with either "" or "", the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is, i.e., H contains an equal number of red and blue vertices. We study the computational complexity landscape of the BCS problem while considering geometric intersection graphs. On one hand, we prove that the BCS problem is NP-hard on the unit disk, outer-string, complete grid, and unit square graphs. On the other hand, we design polynomial-time algorithms for the BCS problem on interval, circular-arc and permutation graphs. In particular, we give algorithms for theproblem on both interval and circular-arc graphs, and those algorithms are used as subroutines for solving the BCS problem on the same classes of graphs. Finally, we present a FPT algorithm for the BCS problem on general graphs. © 2019, Springer Nature Switzerland AG.

关键词： Polynomial approximation

Resolving Infeasibility of Linear Systems: A Parameterized Approach

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bérczi, Kristóf Göke, Alexander Mendoza-Cadena, Lydia Mirabel Mnich, Matthias MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany MTA-ELTE Momentum Matroid Optimization Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary

Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to data inaccuracies or modeling errors, in practical applications one often faces linear systems that are infeasible. Extensive theoretical and practical methods have been proposed for post-infeasibility analysis of linear systems. This generally amounts to detecting a feasibility blocker of small size k, which is a set of equations and inequalities whose removal or perturbation from the large system of size m yields a feasible system. This motivates a parameterized approach towards post-infeasibility analysis, where we aim to find a feasibility blocker of size at most k in fixed-parameter time f(k) · mO(1). We establish parameterized intractability (W[1]- and NP-hardness) results already in very restricted settings for different choices of the parameters maximum size of a deletion set, number of positive/negative right-hand sides, treewidth, pathwidth and treedepth. Additionally, we rule out a polynomial compression for MinFB parameterized by the size of a deletion set and the number of negative right-hand sides. Furthermore, we develop fixed-parameter algorithms parameterized by various combinations of these parameters when every row of the system corresponds to a difference constraint. Our algorithms capture the case of Directed Feedback Arc Set, a fundamental parameterized problem whose fixed-parameter tractability was shown by Chen et al. (STOC 2008). Copyright © 2022, The Authors. All rights reserved.

关键词： Linear systems

Dense steiner problems: Approximation algorithms and inapproximability

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Karpinski, Marek Lewandowski, Mateusz Meesum, Syed Mohammad Mnich, Matthias Universität Bonn Institut für Informatik Bonn Germany University of Wrocaw Institute of Computer Science Wrocaw Poland Tu Hamburg Institute for Algorithms and Complexity Hamburg Germany

The Steiner Tree problem is a classical problem in com-binatorial optimization: the goal is to connect a set T of terminals in a graph G by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the δ-dense version of Steiner Tree, where each terminal has at least δ|V(G) \ T| neighbours outside T, for a fixed δ > 0. They gave a PTAS for this problem. We study a generalization of pairwise δ-dense Steiner Forest, which asks for a minimum-size forest in G in which the nodes in each terminal set T1,... ,Tkare connected, and every terminal in Tihas at least δ|Tj| neighbours in Tj, and at least δ|S| nodes in S = V(G) \ (T1∪ · · · ∪ Tk), for each i,j in {1,... , k} with i ≠ j. Our first result is a polynomial-time approximation scheme for all δ > 1/2. Then, we show a (13/12 + ϵ)-approximation algorithm for δ = 1/2 and any ϵ > 0. We also consider the δ-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is APX-hard. Copyright © 2020, The Authors. All rights reserved.

关键词： Approximation algorithms

Balanced Independent and Dominating Sets on Colored Interval Graphs

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bhore, Sujoy Haunert, Jan-Henrik Klute, Fabian Li, Guangping Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Geoinformation Group University of Bonn Bonn Germany Algorithms and Complexity Group TU Wien Vienna Austria

We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely f-Balanced Independent Set (f-BIS) and f-Balanced Dominating Set (f-BDS). Let G = (V, E) be a vertex-colored interval graph with a k-coloring γ : V → {1,..., k} for some k ∈ N. A subset of vertices S ⊆ V is called f-balanced if S contains f vertices from each color class. In the f-BIS and f-BDS problems, the objective is to compute an independent set or a dominating set that is f-balanced. We show that both problems are NP-complete even on proper interval graphs. For the f-BIS problem we design two FPT algorithms, one parameterized by (f, k) for interval graphs and the other parameterized by the vertex cover number for general graphs. Moreover, for the optimization variant of 1-BIS on interval graphs, we show that a simple greedy approach achieves approximation ratio 2. Copyright © 2020, The Authors. All rights reserved.

关键词： Graphic methods

Algorithmic Extensions of Dirac's Theorem

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Department of Informatics University of Bergen Norway St. Petersburg Department V.A. Steklov Institute of Mathematics Russia Algorithms and Complexity Group TU Wien Austria

In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every n-vertex 2-connected graph G with minimum vertex degree δ ≥ 2 contains a cycle with at least min{2δ, n} vertices. In particular, if δ ≥ n/2, then G is Hamiltonian. The proof of Dirac's theorem is constructive, and it yields an algorithm computing the corresponding cycle in polynomial time. The combinatorial bound of Dirac's theorem is tight in the following sense. There are 2-connected graphs that do not contain cycles of length more than 2δ + 1. Also, there are non-Hamiltonian graphs with all vertices but one of degree at least n/2. This prompts naturally to the following algorithmic questions. For k ≥ 1, (A) How difficult is to decide whether a 2-connected graph contains a cycle of length at least min{2δ + k, n}? (B) How difficult is to decide whether a graph G is Hamiltonian, when at least n - k vertices of G are of degrees at least n/2 - k? The first question was asked by Fomin, Golovach, Lokshtanov, Panolan, Saurabh, and Zehavi. The second question is due to Jansen, Kozma, and Nederlof. Even for a very special case of k = 1, the existence of a polynomial-time algorithm deciding whether G contains a cycle of length at least min{2δ + 1, n} was open. We resolve both questions by proving the following algorithmic generalization of Dirac's theorem: If all but k vertices of a 2-connected graph G are of degree at least δ, then deciding whether G has a cycle of length at least min{2δ + k, n} can be done in time 2O(k) nO(1). The proof of the algorithmic generalization of Dirac's theorem builds on new graph-theoretical results that are interesting on their own. Copyright © 2020, The Authors. All rights reserved.

关键词： Hamiltonians

Graphs with at most two moplexes

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Dallard, Clément Ganian, Robert Hatzel, Meike Krnc, Matjaž Milanič, Martin Lifo Ea 4022 Insa Centre Val de Loire Université d'Orléans Orléans France Algorithms and Complexity Group Tu Wien Vienna Austria National Institute of Informatics Tokyo Japan Famnit University of Primorska Koper Slovenia Famnit Iam University of Primorska Koper Slovenia

A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes such as interval graphs, claw-free, and diamond-free graphs. However, while every non-complete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, in part, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are interval. In this work we initiate an investigation of k-moplex graphs, which are defined as graphs containing at most k moplexes. Of particular interest is the smallest nontrivial case k = 2, which forms a counterpart to the class of interval graphs. As our main structural result, we show that, when restricted to connected graphs, the class of 2-moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs;moreover, both inclusions are tight for hereditary classes. From a complexity theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely Graph Isomorphism and Max-Cut. On the other hand, we prove that every connected 2-moplex graph contains a Hamiltonian path, generalising the same property of connected proper interval graphs. Furthermore, for graphs wi

关键词： Graphic methods

Untangling Circular Drawings: algorithms and complexity

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Rutter, Ignaz Wu, Hsiang-Yun Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Vienna Austria University of Passau Passau Germany Research Unit of Computer Graphics TU Wien Vienna Austria St. Pölten University of Applied Sciences St. Pölten Austria

We consider the problem of untangling a given (non-planar) straight-line circular drawing δG of an outerplanar graph G = (V, E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift◦(δG) as the minimum number of vertices that are required to be shifted in order to resolve all crossings of δG. We show that the problem Circular Untangling, asking whether shift◦(δG) ≤ K for a given integer K, is NP-complete. For n-vertex outerplanar graphs, we obtain a tight upper bound of shift◦(δG) ≤ n − ⌊√n − 2⌋ − 2. Moreover, we study the Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. For this problem, we provide a tight upper bound shift◦(δG) ≤ ⌊n/2⌋ − 1 and present a constructive polynomial-time algorithm to compute the circular shifting number of almost-planar drawings. © 2021, CC BY.

关键词： Drawing (graphics)

A unifying framework for characterizing and computing width measures

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Jaffke, Lars Kwon, O-Joung Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Vienna Austria Department of Informatics University of Bergen Bergen Norway Department of Mathematics Incheon National University Incheon Korea Republic of Discrete Mathematics Group Institute for Basic Science Daejeon Korea Republic of

algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify F-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of F-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can compute every possible F-branchwidth, providing a unifying framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width *** Codes 68Q27 Copyright © 2021, The Authors. All rights reserved.

关键词： Parameter estimation