The Maximum Linear Arrangement Problem for trees under projectivity and planarity

• URL: http://arxiv.org/abs/2206.06924v5
• Date: Tue, 21 Mar 2023 08:47:13 GMT
• Title: The Maximum Linear Arrangement Problem for trees under projectivity and planarity
• Authors: Llu\'is Alemany-Puig, Juan Luis Esteban and Ramon Ferrer-i-Cancho
• Abstract summary: A linear arrangement is a mapping $pi$ from the $n$ vertices of a graph $G$ to $n$ distinct consecutive integers. Here we study two variants of the Maximum Linear Arrangement problem (MaxLA), which consists of finding an arrangement that maximizes the cost. In this paper we present algorithms that are linear in time and space to solve planar and projective MaxLA for trees.
• Score: 0.90238471756546
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A linear arrangement is a mapping $\pi$ from the $n$ vertices of a graph $G$ to $n$ distinct consecutive integers. Linear arrangements can be represented by drawing the vertices along a horizontal line and drawing the edges as semicircles above said line. In this setting, the length of an edge is defined as the absolute value of the difference between the positions of its two vertices in the arrangement, and the cost of an arrangement as the sum of all edge lengths. Here we study two variants of the Maximum Linear Arrangement problem (MaxLA), which consists of finding an arrangement that maximizes the cost. In the planar variant for free trees, vertices have to be arranged in such a way that there are no edge crossings. In the projective variant for rooted trees, arrangements have to be planar and the root of the tree cannot be covered by any edge. In this paper we present algorithms that are linear in time and space to solve planar and projective MaxLA for trees. We also prove several properties of maximum projective and planar arrangements, and show that caterpillar trees maximize planar MaxLA over all trees of a fixed size thereby generalizing a previous extremal result on trees.

Related papers

• Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees [0.0]
  We propose two cut-based mixed integer linear optimization (MILO) formulations for designing optimal binary classification trees. Our models leverage on-the-fly identification of minimal infeasible subsystems (MISs) from which we derive cutting planes that hold the form of packing constraints.
  arXiv  Detail & Related papers  (2024-08-02T14:37:28Z)
• Hierarchical cycle-tree packing model for $K$-core attack problem [0.0]
  A hierarchical cycle-tree packing model is introduced here for this challenging optimization problem. We analyze this model through the replica-symmetric cavity method of statistical physics. The associated hierarchical cycle-tree guided attack (tt hCTGA) is able to construct nearly optimal attack solutions for regular random graphs.
  arXiv  Detail & Related papers  (2023-03-02T06:47:33Z)
• SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
  We introduce SoftTreeMax, the first approach that integrates tree-search into policy gradient. On Atari, SoftTreeMax demonstrates up to 5x better performance in faster run-time compared with distributed PPO.
  arXiv  Detail & Related papers  (2022-09-28T09:55:47Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Minimum projective linearizations of trees in linear time [0.12289361708127873]
  We derive simple algorithms for the projective and planar cases that run without a doubt in $O(n)$ time. We also consider linear arrangements of rooted trees that are constrained to be projective.
  arXiv  Detail & Related papers  (2021-02-05T16:35:38Z)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  adversarial attacks on tree based ensembles such as gradient boosting decision trees (DTs) and random forests (RFs) We show that our method can be thousands of times faster than the previous mixed-integer linear programming (MILP) based approach. Our code is available at https://chong-z/tree-ensemble-attack.
  arXiv  Detail & Related papers  (2020-10-22T10:59:49Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)
• Bounds of the sum of edge lengths in linear arrangements of trees [0.90238471756546]
  In particular, we investigate various problems on the sum of edge lengths in trees of a fixed size. We establish some foundations for research on optimality scores for spatial networks in one dimension.
  arXiv  Detail & Related papers  (2020-06-24T21:53:39Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. We show that the QAOA with $(d-1)2p nA$ for any $A1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large.
  arXiv  Detail & Related papers  (2020-05-18T14:23:09Z)
• Graph Metric Learning via Gershgorin Disc Alignment [46.145969174332485]
  We propose a fast general projection-free metric learning framework, where the objective $min_textbfM in mathcalS$ is a convex differentiable function of the metric matrix $textbfM$. We prove that the Gershgorin discs can be aligned perfectly using the first eigenvector $textbfv$ of $textbfM$. Experiments show that our efficiently computed graph metric matrices outperform metrics learned using competing methods in terms of classification tasks.
  arXiv  Detail & Related papers  (2020-01-28T17:44:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.