2025-288

A Flamengo fan living in Campinas made a promise that if their team reached the final of the 2025 Libertadores de America Cup, they would visit all the stadiums where Flamengo played during the knockout stages. Now that Flamengo has indeed made it to the final, the fan must fulfill their promise before returning home to Campinas to catch a flight to Lima for the final.

To plan the most efficient route, the fan created a simplified map in the form of a graph, where each node represents a stadium and each edge is weighted by the distance between stadiums. Using the Cheapest Insertion heuristic, they determined their itinerary.

What is the total distance to be covered on this journey?

A) 4085 Km

B) 4135 Km

C) 4140 Km

D) 5815 Km

E) None of the above

Original idea by: Eduardo Bouhid

2025-287

Considering the Traveling Salesman Problem (TSP) in a complete graph where the triangular inequality holds, which of the following statements most accurately describes the fundamental difference in tour construction and performance guarantee between the Rosenkrantz-Stearns-Lewis algorithm and the Christofides algorithm?

1. Both algorithms are based on the "Farthest Insertion" heuristic, but Christofides applies additional optimization using dynamic programming to achieve a 1.5 x optimal cost guarantee, while Rosenkrantz-Stearns-Lewis does not.


2. Christofides' algorithm uses minimum perfect matching over the odd degree nodes of the minimum spanning tree (MST) to construct an Eulerian graph, achieving an approximation guarantee of 1.5 x optimal cost. In contrast, the Rosenkrantz-Stearns-Lewis algorithm duplicates all edges of the MST, resulting in a guarantee of 2 x optimal cost.


3. The Rosenkrantz-Stearns-Lewis algorithm duplicates the edges of the MST to form an Eulerian tour, and the Christofides algorithm improves on this by finding a minimum perfect match on all nodes in the graph (not just those of odd degree), but both algorithms share the same 2 x cost-optimal performance guarantee.


4. The Rosenkrantz-Stearns-Lewis algorithm uses a minimum perfect match over the odd degree nodes of the MST, achieving a 1.5 x optimal cost guarantee, while the Christofides algorithm duplicates all MST edges, achieving a 2 x optimal cost guarantee.


5. None of the above.

Original idea by: Juan Jose Rodriguez Rodriguez

2025-286

The Euclidean Traveling Salesman Problem (Euclidean TSP) is a special case of the symmetric TSP where each city corresponds to a point in \(\mathbb{R}^d\) and costs equal the Euclidean distance between points. As the Euclidean distance is symmetric and satisfies the triangle inequality, Euclidean TSP is a special case of Metric TSP, allowing approximation algorithms to be used for a solution.

Consider the Euclidean TSP on 5 cities, located in \(\mathbb{R}^2\) at

A (0, 0); B (2, 0); C (2, 1); D (0, 1); E (1, 1).

Which of the following statements is true?

1. The Nearest Neighbor heuristic starting from any node always yields a tour of cost 6.
2. Any Euclidean TSP can be solved in polynomial time using the ILP formulation.
3. The optimal tour is achieved by ABCED, costing 5.
4. The Cheapest Insertion heuristic is better than the Nearest Neighbor for any starting single-node cycle. 
5. None of the above

Original idea by: Daniel Gardin

2025-285

The graph below is an input instance for the Traveling Salesperson Problem showing the weight of each link between nodes. Considering that links not shown have infinite weight, find the correct alternative.

a) Using the Closest Neighbor heuristic, starting from node 'a' will result in the cycle a-c-d-f-e-b-a, with a total cost of 19.

b) Using the Closest Neighbor heuristic, any starting node will result in a total cost of 16.

c) Using the Cheapest Insertion heuristic, starting from the cycle a-b-c-a will result in a final cost of 16.

d) Using the Closest Neighbor heuristic, starting from node 'a' will result in the cycle a-b-e-c-d-f-a, with a total cost of 16.

e) None of the above.

 

 Original idea  by: Giorgio Rossa

2025-284

Solve the Travel Salesperson Problem for the following undirected weighted graph and pick the best answer:

A) Cycle ABCDEA with weight 24

B) Cycle ABCEDA with weight 20

C) Cycle ADEBCA with weight 18

D) Cycle AEBCDA with weight 19

E) None of the above

Original question by: Raphael Adamski

2025-283

A post office must plan a route to visit five cities (A, B, C, D, E) and return to the start. Distances (cost units) are given in the graph below. The graph satisfies the triangle inequality and is undirected. Apply the cheapest insertion heuristic (from the traveling salesperson problem), starting with triangle ABC (initial cycle: A → B → C → A). At each step, insert the vertex that yields the smallest cost increase according to the cheapest insertion heuristic. Which final cycle is obtained and what is its total cost?

A) A → C → B → D → E → A, total cost 29

B) A → B → E → D → C → A, total cost 27

C) A → B → D → C → E → A, total cost 25

D) A → D → B → E → C → A, total cost 27

E) None of the above

Original idea by: Thiago Soares Laitz

2025-282

A large, undirected network, with no self-loops or multi-links, is analyzed. It exhibits a scale-free degree distribution described by the formula \(p(k) = k^\gamma\) with an exponent \(\gamma=2.5\). Empirical measurement yields a degree correlation coefficient \(r = -0.15\). A plot of the average nearest-neighbor degree \(k_{nn}(k)\) shows relatively independency of the degree \(k\) for small \(k\), but it begins to decay for nodes with \(k > \sqrt{\langle k\rangle N}\), where \(N\) is the network size. What is the most precise classification of this network's degree correlations?

A)  The network is intrinsically disassortative;

B) The network exhibits structural disassortativity, a phenomenon affecting scale-free networks with exponent \(\gamma < 3\) and the network's nature;

C) The network is neutral, as the average nearest-neighbor degree is independent of \(k\) for most nodes and \(r\) is close to 0;

D) The network is assortative, but the measurement is skewed by the high variance of high-degree nodes;

E)  None of the above.

Original idea: Caio Rhoden