A Note on Succinct Representations of Graphs

Galperin and Wigderson (Inform. and Control 56 (1983), 183–198) showed that certain trivial graph properties become NP-complete when the graph is represented in a particular exponentially succinct way. We show that under the same representation, graph properties that are ordinarily NP-complete become complete for non-deterministic exponential time.

• Publication year

  1986

• Venue

  Information and Control

• Publication date

  1986-12-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0019-9958(86)80009-2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Succinct Representations of Graphs

  1984cited by this paper
• The Complexity of Problems Concerning Graphs with Regularities (Extended Abstract)

  1984cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• A complexity theory based on Boolean algebra

  1981cited by this paper
• The Complexity of Computing the Permanent

  1979cited by this paper
• The Polynomial-Time Hierarchy

  1976cited by this paper
• The circuit value problem is log space complete for P

  1975cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper

• The Complexity of Homomorphism Reconstruction Revisited

  2026cites this paper
• Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking

  2025influential citation
• Yet Another Simple Proof of the PCRP Theorem

  2025cites this paper
• 2-DQBF Solving and Certification via Property-Directed Reachability Analysis

  2024cites this paper
• On the Complexity of Pure-State Consistency of Local Density Matrices

  2024cites this paper
• Quantum Merlin-Arthur with an internally separable proof

  2024cites this paper
• Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

  2023cites this paper
• Hardness of monadic second-order formulae over succinct graphs

  2023cites this paper
• Separability and Its Approximations in Ontology-based Data Management

  2023cites this paper
• Querying Circumscribed Description Logic Knowledge Bases

  2023cites this paper
• PARIS: Planning Algorithms for Reconfiguring Independent Sets

  2023cites this paper
• A Theory of Cartesian Arrays (with Applications in Quantum Circuit Verification)

  2023cites this paper
• On the Complexity of k-DQBF

  2023influential citation
• Reducing NEXP-complete problems to DQBF

  2022influential citation
• Higher-Order Quantified Boolean Satisfiability

  2022cites this paper
• A Polynomial-time Solution for the Maximum Subsets Problem

  2022cites this paper
• Answers set programs for non-transferable utility games: Expressiveness, complexity and applications

  2022cites this paper
• Counting Queries over ELHI⊥ Ontologies

  2022cites this paper
• On two-variable guarded fragment logic with expressive local Presburger constraints

  2022cites this paper
• Introduction

  2021cites this paper
• Safety Verification of Parameterized Systems under Release-Acquire

  2021cites this paper
• Cost Optimal Planning as Satisfiability

  2021cites this paper
• Ranking Sets of Objects: The Complexity of Avoiding Impossibility Results

  2021influential citation
• Towards a more efficient approach for the satisfiability of two-variable logic

  2021cites this paper
• Checking LTL[F,G,X] on compressed traces in polynomial time

  2021cites this paper
• Pruning external minimality checking for answer set programs using semantic dependencies

  2021cites this paper
• QDEF and Its Approximations in OBDM

  2021influential citation
• The complexity gap in the static analysis of cache accesses grows if procedure calls are added

  2021influential citation
• The Maximum (k,m)-Subsets Problem is in the Class NEXP

  2021influential citation
• Context-bounded verification of thread pools

  2021cites this paper
• Conversational Recommendation: Theoretical Model and Complexity Analysis

  2021cites this paper
• Query Definability and Its Approximations in Ontology-based Data Management

  2021cites this paper
• A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom

  2020cites this paper
• On the Complexity of Quadratization for Polynomial Differential Equations

  2020cites this paper
• Computational Methods in Systems Biology: 18th International Conference, CMSB 2020, Konstanz, Germany, September 23–25, 2020, Proceedings

  2020influential citation
• A tetrachotomy of ontology-mediated queries with a covering axiom

  2020cites this paper
• On the Complexity of Binomialization for Polynomial Differential Equations

  2020cites this paper
• The Complexity of Bounded Context Switching with Dynamic Thread Creation

  2020cites this paper
• Computing Plan-Length Bounds Using Lengths of Longest Paths

  2020cites this paper
• Limit Datalog

  2020cites this paper
• Linear-Size Constant-Query IOPs for Delegating Computation

  2019cites this paper
• LOGSPACE vs P

  2019influential citation
• LOGSPACE vs P vs NP

  2019influential citation
• NEEXP in MIP*

  2019cites this paper
• Hardness of Approximation Between P and NP

  2019cites this paper
• Symbolic model checking of public announcement protocols

  2019cites this paper
• Some Estimated Likelihoods for Computational Complexity

  2019cites this paper
• Optimal Strategies of Blotto Games: Beyond Convexity

  2019cites this paper
• Sequential Relational Decomposition

  2018influential citation
• Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations

  2018cites this paper
• On the Complexity of Iterative Tropical Computation with Applications to Markov Decision Processes

  2018cites this paper
• Data race detection on compressed traces

  2018cites this paper
• On the Complexity of Value Iteration

  2018cites this paper
• Grammar-Based Graph Compression

  2017cites this paper
• Complexity of mixed equilibria in Boolean games

  2017cites this paper
• CNF and DNF succinct graph encodings

  2017cites this paper
• Revisiting reachability in timed automata

  2017cites this paper
• O ct 2 01 7 Mean-payoff Games with Partial Observation ∗

  2017influential citation
• N ov 2 01 6 Mean-payoff Games with Partial Observation ∗

  2016cites this paper
• The Minimum Oracle Circuit Size Problem

  2016cites this paper
• The Complexity of Bayesian Networks Specified by Propositional and Relational Languages

  2016cites this paper
• A Survey of the Complexity of Succinctly Encoded Problems May 5 , 2016

  2016influential citation
• On Limited Nondeterminism and ACC Circuit Lower Bounds

  2016cites this paper
• The Well-Founded Semantics of Cyclic Probabilistic Logic Programs : Meaning and Complexity

  2016cites this paper
• Satisfiability-Based Methods for Reactive Synthesis from Safety Specifications

  2016cites this paper
• Probabilistic Graphical Models Specified by Probabilistic Logic Programs: Semantics and Complexity

  2016cites this paper
• 3 Subgraph isomorphism in planar graphs parameterized by the difference

  2015influential citation
• The Complexity of Recognizing Unique Sink Orientations

  2015cites this paper
• Bayesian Networks Specified Using Propositional and Relational Constructs: Combined, Data, and Domain Complexity

  2015cites this paper
• On the Structure of Solution-Graphs for Boolean Formulas

  2015cites this paper
• On Matrix Powering in Low Dimensions

  2015cites this paper
• On the (Non) NP-Hardness of Computing Circuit Complexity

  2015cites this paper
• The Complexity of Plate Probabilistic Models

  2015cites this paper
• Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation

  2015cites this paper
• Equality Testing of Compressed Strings

  2015cites this paper
• A decision procedure for satisfiability in separation logic with inductive predicates

  2014influential citation
• High-Multiplicity Scheduling and Packing Problems

  2014cites this paper
• Studies in Models of Quantum Proof Systems

  2014cites this paper
• High-multiplicity Scheduling and Packing Problems : Theory and Applications

  2014cites this paper
• AbsSynthe: abstract synthesis from succinct safety specifications

  2014cites this paper
• Succinct Encodings of Graph Isomorphism

  2014cites this paper
• Computational Complexity of Approximate Nash Equilibrium in Large Games

  2014cites this paper
• Subclasses of presburger arithmetic and the weak EXP hierarchy

  2014cites this paper
• On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic

  2014cites this paper
• Energy and mean-payoff timed games

  2014cites this paper
• Mean-payoff games with partial observation

  2013influential citation
• Two Compact Codes for Rectangular Drawings with Degree Four Vertices

  2013cites this paper
• Succinct Permanent Is NEXP-Hard with Many Hard Instances

  2013influential citation
• Mean-Payoff Games with Partial-Observation - (Extended Abstract)

  2013influential citation
• The Complexity of Optimal Auction Design

  2013cites this paper
• A Decision Procedure for Satisfiability in Separation Logic with Inductive Predicates July 12 , 2013

  2013influential citation
• Analysis of Boolean Programs

  2013cites this paper
• Invariant Generation through Strategy Iteration in Succinctly Represented Control Flow Graphs

  2012cites this paper
• Efficiency-Revenue Trade-Offs in Auctions

  2012cites this paper
• A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers

  2012cites this paper
• On the complexity of the multivariate resultant

  2012cites this paper
• Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap

  2012cites this paper
• A uniform approach to the complexity and analysis of succinct systems

  2012cites this paper
• On the complexity of model checking counter automata

  2012cites this paper
• Count Constraints and the Inverse OLAP Problem: Definition, Complexity and a Step toward Aggregate Data Exchange

  2012cites this paper