Parameterized Complexity of Even Set Definitions

Parameterized Complexity of Even Set (and others) D niel Marx Hungarian Academy of Sciences Dagstuhl Seminar 19041 January 25, 2019 L BELM BGKM BBEGKLMM [1] Bingkai Lin, SODA 2015, JACM 2018 [2] Bonnet, Egri, Lin, M. , unpublished [3] Bhattacharyya, Ghoshal, Kartik C.S., Manurangsi, ICALP 2018

Hitting Set and Variants { { } HITTING UNIQUE HITTING ODD EVEN ODD/EVEN } MINIMUM EXACT { } SET All of them are known to be W[1]-hard, except MINIMUM EVEN SET (note: solution is required to be nonempty). Dual form: SET COVER and friends.

EVEN SET definitions Hypergraphs (EVEN HITTING SET) Bipartite Graphs (RED-BLUE DOMINATING SET) Linear Algebra (MINIMUM DEPENDENT SET) Find a nonempty vector ? ?2 most ? such that ?? = 0. Matroid Theory (SHORTEST CIRCUIT): Find a circuit of size at most ? in a binary matroid Coding Theory (MINIMUM DISTANCE): Find a nonempty codeword of Hamming weight at most ?. ? with Hamming weight at

Coding theory ? Generating matrix: ? ?2 ?} ? = ?? ? ?2 Codewords: ? ? ? ? = 0 Fact: distance, systematic code, Sphere packing bound,

W[1]-hardness of ODD SET ?1 ?2 ?3 ?4 ?1,2 ?1,3 ?1,4 ?2,3 ?2,4 ?3,4

? Odd Set Even Set

? Odd Set Even Set Gap Odd Set Gap Even Set

? Odd Set Even Set Gap Odd Set Gap Even Set

BICLIQUE Given a bipartite graph ? and integer ?, find two sets ? and ? of size ? that are fully adjacent to each other. Should have been on the Downey-Fellows list. Easy to give an incorrect proof (which works only for PARTITIONED BICLIQUE) Theorem: BICLIQUE is W[1]-hard [Bingkai Lin, SODA 15, JACM 18]

Template graph ?,?,?, -threshold property for a bipartite graph on ? = (?1, ,??) and ?: For any ? + 1 vertices in ? have at most ? common neighbors. For any choice of ? sets ??1, ,???, we can find one vertex in each set such that these ? vertices have at least common neighbors. There are randomized constructions for such graphs with ? = ?(?2) and = ? (1 ?)(deterministic construction is worse).

The reduction ? 2 vertices with common neighbors ? clique Any ? has ? common neighbors 2 vertices no ? clique

Hardness of BICLIQUE We reduced ?-CLIQUE to ? 2-BICLIQUE. Theorem: BICLIQUE is W[1]-hard and no ? ? ??( ?) algorithm assuming randomized ETH. Approximation version: ONE SIDED BICLIQUE Find ? vertices maximizing the common intersection Hard to distinguish between optimum of ?2 and ? (1 ?)

Randomized construction Random graph on ?2+ ?2 vertices with edge probability ? = ? 2 ?+1+?+1 +2 (?+1)(?+1) Claim 1: probability of ? + 1 vertices with ? + 1 common vertices is at most ? 2. Claim 2: probability of a given set of ? vertices do not have common neighbors is less than ? 1 4?.

LINEAR DEPENDENT SET ?, find ? vectors that Given vectors ?1, ,?? ?? are linearly dependent. ?? = 0 s.t. ? has Hamming weight at most ? Hard to approximate for any constant: proof by reduction from ONE SIDED BICLIQUE.

Encoding vertices Vertex set ? = ?1, ,?? vectors in ?(?1), ,?(??) ?? any ? 1 are linearly independent any ? are linearly dependent ? 1 such that Vertex set B= ?1, ,?? vectors in ?(?1), ,?(??) ?? any 1 are linearly independent any are linearly dependent 1 such that (Vandermonde matrices)

Reduction edge ? = {??,??} F(e) block ? block ? ?(??) ?(??) REALLY! REALLY!

Reduction ? biclique ? linearly dependent sets no ? ? biclique no ?? linearly dependent sets (if is sufficiently large)

COLORED LINEAR DEPENDENT SET Vectors partitioned into ? color classes, distinguish between exists dependent set of ? vectors, one from each color, no dependent set of ? vectors (or arbitrary colors!) Simple reduction from the uncolored version using Color Coding (Turing or not)

MAXIMUM LIKELIHOOD DECODING ? ? and ? ?2 ?, find ? ?2 ?of Hamming Given ? ?2 weight at most ? such that ?? = ?. = ODD/EVEN SET Reduction from COLORED LINEAR DEPENDENT SET. Tool: ?2? as ?-bit vectors.

Reduction Colored ? dependent set MLD solution of weight ? no dependent set of size 3? No MLD solution of weight 3?

NEAREST CODEWORD ? ? and ? ?2 ?, find ? ?2 ?such that Given ? ?2 ?? ? has Hamming weight at most ?. Sparse version: in a YES instance, exists solution ? of Hamming weight at most ?. Inapproximability by an easy reduction from MAXIMUM LIKELIHOOD DECODING.

Minimum Distance (finally!) SPARSE NEAREST CODEWORD Given ? ?2 Hamming weight at most ?. ? ?, find ? ?2 ?such that ?? ? has MINIMUM DISTANCE Given ? ?2 that ?? has Hamming weight at most ?. ? ? and ? ?2 ?, find ? ?2 ?of such

Reduction codeword at distance ? Distance is at most ? no codeword at distance 5? Distance is at least 1.25?

Increasing the gap ?, the Codes ?1,?2with matrices ?1,?2 ?2 tensor product is the code ? ?} ? ? ?2 Fact: dist ?1 ?2 = dist(?1)dist ?2 ?1 ?2= ?1??2 Any ? > 1 inapproximability for MINIMUM DISTANCE can be boosted to ?2 and hence to any constant. Theorem: MINIMUM DISTANCE (EVEN SET etc.) is randomized W[1]-hard to approximate for any > 1.

Integer Lattice problems SHORTEST VECTOR Given a matrix ? ? ? and integer ?, find a vector ? ? {0} with ??? ? ?. NEAREST VECTOR Given a matrix ? ? ? , vector ? ? and integer ?, find an ? ? {0} with ?? ?? ? ?. Theorem: SHORTEST VECTOR for any ? > 1 and NEAREST VECTOR for any ? 1 is randomized W[1]-hard to approximate for any constant > 1.

Summary CLIQUE ONE SIDED BICLIQUE LINEAR DEPENDENT SET MAXIMUM LIKELIHOOD DECODING (SPARSE) NEAREST CODEWORD MINIMUM DISTANCE Transferring inapproximability results can be easier than transferring exact hardness!