4
$\begingroup$

I have $n$ variables $x_1,\dots,x_n$. I'm given a set $E$ of equalities (each of the form $x_i=x_j$ for some $i,j$) and a set $I$ of inequalities (each of the form $x_i \ne x_j$ for some $i,j$). I want to find a maximum-size subset $E' \subseteq E$ such that $E'$ is compatible with $I$, i.e., such that there is an assignment to the $n$ variables that satisfies every inequality in $I$ and every equality in $E'$.

Is there an efficient algorithm for this?

I can see that the greedy algorithm (try adding equalities to $E'$ as long as doesn't imply the negation of some inequality) doesn't yield an optimal solution. I have no idea what other approaches to try.


Equivalently, the problem can be formulated in graph-theoretic terms. I'm given an undirected graph $G=(V,E)$ and a set $I \subseteq V \times V$. I want to find a maximum-cardinality subset $E' \subseteq E$ of edges, such that when I decompose the graph $G'=(V,E')$ into connected components, $v,w$ are in different connected components for all $(v,w) \in I$.

$\endgroup$
  • $\begingroup$ In simple terms: every constraint must be obeyed, equalities are subject of optimization. The solution to be found must be optimal or efficient to optimal ratio is important? What about backtracking approach? The equalities may be chained? I mean $x_i = x_j = x_k = x_l$ etc? So it may happen that backtracking is running slow? Can you estimate number of Eq and Ineq in terms of $n$? $\endgroup$ – Evil May 1 '16 at 1:09
  • $\begingroup$ @EvilJS, Yes, every inequality must be obeyed, and I'd like to obey as many equalities as possible. I'd like to know if there is a polynomial-time algorithm to find the optimum solution, but an approximation algorithm or efficient heuristic would also be interesting. As far as I can tell, backtracking can potentially take exponential time, so it doesn't answer the question (unless you have some clever way to do backtracking that you can prove will be efficient). Yes, equalities might be chained; we might have $x_1=x_2$ as one equality in $E$ and $x_2=x_3$ as another. $\endgroup$ – D.W. May 1 '16 at 1:11
  • $\begingroup$ I don't have a good estimate of the number of equalities and inequalities as a function of $n$, unfortunately. $\endgroup$ – D.W. May 1 '16 at 1:12
2
$\begingroup$

Using your graph theoretic formulation, this problem can be restated as the multi-cut problem.

Given a graph $G = (V, E)$ and a set of pairs $(s_i, t_i) \in I$ find a set of edges $E' \subseteq E$ such that there is no path $s_i \leadsto t_i$ in the resulting graph $G' = (V, E \setminus E')$ for each $i$.

Since each inequality is unweighted you need to find a minimum size multi-cut.

This problem is NP-hard in general however there exist reasonable approximation algorithms that solve an LP. However a simple strategy might be to just take the union of each $(s_i, t_i)$ cut.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.