Weight-Assignment Tree

Problem Description

Weight-Assignment Tree problem is inspired by cost-based "join-order" optimization of SQL queries problem in databases. It is concerned with a full-binary tree with n leaves such that

1. its leaves are pairs (weight,cardinality), where weight and cardinality are integers ii. the right child of an inner node is a leaf, iii. each inner node is a pair (color,weight), where color is either green, red, or blue. iv. there are 1 .. n-1 inner nodes such that node "n-1" is a root node and inner node "i-1" is the left child of inner node "i" for i=2..n-1 .

Condition "ii" implies that the trees of interest are paths going to the left with each node on the path having the right child being a leaf of the tree.

The weights of inner nodes are computed recursively (or to put it differently, are subject to constraints) based on their colors, weights and the cardinalities of their children.

Specifically, the weight of an inner node X satisfies the formulas (constraint):

• if color of X is green weight(X) = weight(right child of X) + cardinality(right child of X)

  if color of X is red weight(X) = weight(right child of X) + weight(left child of X)

  if color(X) is blue weight(X) = cardinality(right child of X) + weight(left child of X)

Total weight of a tree is the sum of the weights of its inner nodes.

The problem is: Given

1. weights and cardinality values of n leaves and b. an integer mv, verify if there is a tree T with these n leaves satisfying conditions "i"-"iv" whose total weight is less or equal to mv.

Predicates

• Input: leafWeightCardinality/3, num/1, max_total_weight/1, innerNode/1

• Output: exists/0, leafWeightCardinality/3, innerNodeColor/2, innerLeftRight/3, num/1, max_total_weight/1 

Input format

An input consists of the following parts:

1. n leaves are given with corresponding weight and cardinality (there are 1..n leaves):

leafWeightCardinality(leaf1,w1,c1).
...
leafWeightCardinality(leafn,wn,cn).
where w1..wn, c1..cn are integers.

• b. The number of leaves in the tree is given by num(n).

  c. Integer mv is given by max_total_weight(mv). d. n-1 inner nodes are given:

  innerNode(1).
  ...
  innerNode(n-1).

Output format

A solution is represented by means of a constant "exists" if there is a tree T and a specification of T in the following format

 innerNodeColor(1,color1)
 ...
 innerNodeColor(n-1,color_n-1)
 innerLeftRight(1,leafL_id_1, leafR_id_1).
 ..
 innerLeftRight(n-1,n-2, leafR_id_n-1).
 leafWeightCardinality/3. %as in input instance
 ...
 max_total_weight/1.     %as in input instance  
 num/1.                  %as in input instance           

Otherwise, no answer set is returned.

Example(s)

Given:

leafWeightCardinality(leaf1,4,5).
leafWeightCardinality(leaf2,3,7).

innerNode(1).

num(2).
max_total_weight(9).

Output contains:

exists.
leafWeightCardinality(leaf1,4,5).
leafWeightCardinality(leaf2,3,7).
innerNodeColor(1,red). 
innerLeftRight(1,leaf2,leaf1).
max_total_weight(9).
num(2).

Explanation: Total weight of the tree in the output is 7.

Author(s)

• Author: Yuliya Lierler
  • Affiliation: University of Kentucky and Texas Tech