Hidden Graph

Time limit5sMemory limit512 MB

Summary
Find a hidden undirected graph on n vertices, where every induced subgraph has a vertex of degree at most k, using at most 2nk+n independence queries that return an edge when the set is not independent.
Level

Hard8 of 10

Topics
Graph, Divide and conquer, Greedy, Implementation
Solved
No attempts yet

Problem

There is a simple undirected graph with nn vertices. This graph satisfies one additional property:

  • Every induced subgraph contains a vertex with degree at most kk.

You need to find this hidden graph. You can check whether any subset is an independent set. If it is not an independent set, we will show you one edge with both endpoints inside that set.

We do not change the graph during the interaction, so you may assume it is fixed.

However, we may choose which edge inside the induced subgraph to show.

In other words, in every test the graph is fixed, but the interactor is adaptive.

You need to determine the graph in at most 2nk+n2nk+n queries.

Examples1

  1. Example 1

    Input
    3
1 2
2 3
1 3
    Expected output
    ? 2 1 2
? 2 2 3
? 2 1 3
! 3
1 2
2 3
1 3