[Rule] KSatisfiability/K3 to BicliqueCover

[GiggleLiu]

[Rule] KSatisfiability/K3 to BicliqueCover

Source

KSatisfiability with variant K3.

Target

BicliqueCover.

Motivation

BicliqueCover is connected forward to BMF and ILP, but there is no direct NP-hardness bridge from 3SAT/KSatisfiability into BicliqueCover.

This rule adds a source-backed direct construction:

KSatisfiability/K3 -> BicliqueCover

The reduction is useful because Chandran, Issac, and Karrenbauer give a polynomial-time reduction from 3SAT to BicliqueCover with logarithmic biclique-cover rank. This is stronger than routing through graph coloring when the rank parameter matters.

Reference

Primary construction:

S. Chandran, D. Issac, and A. Karrenbauer, "On the Parameterized Complexity of Biclique Cover and Partition", IPEC 2016, Theorem 6 and Section 3.

Repository reference PDF:

docs/research/raw/chandran2016-biclique-cover-partition.pdf

The issue draft was prepared from the paper's Theorem 6, Section 3 construction, Lemma 16, Lemma 17, Lemma 18, and Lemma 19.

Reduction Algorithm

Input: a 3-CNF formula psi with variables x_1, ..., x_n and clauses C_1, ..., C_m, where each clause has exactly three literals.

1. Normalize the source formula

The paper assumes:

n = 2^ell
every satisfying assignment has exactly n/2 true variables

For implementation, normalize an arbitrary 3SAT instance before applying the paper gadget:

1. For each original variable x_i, create two normalized variables t_i and f_i.
2. Replace literal x_i by t_i.
3. Replace literal not x_i by f_i.
4. Add clauses enforcing exactly one of t_i, f_i:

(t_i OR f_i OR f_i)
(not t_i OR not f_i OR not f_i)

5. Add dummy exactly-one pairs until the total number of normalized variables is a power of two.

After normalization, let:

n = 2^ell              normalized variable count
m = normalized clause count

Every satisfying normalized assignment has exactly n/2 true variables.

2. Build the target bipartite graph

Construct a bipartite graph G = (U, V, E) for BicliqueCover.

Partition the edges into:

E_imp   important edges
E_free  free edges

The free edges are forced to use exactly k_f bicliques that do not cover important edges. Satisfiability is encoded by whether the important edges can be covered with 2ell + 2 more bicliques.

3. Add the crown graph H

Create a crown graph H_n.

U(H) = {h_i^u : i in [n]}
V(H) = {h_i^v : i in [n]}

Add important edges:

h_i^u h_j^v for all i != j

The missing pairs h_i^u h_i^v represent the positive/negative conflict for variable x_i.

4. Add clause gadgets P_i

For each clause C_i, add an induced matching P_i of size 3:

U(P_i) = {p_i1^u, p_i2^u, p_i3^u}
V(P_i) = {p_i1^v, p_i2^v, p_i3^v}

Add important edges:

p_ia^u p_ia^v for a in {1,2,3}

Edge p_ia^u p_ia^v corresponds to literal C_i^a.

5. Add domino gadgets S_j

For each j in [ell], add a domino graph S_j:

U(S_j) = {s_j1^u, s_j2^u, s_j3^u}
V(S_j) = {s_j1^v, s_j2^v, s_j3^v}

Add the domino's seven important edges:

(s_j1^u, s_j1^v)
(s_j1^u, s_j2^v)
(s_j2^u, s_j1^v)
(s_j2^u, s_j2^v)
(s_j2^u, s_j3^v)
(s_j3^u, s_j2^v)
(s_j3^u, s_j3^v)

The pair of bicliques covering each domino induces a duplex biclique cover of the crown graph.

6. Add guard gadget Q

Add an induced matching Q of size 2:

U(Q) = {q_1^u, q_2^u}
V(Q) = {q_1^v, q_2^v}

Add important edges:

q_1^u q_1^v
q_2^u q_2^v

Note: the paper's text uses Q in the construction and lemmas but does not spell out the vertex definition in the same explicit list as H, P, S, and Y. The proof of Lemmas 18 and 19 requires Q to be this induced matching of size 2.

7. Add important edges between H and S

For every j in [ell] and i in [n], add:

s_j2^u h_i^v
s_j2^v h_i^u

These are important edges.

8. Add free edges between H and S

For every j in [ell] and i in [n], add:

s_j1^u h_i^v
s_j3^u h_i^v
s_j1^v h_i^u
s_j3^v h_i^u

These are free edges.

9. Add free edges between clause gadgets

For all distinct clauses i != j, add every edge from U(P_i) to V(P_j).

These are free edges.

10. Add free edges between P and Q

For every clause gadget P_i, add all edges:

U(Q) x V(P_i)
U(P_i) x V(Q)

These are free edges.

11. Add free edges between H and P

For each literal edge p_ia^u p_ia^v corresponding to literal C_i^a:

add p_ia^u h_j^v unless C_i^a is the positive literal x_j
add p_ia^v h_j^u unless C_i^a is the negative literal not x_j

These are free edges.

12. Add free edges between S_1 and P

Only the first domino gadget connects to the clause gadgets:

s_11^u and s_12^u connect to all vertices in V(P_i), for all i
s_11^v and s_12^v connect to all vertices in U(P_i), for all i

These are free edges.

13. Cover the non-Y free edges with k_f bicliques

Let:

k_f = 4ell + 2ceil(log2 m) + 6

The free-edge cover from Lemma 16 consists of:

2 bicliques for H-S free edges
2ceil(log2 m) bicliques for P-P free edges
2 bicliques for P-Q free edges
4ell bicliques for H-P free edges
2 bicliques for S-P free edges

Call these bicliques:

B_1^f, ..., B_kf^f

14. Add the forcing matching Y

Create an induced matching Y of size k_f:

U(Y) = {y_r^u : r in [k_f]}
V(Y) = {y_r^v : r in [k_f]}

For every r, add the matching edge:

y_r^u y_r^v

This is a free edge.

Make edge y_r^u y_r^v bisimplicial with respect to B_r^f:

add y_r^u to every right vertex of B_r^f
add every left vertex of B_r^f to y_r^v

Equivalently, add:

y_r^u v for every v in V(B_r^f)
u y_r^v for every u in U(B_r^f)

These are free edges.

By Lemma 17, every cover of all free edges uses k_f bicliques that contain no important edge.

15. Set the target rank

Set the BicliqueCover rank to:

k = k_f + 2ell + 2

The target instance is:

BicliqueCover(G, k)

Correctness

Forward direction

Assume psi is satisfiable. By normalization, take a satisfying assignment with exactly n/2 true variables.

For each clause, choose one satisfied literal edge e_i in P_i.

Use two guard bicliques to cover:

q_1^u q_1^v
q_2^u q_2^v

and two of the three important edges in each P_i, leaving exactly the chosen satisfied edge e_i uncovered.

The satisfying assignment defines a duplex biclique pair B_1, \bar{B}_1 in the crown graph H. Lemma 13 in the paper extends it to ell duplex biclique pairs covering all important edges in H.

Extend those 2ell bicliques into the domino gadgets. Extend B_1 further through S_1 and the chosen satisfied literal edges e_i. The edges omitted in the H-P construction ensure that B_1 can include only literal edges satisfied by the assignment.

Together, the 2ell crown/domino bicliques plus the two guard bicliques cover all important edges. Lemma 17 covers the free edges with k_f additional bicliques. Therefore G has a biclique cover of size:

k_f + 2ell + 2

Reverse direction

Assume G has a biclique cover of size k_f + 2ell + 2.

By Lemma 17, k_f bicliques are consumed by the free-edge forcing matching Y, and they contain no important edge. Thus only 2ell + 2 bicliques remain for important edges.

The important edges:

q_1^u q_1^v
q_2^u q_2^v
s_j1^u s_j1^v for all j in [ell]
s_j3^u s_j3^v for all j in [ell]

form an induced matching of size 2ell + 2, so each must be covered by a distinct important-edge biclique.

Let:

B_1^g, B_2^g

cover the two Q edges. Let:

B_j, \bar{B}_j

cover s_j1^u s_j1^v and s_j3^u s_j3^v.

The edges from each middle domino vertex s_j2 to H force {B_j, \bar{B}_j} to induce a duplex biclique pair on H. In particular, {B_1, \bar{B}_1} selects exactly one side of each missing crown pair.

The guard bicliques cover at most two of the three important edges in each clause gadget P_i, so at least one literal edge e_i in each P_i must be covered by a biclique other than the two guard bicliques. Because only S_1 is connected to P, and because the third vertices of S_1 block \bar{B}_1, each such e_i must be covered by B_1.

Extract an assignment from B_1:

x_i = true  if h_i^u is in B_1
x_i = false otherwise

If the chosen literal edge e_i for clause C_i corresponds to positive literal x_j, then the construction omitted the edge from its endpoint to h_j^v; since e_i is covered by B_1, h_j^v cannot be in B_1, so h_j^u is in B_1 and x_j = true.

If e_i corresponds to negative literal not x_j, the symmetric argument gives x_j = false.

Thus each clause has a satisfied literal, and psi is satisfiable.

Solution Extraction

Given a valid BicliqueCover witness:

1. Ignore bicliques that cover the Y matching edges; by Lemma 17 these are the free-edge bicliques.
2. Identify the biclique B_1 covering edge s_11^u s_11^v.
3. For each normalized variable x_i, set:

x_i = true  if h_i^u is in B_1
x_i = false otherwise

4. Map the normalized variables back to the original source variables by reading each original t_i.

Size Overhead

Let the normalized source have:

n = num_vars = 2^ell
m = num_clauses

Target size fields for BicliqueCover are num_vertices, num_edges, and rank.

Target metric	Formula
num_vertices	2*n + 6*m + 6*ell + 4 + 2*k_f
rank	k_f + 2*ell + 2, where k_f = 4*ell + 2*ceil(log2 m) + 6
num_edges	O((n + m + ell + k_f)^2)

The paper states |U(G)| + |V(G)| = O(n + m) and k = O(log n) for formulas with m polynomially bounded in n. In implementation metadata, use a conservative polynomial edge bound because the graph is represented by an explicit edge list.

More detailed edge-count components:

• H: n(n-1) important edges.
• Clause gadgets P: 3m important edges.
• Domino gadgets S: 7ell important edges.
• Guard gadget Q: 2 important edges.
• Important H-S: 2ell*n edges.
• Free H-S: 4ell*n edges.
• Free P-P: 9m(m-1) directed cross-gadget edges.
• Free P-Q: 12m edges.
• Free H-P: at most 6mn edges, minus omitted literal conflicts.
• Free S-P: 12m edges.
• Y: k_f matching edges plus bisimplicial edges into the chosen free-edge bicliques.

Validation Method

Implementation should include:

1. A closed-loop YES test on a small satisfiable 3-CNF formula after normalization.
2. A closed-loop NO test on an unsatisfiable 3-CNF formula.
3. A structure test checking the constructed gadget counts: H, P, S, Q, Y, and target rank.
4. A witness extraction test: solve the target BicliqueCover instance, extract a normalized assignment from B_1, map it back, and verify it satisfies the source.
5. A negative test that changing/removing the Q guard or Y forcing edges breaks the expected budget, since these are easy implementation mistakes.

The implementation PR should run the repo's verify-reduction workflow because the construction is subtle.

Example

Use a satisfiable formula with four normalized variables so n is already a power of two:

variables: x_1, x_2, x_3, x_4
clauses:
  C_1 = (x_1 OR x_2 OR x_3)
  C_2 = (not x_1 OR x_3 OR x_4)

A satisfying balanced assignment is:

x_1 = true
x_2 = false
x_3 = false
x_4 = true

Here:

n = 4
m = 2
ell = 2
k_f = 4*2 + 2*ceil(log2 2) + 6 = 16
rank = k = 16 + 2*2 + 2 = 22

Target gadgets:

H: crown graph H_4
P_1, P_2: two clause induced matchings, each of size 3
S_1, S_2: two domino gadgets
Q: induced matching of size 2
Y: induced matching of size 16

The selected satisfied literal edges can be:

e_1 = edge for literal x_1 in C_1
e_2 = edge for literal x_4 in C_2

The biclique B_1 used for extraction contains:

h_1^u, h_4^u
h_2^v, h_3^v

so extraction recovers exactly:

x_1 = true
x_2 = false
x_3 = false
x_4 = true

This example is intended for a structure/witness test. The PR should also include a smaller NO formula for infeasibility preservation.

Implementation Notes

The paper text has a minor presentation inconsistency: one summary line mentions i in [ell - 1] for the H-S edges, while the construction and proof use domino gadgets S_1, ..., S_ell and need the relevant H-S edges for all i in [ell]. Follow the construction/proof lemmas, not the inconsistent summary line.

BibTeX

@InProceedings{chandran_et_al:LIPIcs.IPEC.2016.11,
  author = {Chandran, Sunil and Issac, Davis and Karrenbauer, Andreas},
  title = {{On the Parameterized Complexity of Biclique Cover and Partition}},
  booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages = {11:1--11:13},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN = {978-3-95977-023-1},
  ISSN = {1868-8969},
  year = {2017},
  volume = {63},
  editor = {Guo, Jiong and Hermelin, Danny},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik},
  address = {Dagstuhl, Germany},
  URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.11},
  URN = {urn:nbn:de:0030-drops-69293},
  doi = {10.4230/LIPIcs.IPEC.2016.11}
}