How to solve Line Line Line Graph

Can anyone provide any hints for solving this problem?
Problem Link:


How to solve it for 30 points?

For 30 points you can go through this link

The setters solution passes it for 30 points as largest independent set in L(G) = maximum matching in G so you just output max_matching size .

Edmonds’ blossom algorithm can be used on the given graph.Its answer will be the LIS of the corresponding line graph L(G)


For K >= 2 you will have edges such that your matching for each connected component in the graph will be equal to floor(number of nodes / 2).

So the task reduces to finding the number of nodes which you can do for upto K = 6 in O(n + m). If K = 7, just build L(G) and reduce K by 1

1 Like

Thank you.

How to find number of nodes for K >= 3?

It’s a bit hard to explain without diagrams.

For K = 3, The number of nodes will be equal to \sum_{i = 0}^{V-1} (Adj[i].size()) C_2, So update each node with the value Adj[i].size(). This is useful for future calculations.

For K = 4, It’s equivalent to finding K = 3 in L(G). This means I have to update the values in edges to it’s adjacency list size in L(G) as this edge is a node there. Turns out that Adj[i].size() for a node in L(G) which is an edge in G connecting u, v is equal to Adj[u].size() + Adj[v].size() - 2 as that’s how many edges are connected to this edge in G. So update the Edge with this value (Let’s say X_i) and the answer is summation of X_iC_2

Notice that whatever values you updated for the Edge in K = 4 will be updated to the vertex in L(G) for K = 3.

For K = 5, You need that summation X_iC_2 from L(G). In order to find that you need to know what forms an edge in L(G). An edge is formed in L(G) when 2 edges are adjacent in G so your required answer will be \sum XiC2 for all edge i in L(G). which is equal to

half of \forall \ vertices \ in \ G \sum_{i }^{vertices \ in \ Adj[v]} \sum_{j \ != \ i}^{vertices \ in \ Adj[v]} (X_{j, v} + X_{i,v} - 2)C_2

(a + b) C _ 2 = aC_2 + bC_2 + ab

= \sum_i\sum_j X_{i,v}C_2 + X_{j,v}C2 + X_{i,v}X_{j,v}

All three terms simplify to O(1) after calculations of \sum X_{i,v} and \sum X_{i,v}^2 in O(n)

For K = 6 It is similar to the above process by taking 3 edges at a time with one edge being common (All 3 must be connected in one component if considered as a seperate graph). The formula becomes a bit more complicated here and hence Im skipping it.


How did you find the number of nodes in each connected component?

Thanks. I expected it to be some generalized method, but it seems caseworks for each K.