3
$\begingroup$

Box-Depth Problem:

Given $n$ rectangles, such that their sides are parralel to the coordinate axes ($x$ and $y$), Find a subset with maximum size such that the intersection of its members are not empty.

Max-Clique Problem:

A simple graph $G$ is given. What is the size of the biggest complete subgraph (clique) of $G$?

Question:

Polynomially Reduce Box-Depth Problem to Max-Clique Problem. (Provide a translation function)

Note: I was thinking of seeing a rectangle as a clique with $4$ nodes... But, This doesn't work out... Because this way, All of the cliques are of size $4$, and the answer to the problem would be always $4$... which is incorrect.

$\endgroup$
1
  • 1
    $\begingroup$ Hint : See a rectangle as a one vertex and edge means two rectangles are overlapping $\endgroup$
    – user275490
    Commented Jun 7, 2017 at 14:36

1 Answer 1

Reset to default
1
$\begingroup$

Hint.

You want to build a graph whose nodes are the rectangles. Two nodes are connected by an edge when the rectangles intersect.

How can you tell if a pair of rectangles intersect? Can you decide that for all pairs of rectangles in polynomial time?

Edit: My second thoughts led me to doubt this solution. A clique in the graph is set of rectangles each pair of which intersect, but the question calls for a set with an empty intersection.

My third thoughts are that this is not a problem. For arbitrary rectangles, three can intersect in pairs without having a common point. But I am pretty sure you can prove that for any finite set of rectangles with axes parallel to the coordinate axes, pairwise intersection implies intersection. I'll leave it up as a cautionary tale.

$\endgroup$
4
  • $\begingroup$ Excuse me... I don't get the idea... I'm lost somehow... Would you please explain more? $\endgroup$
    – Arman Malekzadeh
    Commented Jun 7, 2017 at 14:37
  • $\begingroup$ I can tell if just $2$ rectangles are given... By the coordinates, it can be done easily... But, all pairs means $n$ choose $2$, which is exponential. Am i right? $\endgroup$
    – Arman Malekzadeh
    Commented Jun 7, 2017 at 14:39
  • $\begingroup$ $n$ choose $2$ is quadratic in $n$. There's an easy formula for it. $\endgroup$
    – Ethan Bolker
    Commented Jun 7, 2017 at 14:43
  • $\begingroup$ Yes you're right... My mistake... :) $\endgroup$
    – Arman Malekzadeh
    Commented Jun 7, 2017 at 14:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .