Anti Tai mapping for unordered labeled trees

DOI10.1016/J.IPL.2023.106454MaRDI QIDQ6195334zbMATH OpenOpenAlexFDO

Authors Mislav Blažević, Stefan Canzar, Khaled Elbassioni, Domagoj Matijević

Publication date 13 March 2024

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.08292

zbMATH Keywords

clique constraintscombinatorial problemsTai mappingtree edit distanceunordered trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The well-studied Tai mapping between two rooted labeled trees $T_1(V_1,E_1)$ and $T_2(V_2,E_2)$ defines a one-to-one mapping between nodes in $T_1$ and $T_2$ that preserves ancestor relationship. For unordered trees the problem of finding a maximum-weight Tai mapping is known to be NP-complete. In this work, we define an anti Tai mapping $Msubseteq{V}_{1}imes{V}_2$ as a binary relation between two unordered labeled trees such that any two $(x,y),(x^{\prime },y^{\prime })inM$ violate ancestor relationship and thus cannot be part of the same Tai mapping, i.e. $(xle{x}^{\prime }iffyotle{y}^{\prime })vee(x^{\prime }lexiff{y}^{\prime }otley)$, given an ancestor order $x<x^{\prime }$ meaning that $x$ is an ancestor of $x^{\prime }$. Finding a maximum-weight anti Tai mapping arises in the cutting plane method for solving the maximum-weight Tai mapping problem via integer programming. We give an efficient polynomial-time algorithm for finding a maximum-weight anti Tai mapping for the case when one of the two trees is a path and further show how to extend this result in order to provide a polynomially computable lower bound on the optimal anti Tai mapping for two unordered labeled trees. The latter result stems from the special class of anti Tai mapping defined by the more restricted condition $xsim{x}^{\prime }iffyotsim{y}^{\prime }$, where $sim$ denotes that two nodes belong to the same root-to-leaf path. For this class, we give an efficient algorithm that solves the problem directly on two unordered trees in $O(|V_1{|}^2|V_2{|}^2)$.

Cites work

• Cumulative disease progression models for cross-sectional data: a review and comparison
• Geometric algorithms and combinatorial optimization.
• On a matching distance between rooted phylogenetic trees
• On the editing distance between unordered labeled trees
• Some MAX SNP-hard results concerning unordered labeled trees
• Tai mapping hierarchy for rooted labeled trees through common subforest
• The Tree-to-Tree Correction Problem

This page was built for publication: Anti Tai mapping for unordered labeled trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6195334)