In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NPhard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhardmore »
On the Hardness and Inapproximability of Recognizing Wheeler Graphs
In recent years several compressed indexes based on variants of the BurrowsWheeler transformation have been introduced. Some of these are used to index structures far more complex than a single string, as was originally done with the FMindex [Ferragina and Manzini, J. ACM 2005]. As such, there has been an increasing effort to better understand under which conditions such an indexing scheme is possible. This has led to the introduction of Wheeler graphs [Gagie et al., Theor. Comput. Sci., 2017]. Gagie et al. showed that de Bruijn graphs, generalized compressed suffix arrays, and several other BWT related structures can be represented as Wheeler graphs and that Wheeler graphs can be indexed in a way which is spaceefficient. Hence, being able to recognize whether a given graph is a Wheeler graph, or being able to approximate a given graph by a Wheeler graph, could have numerous applications in indexing. Here we resolve the open question of whether there exists an efficient algorithm for recognizing if a given graph is a Wheeler graph. We present  The problem of recognizing whether a given graph G=(V,E) is a Wheeler graph is NPcomplete for any edge label alphabet of size sigma >= 2, even more »
 Publication Date:
 NSFPAR ID:
 10164524
 Journal Name:
 27th Annual European Symposium on Algorithms (ESA) 2019
 Sponsoring Org:
 National Science Foundation
More Like this


Given a directed acyclic graph (DAG) G=(V,E), we say that G is (e,d)depthrobust (resp. (e,d)edgedepthrobust) if for any set S⊆V (resp. S⊆E) of at most S≤e nodes (resp. edges) the graph G−S contains a directed path of length d. While edgedepthrobust graphs are potentially easier to construct, many applications in cryptography require node depthrobust graphs with small indegree. We create a graph reduction that transforms an (e,d)edgedepthrobust graph with m edges into a (e/2,d)depthrobust graph with O(m) nodes and constant indegree. One immediate consequence of this result is the first construction of a provably (nloglognlogn,nlogn(logn)loglogn)depthrobust graph with constant indegree. Ourmore »

The cumulative pebbling complexity of a directed acyclic graph G is defined as cc(G) = min_P ∑_i P_i, where the minimum is taken over all legal (parallel) black pebblings of G and P_i denotes the number of pebbles on the graph during round i. Intuitively, cc(G) captures the amortized SpaceTime complexity of pebbling m copies of G in parallel. The cumulative pebbling complexity of a graph G is of particular interest in the field of cryptography as cc(G) is tightly related to the amortized AreaTime complexity of the DataIndependent MemoryHard Function (iMHF) f_{G,H} [Joël Alwen and Vladimir Serbinenko, 2015] definedmore »

For graphs G and H, we say that G is Hfree if it does not contain H as an induced subgraph. Already in the early 1980s Alekseev observed that if H is connected, then the Max Weight Independent Set problem (MWIS) remains NPhard in Hfree graphs, unless H is a path or a subdivided claw, i.e., a graph obtained from the threeleaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is thatmore »

For a graph F, a graph G is Ffree if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an Hcoloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem HColoring, which asks for the existence of an Hcoloring of an input graph G. In particular, we consider HColoring of Ffree graphs, where F is a fixed graph and H is an odd cycle of length atmore »