How to solve Line Line Line Graph

Can anyone provide any hints for solving this problem?
Problem Link: CodeChef: Practical coding for everyone

2 Likes

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)

2 Likes

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.

2 Likes

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.

3 Likes