5
$\begingroup$

Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every vertex $i_1$ has only $1$ outgoing hyperedge $\{i_1\rightarrow i_2,i_3,i_4,\dots,i_{c^a}\}\in\mathcal{E}(\mathcal{H}(a))$ which has $c^a$ vertices and every vertex is on $(c+d)^a$ hyperedges).

Consider the NP-complete HYPERGRAPH-MAXDICUT problem of given an integer $t$ and a hypergraph $\mathcal{H}(a)$ with above parameters, one has to decide if there is a subset $S \subset \mathcal{V}(\mathcal{H}(a))$ such that $$|\{\mathcal{I}=\{i_1\rightarrow i_2,i_3,i_4,\dots,i_{c^a}\}\in\mathcal{E}(\mathcal{H}(a))\mid i_1\in S \text{ and } \mathcal{I}\setminus i_1\cap S=\emptyset\}|\geq t$$

Can there be a $c^{a^{\beta}}$ approximation algorithm to HYPERGRAPH-MAXDICUT where $\beta\in(0,1)$? For which classes of $\mathcal{H}(a)$ could we have such approximation?

If $n$ is variable how does the factor depend on both $a$ and $n$?

$\endgroup$
  • $\begingroup$ I do not understand the parameterization of the problem. Which factors go to infinity and which are fixed constants? Why not just ask about a $(n, \Delta, 1)$-regular "directed hypergraph"? $\endgroup$ – Sasho Nikolov Oct 4 '13 at 21:25
  • $\begingroup$ Is there anything ambiguous as framed here? Everything is fixed except $a$. $\endgroup$ – T.... Oct 4 '13 at 22:19
  • 2
    $\begingroup$ yes, the ambiguous thing for me is that you want approximation factor "independent of $n$", where $n$ is a fixed constant. Do you mean independent of max degree and number of vertices? Or if not, how is what you mean different? $\endgroup$ – Sasho Nikolov Oct 4 '13 at 22:23
  • 1
    $\begingroup$ Maybe I'm missing something but how can $d > 0$? If each vertex is the head of at most one hyperedge, then there are at most $n$ edges in the graph, i.e., the total degree is at most $c^a n$ and hence the average degree, i.e. the number of edges each (regular) vertex partakes is in, is at most $c^a$. $\endgroup$ – c.lorenz Oct 6 '13 at 3:40
  • 2
    $\begingroup$ Are the instances produced in a special way using the parameter $a$ which might lend an structure exploitable by approximation algorithms? $\endgroup$ – c.lorenz Oct 6 '13 at 9:54
1
$\begingroup$

This is perhaps not entirely satisfactory since you asked for an approximation rather than a hardness result but there is no constant independent of $a$ for which the problem can be approximated to within via an FGLSS-like reduction.

Unless P=NP, for every $\epsilon > 0$, there exists $c_0$ such that there is no poly-time $\epsilon$-approximation for Hypergraph-DiCut (HDC) instances on $c_0 \le c$-uniform hypergraphs.

Note that this covers the original question since for any $c > 1$, one can take $a$ sufficiently large so that $c^a \ge c_0$; if $a$ grows with $n$, the problem only becomes harder to approximate. It is also easy to artificially increase $c$ in the sense that if one has approximation hardness for any $c$, then one also has an approximation hardness for $c' \ge c$ (ignoring rounding). (see below for details)

Let me tell you the basic idea first and then do it properly.

Example Reduction from 3SAT

We know that it is NP-hard to distinguish satisfiable 3SAT instances from, say, 88%-satisfiable instances. 3SAT can be reduced to your problem like this: for each clause $C$, such as $(x_3 \lor \lnot x_5 \lor x_6)$, we introduce seven vertices - one for each of the seven satisfying assignments to these three variables, such as $(x_3=1, x_5=0, x_6=1)$. For each of these vertices $v$, we have a hyperedge where $v$ is the head and the tail consists of the six other assignments. This way, we force a solution to include in $S$ at most one of the assignments (for simplicity, we may assume that $S$ only contains vertices such that they are the head of a satisfied hyperedge). We also include in the tail of the hyperedge every other vertex that shares a variable with the clause $C$, and where the assignments of shared variables are inconsistent.

As an example, if we also have the clause $(x_3 \lor x_8 \lor x_9)$, we include in the tail of the hyperedge where $(x_3=1, x_5=0, x_6=1)$ is the head, the vertices corresponding to $(x_3=0, x_8=0, x_9=1), (x_3=0, x_8=1, x_9=0)$, and $(x_3=1, x_8=1, x_9=1)$. Note that these are added to the tail, so the hyperedge both rules out inconsistent assignments to the original clause as well as inconsistent assignments of clauses with common variables.

This way, we can now only choose cuts $S$ where the assignments to variables are consistent and each cut hyperedge corresponds to one satisfied clause. In fact, the optimal cuts will correspond precisely to the optimal simultaneously satisfiable clauses. If we reduced from a 3SAT instance where each variable appeared in a bounded number of clauses, then the size of the constructed hyperedges will also be bounded by some constant. If the 3SAT instance was hard to approximate within, say, 0.88, then the Hypergraph DiCut problem, for sufficiently large $c$, is also hard to approximate within 0.88.

Finally, we could have done precisely the same reduction but with each vertex representing the assignment to some $r$ number of clauses with the effect that the problem becomes hard to approximate to within any constant for sufficiently wide hyperedges.

Label Cover Reduction in Detail

More carefully now, the hardness reduction is from Label Cover (LC) and is similar to the FLGSS reduction from SAT to Clique (see references).

Let $u \sim v$ indicate that the vertices $u$ and $v$ are neighbors. If a hyperedge is $k$-uniform, I will also refer to $k$ as the width of the hyperedge.

We know that for every $\epsilon > 0$, there exists fixed $L$, $R$, $d$, $\Delta$, such that for Label Cover with label sets $L$ and $R$, projection degrees at most $d$, and bipartite constraint graphs with degrees at most $\Delta$, it is NP-hard to distinguish perfectly satisfiable instances from $\epsilon$-satisfiable.

Given an LC instance $(U, V, E, \Pi)$, we consider introducing for each LC vertex $v \in V$ and label $i \in R$, an HDC vertex $(v, i)$ which represents assigning $v$ the label $i$. For each HDC vertex $(v, i)$, let $A(v, i)$ be the set of HDC vertices with conflicting assignments to $v$. That is, $A(v, i) = \{ (v, j) : i \neq j \}_{j \in R}$. Similarly, let $N(v, i)$ be the set of neighbor-of-neighbor assignments conflicting with $(v, i)$. That is, $N(v, i) = \{ (w, j) : \forall_{u \in U: v \sim u \sim w} \pi_{vu}(i) \neq \pi_{v'u}(j) \}_{w \in W, j \in R}$. For each HDC vertex $(v, i)$, we introduce an hyperedge with head $(v, i)$ and tail consisting of $A(v, i) \cup N(v, i)$. From the assumptions of the reduced-from LC instances, the cardinality of $A(v, i)$ is at most $|R|-1$ and of $N(v, i)$ at most $(|R| - d) \Delta^2$. Hence the hyperedges have width at most $|R| \Delta^2$; the hyperedges may also have smaller width but it easy to add extra variables to pad the hyperedges (see below). The tail elements $A(v,i)$ of $(v,i)$ ensure that we cannot simultaneously satisfy two hyperedges giving different assignments to $v$. The elements $N(v, i)$ ensure that we may assign a label to the neigbors $u \in U$ of $v$ such that all neighbors $w \in V$ of $u$ have projected labels which are consistent with the projection of $v$'s label; in effect, all LC edges incident $v$ are satisfied by the projected label.

For any set of HDC vertices $S$, let $H(S)$ be the set of hyperedges which have a head in $S$. Again, wlog, we may assume that a cut $S$ only contains HDC vertices which are heads of satisfied hyperedges.

Analysis

Completeness claim: if the LC instance has value 1, then the HDC instance has a cut of size $|V|$. Proof: Simply take a satisfying labeling $\lambda$ of the LC instance and let $S$ consist of the vertices $(v, \lambda(v))$ for each $v \in V$. Note that since we only take one assignment per vertex, the tail $A(v, i)$ has an empty intersection with $S$. Similarly, since the labeling satisfies all LC edges, for every $v, v' in V$ with a common neighbor $u \in U$, we have $\pi_{vu}(\lambda(v)) = \lambda(u) = \pi_{v'u}(\lambda(v'))$ and hence none of the elements in $S$ appear in the tails of the hyperedges of $H(S)$.

Soundness claim: if the LC instance has value at most $\epsilon$, then the HDC instane has no cut larger than $\epsilon |V|$. Proof: since we assume that $S$ only contains heads of satisfied hyperedges, we know that for every LC vertex $v \in V$, there is at most one label $j \in R$ such that $(v, j) \in S$. We also know that for every $u \in U$, all neighbors $v \in V$ of $u$, which have an assignment in $S$ are consistent about the projected label of $u$. Consequently, we can define the partial labeling $\lambda$ by choosing $j$ as the label for $V$ if $(v, j) \in S$ and for every neighbor $u \in U$, the label $\lambda(u) = \pi_{v,u}(j)$. This labeling satisfies at least a fraction $|S| / |V|$ of LC constraints since for each labeled $v \in V$, we satisfy all incident constraints and the LC instance is regular.

Conclusion: it is NP-hard to distinguish $|V|$-satisfiable instances from $\epsilon |V|$, i.e., it is NP-hard to approximate the problem to within a constant better than $\epsilon$ for sufficiently large hyperedge widths.

-- Caveat: The hardness result assumes that $c$ can be a large constant, i.e., $a$ reasonably large, and is therefore chiefly only of theoretical interest.

-- To reduce instances with hyperedges of width $c$ to width $c' < 2c$, introduce a copy $v'$ of each variable $v$ and call the two duals of one another. Also introduce the corresponding copy of each hyperedge. Next, replace augment every - original and copy - hyperedge $v_1 \rightarrow v_2, \dotsc, v_c$ by adding $c'-c$ dual variables as tail: $v_1 \rightarrow v_2, \dotsc, v_c, v'_2, \dotsc, v'_{c'-c}$; the new instance will have the same value (=maximum fraction of simultaneously satisfied hyperedges). To see this, suppose the original instance had value $x$ and the augmented value $y > x$. Let $S \cup S'$ be a value-$y$ solution to the augmented instance where $S$ is the set of included original vertices and $S'$ the set of included copied vertices. Then the fraction of satisfied original hyperedges or the fraction of satisfied copied hyperedges must be at least $y$. Suppose it is $S$, then we choose $S$ as the assignment to the original instance as well. Since we only added more vertices to the hyperedges, if an original edge was satisfied by $S, S'$ in the augmented instance, it is also satisfied in the original instance by $S$. In effect, the value of the original instance must have been at least $y$.

P.S. Sorry about the wall of text.

References

  • Johan Håstad. Some Optimal Inapproximaility Results. In JACM'01.

  • Feige, Goldwasser, Lovasz, Safra, and Szegedy. Approximating clique is almost NP-complete. In FOCS'91.

$\endgroup$
  • $\begingroup$ the question uses "....where the factor is in terms of a" $\endgroup$ – T.... Oct 6 '13 at 13:59
  • $\begingroup$ Well, the above simply shows that the (worst-case) approximation factor much approach 0 as $a$ grows - would such an algorithm still be of interest to you? $\endgroup$ – c.lorenz Oct 6 '13 at 18:05
  • 1
    $\begingroup$ A more careful analysis shows that there exists some constant $\alpha$ such that it is hard to approximate $c$-uniform hyperedges to within $\alpha / c$. This implies that there is no $c^{-a^\beta}$-approximation for any $\beta < 1$ as $c^a$ grows since $c^{-a^\beta} = (c^{-a})^{a^(\beta-1)} < \alpha / c^a$ for sufficiently large $c^a$. For $\beta = 1$, there is a trivial $c^{-a}$ approximation which simply chooses a uniform at random ordering of the vertices and chooses as cut those vertices preceding the tail. $\endgroup$ – c.lorenz Oct 6 '13 at 18:28
  • $\begingroup$ I need some time to study your argument. $\endgroup$ – T.... Oct 7 '13 at 2:51
  • $\begingroup$ is this non-approximability for all regaular graphs or just random regular hypergraphs? $\endgroup$ – T.... Oct 8 '13 at 21:36

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.