81 problems
Let be positive integers with and , and let and . Let be a family of graphs for which recognizing generating subgraphs isomorphic…
Determine the computational complexity of the following decision problem: given a planar graph with maximum degree at most and an integer , decide whether…
Let be a simple undirected graph with . For each vertex independently, choose incident edges uniformly with replacement, and let be the spanning subgraph…
Given a finite graph , decide whether every minimal separator of is bisimplicial, that is, whether for every set such that there exist distinct vertice…
For every fixed finite graph and every , there is a deterministic quasipolynomial-time algorithm that, given a graph with nonnegative vertex weights and cont…
For every fixed planar graph , Maximum Independent Set is solvable in polynomial time on the class of -induced-minor-free graphs.
Given a finite point set with , let range over spanning trees on , with each edge weighted by its Euclidean length. Define the dilation of …
Let be the publicly specified -vertex Model-RB benchmark graph. Determine its independence number…
Given a weighted graph , where , find an integral cycle basis minimizing its total weight…
Given a graph and an integer , determine whether there exists an edge set with such that every connected component of has diameter at m…
This entry tracks Gao–Zhang well-separated pair decomposition problem for unit-disk graphs. It determines the asymptotically optimal decomposition size for this geometric graph cla…
Let be a simple graph, directed or undirected, with positive real-valued edge weights, and let . When the graph is accessed through vertex and incident-edge que…
Given local random-neighbor access to an unknown unweighted graph with vertices, let denote its normalized adjacency matrix and let…
Feasible indexing conjecture. There exists an indexing satisfying this successor-set ordering and, whenever two consecutive nodes have equal successor-set order,
Polynomial-time computation conjecture. The following problem can be solved in polynomial time: given a graph , output .
Xu et al.'s conjecture. The maximum forcing number of can be computed in polynomial time.
Polynomial-time dimension conjecture. The dimension of a poset given its linear extension graph can be determined in polynomial time.
Gartland and Lokshtanov's conjecture. For every fixed and CMSO formula , -MWIS and can be solved in polynomi…
Let be a hereditary class of graphs. A class is dependent if it has the model-theoretic non-independence property, and first-order model checking is fixed parameter tr…
Worst-case output-size conjecture. For every , there exists a sourceless digraph such that, for every vertex of , every quasi-kernel returned by the algor…
Small Quasi-Kernel Conjecture. The digraph contains a quasi-kernel of order at most .
Let be the -by- hexagonal grid and let be the complete bipartite graph with both sides of the bipartition of size . For a positive integer , l…
Let be a connected plane digraph and let be an integer. The Directed Plane Strong Connectivity Augmentation problem asks whether there is a set with…
Let be a simple graph. In Max Partial -Coloring\, the input is a graph with a revenue function , an…
NP-hardness conjecture. Minimum Eternal Vertex Cover is NP-hard on series-parallel graphs.