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

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

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

Single-Peaked Opinion Updates

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bredereck, Robert George, Anne-Marie Israel, Jonas Kellerhals, Leon Algorithm Engineering Humboldt-Universität Berlin Germany Institut für Informatik TU Clausthal Germany Analytical Solutions and Reasoning University of Oslo Germany Research Group Efficient Algorithms Technische Universität Berlin Germany Algorithmics and Computational Complexity Technische Universität Berlin Germany

We consider opinion diffusion for undirected networks with sequential updates when the opinions of the agents are single-peaked preference rankings. Our starting point is the study of preserving single-peakedness. We identify voting rules that, when given a single-peaked profile, output at least one ranking that is single peaked w.r.t. a single-peaked axis of the input. For such voting rules we show convergence to a stable state of the diffusion process that uses the voting rule as the agents’ update rule. Further, we establish an efficient algorithm that maximises the spread of extreme opinions. Copyright © 2022, The Authors. All rights reserved.

关键词： Machine learning

Exact algorithms for Clustered Planarity with Linear Saturators

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Da Lozzo, Giordano Ganian, Robert Gupta, Siddharth Mohar, Bojan Ordyniak, Sebastian Zehavi, Meirav Roma Tre University Italy Algorithms and Complexity Group TU Wien Vienna Austria BITS Pilani K K Birla Goa Campus India Department of Mathematics Simon Fraser University BurnabyBC Canada University of Leeds United Kingdom Ben-Gurion University of the Negev Beer-Sheva Israel

We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an n-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths—one for each cluster—that connect all the vertices in each cluster while maintaining planarity. We show that the problem can be solved in time 2O(n) for both the variable and fixed embedding case. Moreover, we show that it can be solved in subexponential time 2O(√n log n) in the fixed embedding case if additionally the input graph is connected. The latter time complexity is tight under the Exponential-Time Hypothesis. We also show that n can be replaced with the vertex cover number of the input graph by providing a linear (resp. polynomial) kernel for the variable-embedding (resp. fixed-embedding) case;these results contrast the NP-hardness of the problem on graphs of bounded treewidth (and even on trees). Finally, we complement known lower bounds for the problem by showing that Clustered Planarity with Linear Saturators is NP-hard even when the number of clusters is at most 3, thus excluding the algorithmic use of the number of clusters as a parameter. © 2024, CC BY.

关键词： Graph embeddings

The most general structure of graphs with hamiltonian or hamiltonian connected square

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Ekstein, Jan Fleischner, Herbert Department of Mathematics European Centre of Excellence Ntis - New Technologies for the Information Society Faculty of Applied Sciences University of West Bohemia Pilsen Technická 8 Plzeň306 14 Czech Republic Institute of Logic and Computation Algorithms and Complexity Group Technical University of Vienna Favoritenstrasse 9 - 11 Wien1040 Austria

On the basis of recent results on hamiltonicity, [4], and hamiltonian connectedness, [8], in the square of a 2-block, we determine the most general block-cutvertex structure a graph G may have in order to guarantee that G2 is hamiltonian, hamiltonian connected, respectively. Such an approach was already developed in [9] for hamiltonian total *** Codes 05C38, 05C45 © 2022, CC BY.

关键词： Hamiltonians

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)

complexity of the steiner network problem with respect to the number of terminals

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Eiben, Eduard Knop, Dušan Panolan, Fahad Suchý, Ondřej Algorithms and Complexity Group TU Wien Vienna Austria Department of Informatics University of Bergen Bergen Norway Department of Applied Mathematics Faculty of Mathematics and Physics Charles University Prague Czech Republic Department of Theoretical Computer Science Faculty of Information Technology Czech Technical University in Prague Prague Czech Republic

In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T ⊆ V (G), and an (unweighted) directed request graph R with V (R) = T. Our task is to output a subgraph G′ ⊆ G of the minimum cost such that there is a directed path from s to t in G′ for all st ∈ A(R). It is known that the problem can be solved in time |V (G)|O(|A(R)|) [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time |V (G)|o(|A(R)|) even if G is planar, unless Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, as this reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time |V (G)|o(|T|) unless ETH fails, there is a significant gap in the complexity with respect to |T| in the exponent. We show that Directed Steiner Network is solvable in time f(R) · |V (G)|O(cg·|T|), where cg is a constant depending solely on the genus of G and f is a computable function. We complement this result by showing that there is no f(R)·|V (G)|o(|T|2/ log |T|) algorithm for any function f for the problem on general graphs, unless ETH fails. Copyright © 2018, The Authors. All rights reserved.

关键词： Complex networks

Integer programming and incidence treedepth

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Eiben, Eduard Ganian, Robert Knop, Dušan Ordyniak, Sebastian Pilipczuk, Michal Wrochna, Marcin Department of Computer Science Royal Holloway University of London United Kingdom Algorithms and Complexity Group Vienna University of Technology Austria Department of Theoretical Computer Science Czech Technical University in Prague Czech Republic School of Computing University of Leeds United Kingdom Institute of Informatics University of Warsaw Poland University of Oxford United Kingdom

Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Koutecký, Levin, and Onn [ICALP 2018] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)? We answer this question in negative. In particular, we prove that deciding the feasibility of a system in the standard form, Ax = b, l 6 x 6 u, is NP-hard even when the absolute value of any coefficient in A is 1 and the incidence treedepth of A is 5. Consequently, it is not possible to decide feasibility in polynomial time even if both the assumed parameters are constant, unless P = NP. Moreover, we complement this intractability result by showing tractability for natural and only slightly more restrictive settings, namely: (1) treedepth with an additional bound on either the maximum arity of constraints or the maximum number of occurrences of variables and (2) the vertex cover number. Copyright © 2020, The Authors. All rights reserved.

关键词： Integer programming

Geometric systems of unbiased representatives

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Banik, Aritra Bhattacharya, Bhaswar B. Bhore, Sujoy Martínez-Sandoval, Leonardo School of Computer Sciences National Institute of Science Education and Research HBNI Bhubaneswar India Department of Statistics University of Pennsylvania Philadelphia United States Algorithms and Complexity Group Technische Universität Wien Austria Institut de Mathématiques de Jussieu-Paris Rive Gauche UMR 7586 Sorbonne Université France

Let P be a set of points in Rd, B a bicoloring of P and O a family of geometric objects (that is, intervals, boxes, balls, etc). An object from O is called balanced with respect to B if it contains the same number of points from each color of B. For a collection B of bicolorings of P, a geometric system of unbiased representatives (G-SUR) is a subset O0 ⊆ O such that for any bicoloring B of B there is an object in O0 that is balanced with respect to B. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives. Copyright © 2020, The Authors. All rights reserved.

关键词：