Clique, independent set and vertex cover

Vertex pairs in encoding order to The vertex pairs are listed without repetition

• Vertex pairs in encoding order
• Adjacency bit of a vertex pair
• The graph encoded by pair bits
• Encoding of a graph instance
• Decoding a graph instance
• Fixed no-instance
• Language of graph instances with a property
• CLIQUE
• INDEPENDENT-SET
• The VERTEX-COVER problem
• Literal occurrences of a CNF formula
• Adjacency of literal occurrences in Karp's clique graph
• Adjacency bits of Karp's clique graph
• Karp's CLIQUE instance of a CNF formula
• Karp's SAT-to-CLIQUE map on bit strings
• Complementing map from CLIQUE to INDEPENDENT-SET instances
• Map from INDEPENDENT-SET to VERTEX-COVER instances
• Unparsable input is rejected
• Membership in the vertex pairs
• The vertex pairs are listed without repetition

Pair bits are read off by position to The row-by-row check of the clique verifier

• Pair bits are read off by position
• Pair bits computed by a function
• Complementing the pair bits complements the graph
• Correctness of the complementing map from CLIQUE to INDEPENDENT-SET
• Independent sets and vertex covers of complementary sizes
• Membership in the literal occurrences of a CNF formula
• Adjacency in Karp's clique graph
• Karp's reduction from SAT to CLIQUE is correct
• SAT decision on undecodable input (moved alias)
• Modes of the clique verifier
• Pair condition of the clique verifier
• The verifier for CLIQUE, INDEPENDENT-SET and VERTEX-COVER
• Vertices that settle their pairs alone
• The pair condition left to the later vertex
• The pair condition splits by vertex
• Vertex pairs in encoding order for one more vertex
• Chosen-flag pairs
• Reading a list at every index
• Chosen-flag pairs of a list with a new head
• The row-by-row check of the clique verifier

The row-by-row check is the pairwise check to Labels of the CLIQUE verifier

• The row-by-row check is the pairwise check
• The verifier as a row-by-row check
• Lookup in a list of pairs with distinct keys
• Checking each listed vertex pair against its bit
• Characterization of the CLIQUE verifier
• Counting the set bits of a list built from a function
• The first \(n\) bits of a list, read index by index
• Vertex sets meeting a mode's pair condition
• An accepted input encodes an instance with a good vertex set
• The characteristic vector of a good vertex set is accepted
• Verifying a graph language defined by a vertex-set condition
• Symmetric relations on increasing pairs
• Cliques of the graph given by pair bits
• Independent sets of the graph given by pair bits
• Vertex covers of the graph given by pair bits
• CLIQUE is verified with witnesses no longer than the input
• INDEPENDENT-SET is verified with witnesses no longer than the input
• VERTEX-COVER is verified by the clique verifier in cover mode
• Stacks of the CLIQUE verifier
• Labels of the CLIQUE verifier

Statements of the clique verifier to Row-by-row pair bits see only adjacency

• Statements of the clique verifier
• The clique verifier's unary reader
• Load step of the CLIQUE verifier
• Rest of a walk step of the clique verifier
• Walk step of the clique verifier
• Program of the clique verifier
• Start label of the clique verifier
• One step of a clique-verifier program to a known label
• The clique verifier's unary reader succeeds
• Reading an unterminated unary number rejects
• Run of the load phase
• Walking the pairs of one row of the clique verifier
• One row of the clique verifier's walk
• All rows of the clique verifier's walk
• The verifier machine for clique, independent set and vertex cover
• Distinctness of CLIQUE verifier pairs (moved alias)
• Karp adjacency of two literals
• Row-by-row pair bits of an occurrence list
• Pair bits of an occurrence list, row by row
• Row-by-row pair bits see only adjacency

Occurrences of a formula with a first clause to Moving a walked name from \(D\) to \(E\)

• Occurrences of a formula with a first clause
• Polarity-first tokens of a literal
• Tokens of an item on the walked stack
• Bits pushed by a walk of the CLIQUE emitter
• Walked items of a formula
• Rows pushed for a clause's literals
• Row bits of a formula for the CLIQUE emitter
• Pair bits of a leading clause
• The CLIQUE emitter's row bits are Karp's pair bits
• Stacks of the SAT-to-CLIQUE emitter
• Stack alphabets of the CLIQUE emitter
• Labels of the SAT-to-CLIQUE emitter
• The CLIQUE emitter machine
• Start label of the CLIQUE emitter
• Configuration stacks of the CLIQUE emitter
• CLIQUE emitter: recognizing a standard state
• Tokens moved by the walk
• Name bits of a variable in the CLIQUE emitter
• CLIQUE emitter: reading a variable name
• Moving a walked name from \(D\) to \(E\)

Clique emitter: comparing two names to Pair-bit transform of each mode

• Clique emitter: comparing two names
• CLIQUE emitter: putting the current occurrence on the walked stack
• Clique emitter: moving the walk side back
• Clique emitter: the instance prefix
• Reversing a list preserves the length of a flat map
• Walk over the occurrence stack in the CLIQUE emitter
• Emitter run over one literal occurrence
• Emitter run over a clause's literals
• Clique emitter: one clause
• Emitter run over a formula's clauses
• The CLIQUE emitter computes Karp's instance in cubic time
• Modes of the CLIQUE/VERTEX-COVER reduction machine
• Reduction computed in each mode
• Stacks of the CLIQUE to VERTEX-COVER reduction machine
• Stack alphabets of the clique reduction machine
• Labels of the KG-map machine
• Counter unit symbol of the clique reduction machine
• Test for the input bit true
• Test for the moved bit true
• Pair-bit transform of each mode

Label after the move phase of the KG-map machine to SAT ≤ CLIQUE is polynomial-time

• Label after the move phase of the KG-map machine
• Counter of the first output number of the KG-map machine
• The KG-map machine
• Start label of the KG-map machine
• Reading the first unary number in the KG-map machine
• Unterminated first unary number in the KG-map machine
• Reading the second unary number in the KG-map machine
• Unterminated second unary number in the KG-map machine
• Moving the pair bits onto stack \(Y\)
• Subtraction loop of the clique reduction machine
• Failed subtraction in the KG-map machine
• Output loop for the pair bits of the KG-map machine
• Number output of the clique reduction machine
• Output phase of the KG-map machine
• Correctness and running time of the KG-map machine
• The CLIQUE-to-INDEPENDENT-SET and INDEPENDENT-SET-to-VERTEX-COVER map as a host component
• CLIQUE ≤ INDEPENDENT-SET is polynomial-time
• INDEPENDENT-SET ≤ VERTEX-COVER is polynomial-time
• The CLIQUE emitter
• SAT ≤ CLIQUE is polynomial-time

CLIQUE is NP-hard to VERTEX-COVER (exact size k) is NP-complete

• CLIQUE is NP-hard
• INDEPENDENT-SET is NP-hard
• VERTEX-COVER (exact size k) is NP-hard
• The CLIQUE, INDEPENDENT-SET and VERTEX-COVER verifier as a host component
• NP membership from the CLIQUE, INDEPENDENT-SET and VERTEX-COVER verifier
• CLIQUE is in NP
• INDEPENDENT-SET is in NP
• VERTEX-COVER (exact size k) is in NP
• CLIQUE is NP-complete
• INDEPENDENT-SET is NP-complete
• VERTEX-COVER (exact size k) is NP-complete

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.