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

SAT-Based Search for Minwise Independent Families

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Iurlano, Enrico Raidl, Günther R. Algorithms and Complexity Group TU Wien Favoritenstraße 9-11/192-01 Vienna1040 Austria

Proposed for rapid document similarity estimation in web search engines, the celebrated property of minwise independence imposes highly symmetric constraints on a family F of permutations of {1, ..., n}: The property is fulfilled by F if for each j ∈ {1, ..., n}, any cardinality-j subset X ⊆ {1, ..., n}, and any fixed element x∗ ∈ X, it occurs with probability 1/j that a randomly drawn permutation π from F satisfies π(x∗) = min{π(x): x ∈ X}. The central interest is to find a family with fewest possible members meeting the stated constraints. We provide a framework that, firstly, is realized as a pure SAT model and, secondly, generalizes a heuristic of Mathon and van Trung to the search of these families. Originally, the latter enforces an underlying group-theoretic decomposition to achieve a significant speed-up for the computer-aided search of structures which can be identified with so-called rankwise independent families. We observe that this approach is suitable to find provenly optimal new representatives of minwise independent families while yielding a decisive speed-up, too. As the problem has a naive search space of size at least (n!)n, we also carefully address symmetry breaking. Finally, we add a bijective proof for a problem encountered by Bargachev when deriving a lower bound on the number of members in a minimal rankwise independent *** Codes 90C27, 68R05 © 2024, CC BY-SA.

关键词： group theory

A Dynamic MaxSAT-based Approach to Directed Feedback Vertex Sets

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Kiesel, Rafael Schidler, André Institute of Logic and Computation Tu Wien Vienna Austria Algorithms and Complexity Group Tu Wien Vienna Austria

We propose a new approach to the Directed Feedback Vertex Set Problem (DFVSP), where the input is a directed graph and the solution is a minimum set of vertices whose removal makes the graph acyclic. Our approach, implemented in the solver DAGer, is based on two novel contributions: Firstly, we add a wide range of data reductions that are partially inspired by reductions for the similar vertex cover problem. For this, we give a theoretical basis for lifting reductions from vertex cover to DFVSP but also incorporate novel ideas into strictly more general and new DFVSP reductions. Secondly, we propose dynamically encoding DFVSP in propositional logic using cycle propagation for improved performance. Cycle propagation builds on the idea that already a limited number of the constraints in a propositional encoding is usually sufficient for finding an optimal solution. Our algorithm, therefore, starts with a small number of constraints and cycle propagation adds additional constraints when necessary. We propose an efficient integration of cycle propagation into the workflow of MaxSAT solvers, further improving the performance of our algorithm. Our extensive experimental evaluation shows that DAGer significantly outperforms the state-of-the-art solvers and that our data reductions alone directly solve many of the instances. Copyright © 2022, The Authors. All rights reserved.

关键词： Directed graphs

Problems on group-Labeled Matroid Bases 51

学校读者我要写书评

暂无评论

Problems on Group-Labeled Matroid Bases

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Hörsch, Florian Imolay, András Mizutani, Ryuhei Oki, Taihei Schwarcz, Tamás Algorithms and Complexity Group CISPA Saarbrücken Germany MTA-ELTE Matroid Optimization Research Group Department of Operations Research ELTE Eötvös Loránd University Budapest Hungary Department of Mathematical Informatics Graduate School of Information Science and Technology The University of Tokyo Japan

ISBN: (纸本)9783959773225

Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed. © Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz.

关键词： Polynomial approximation

The Half-integral Erdős-Pósa Property for Non-null Cycles

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Lokshtanov, Daniel Ramanujan, M.S. Saurabh, Saket Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences

A group Labeled Graph is a pair (G, Λ) where G is an oriented graph and Λ is a mapping from the arcs of G to elements of a group. A (not necessarily directed) cycle C is called non-null if for any cyclic ordering of the arcs in C, the group element obtained by ‘adding’ the labels on forward arcs and ‘subtracting’ the labels on reverse arcs is not the identity element of the group. Non-null cycles in group labeled graphs generalize several well-known graph structures, including odd cycles. A family F of graphs has the Erdős-Pósa property, if for every integer k there exists an integer f(k, F) such that every graph G contains either k vertex-disjoint subgraphs each isomorphic to a graph in F or a set at most f(k, F) vertices intersecting every subgraph isomorphic to a graph in F. In this paper, we prove that non-null cycles on group Labeled Graphs have the 21 -integral Erdős-Pósa property. That is, there is a function f : N → N such that for any k ∈ N, any group labeled graph (G, Λ) has a set of k non-null cycles such that each vertex of G appears in at most two of these cycles or there is a set of at most f(k) vertices that intersects every non-null cycle. Since it is known that non-null cycles do not have the Erdős-Pósa property in general, a 21 -integral Erdős-Pósa result is the best one could hope for. Copyright © 2017, The Authors. All rights reserved.

关键词： Machine learning

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem 18

学校读者我要写书评

暂无评论

From Data Completion to Problems on Hypercubes: A Parameteri...

18th International Symposium on Parameterized and Exact Computation, IPEC 2023

作者： Eiben, Eduard Ganian, Robert Kanj, Iyad Ordyniak, Sebastian Szeider, Stefan Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group TU Wien Austria School of Computing DePaul University ChicagoIL United States School of Computing University of Leeds United Kingdom

ISBN: (纸本)9783959773058

Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular. Interestingly, these problems can be equivalently formulated as classical graph problems on induced subgraphs of powers of partially-defined hypercubes. In this paper, we follow up on this recent direction by investigating the Independent Set problem on this graph class, which has been studied in the data science setting under the name Diversity. We obtain a comprehensive picture of the problem's parameterized complexity and establish its fixed-parameter tractability w.r.t. the solution size plus the power of the hypercube. Given that several such FO-definable problems have been shown to be fixed-parameter tractable on the considered graph class, one may ask whether fixed-parameter tractability could be extended to capture all FO-definable problems. We answer this question in the negative by showing that FO model checking on induced subgraphs of hypercubes is as difficult as FO model checking on general graphs. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Model checking

On strict (Outer-)confluent graphs

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2021年第1期25卷 481-512页

作者： Förster, Henry Ganian, Robert Klute, Fabian Nöllenburg, Martin University of Tübingen Tübingen Germany Algorithms and Complexity Group TU Wien Vienna Austria Utrecht University Utrecht Netherlands

A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like (∆-)SOC graphs have bounded cliquewidth. © 2021, Brown University. All rights reserved.

关键词： Trees (mathematics)

Computing Twin-Width Parameterized by the Feedback Edge Number

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Balabán, Jakub Ganian, Robert Rocton, Mathis Faculty of Informatics Masaryk University Brno Czech Republic Algorithms and Complexity Group TU Wien Vienna Austria

The problem of whether and how one can compute the twin-width of a graph—along with an accompanying contraction sequence—lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an -contraction sequence (for an arbitrary specified ) or determines that the twin-width of the input graph is at least . These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number. © 2023, CC BY.

关键词： Parameterization

Worbel: Aggregating point labels into word clouds

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Vienna Austria

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021, CC BY.

关键词： Visualization

A Unifying Framework for Characterizing and Computing Width Measures 13

学校读者我要写书评

暂无评论

A Unifying Framework for Characterizing and Computing Width ...

13th Innovations in Theoretical Computer Science Conference, ITCS 2022

作者： 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 Austria Department of Informatics University of Bergen Norway Department of Mathematics Incheon National University Korea Republic of Discrete Mathematics Group Institute for Basic Science Daejeon Korea Republic of

ISBN: (纸本)9783959772174

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 approximate every possible F-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions. © Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon;licensed under Creative Commons License CC-BY 4.0

关键词： Parameter estimation