Results 1 to 10 of about 272,983 (311)
NP-Completeness Results for Minimum Planar Spanners [PDF]
Discrete Mathematics & Theoretical Computer Science, 1998 For any fixed parameter t greater or equal to 1, a \emph t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times their distance in G.
Ulrik Brandes, Dagmar Handke
doaj +3 more sources
On subset sum problem in branch groups [PDF]
Groups, Complexity, Cryptology, 2020 We consider a group-theoretic analogue of the classic subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group.
Andrey Nikolaev, Alexander Ushakov
doaj +1 more source
Contractibility and NP‐completeness [PDF]
Journal of Graph Theory, 1987 AbstractFor a fixed graph H, let H‐CON denote the problem of determining whether a given graph is contractible to H. The complexity of H‐CON is studied for H belonging to certain classes of graphs, together covering all connected graphs of order at most 4.
A.E. Brouwer (Andries), H.J. Veldman
openaire +2 more sources
Shellability is NP-complete [PDF]
Journal of the ACM, 2019 We prove that for every d ≥ 2, deciding if a pure, d -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k
Xavier Goaoc +4 more
openaire +5 more sources
LaserTank is NP-Complete [PDF]
, 2020 We show that the classical game LaserTank is $\mathrm{NP}$-complete, even when the tank movement is restricted to a single column and the only blocks appearing on the board are mirrors and solid blocks. We show this by reducing $3$-SAT instances to LaserTank puzzles.
Per Alexandersson, Petter Restadh
openaire +2 more sources
Hard to Detect Factors of Univariate Integer Polynomials
Mathematics, 2023 We investigate the computational complexity of deciding whether a given univariate integer polynomial p(x) has a factor q(x) satisfying specific additional constraints.
Alberto Dennunzio +2 more
doaj +1 more source
Probabilistic Nearest Neighbors Classification
Entropy, 2023 Analysis of the currently established Bayesian nearest neighbors classification model points to a connection between the computation of its normalizing constant and issues of NP-completeness. An alternative predictive model constructed by aggregating the
Bruno Fava +2 more
doaj +1 more source
NP-completeness of slope-constrained drawing of complete graphs
Journal of Computational Geometry, 2020 We prove the NP-completeness of the following problem. Given a set $S$ of $n$ slopes and an integer $k\geq 1$, is it possible to draw a complete graph on $k$ vertices in the plane using only slopes from $S$? Equivalently, does there exist a set $K$ of
Cédric Pilatte
doaj +1 more source
CoRR, 2020 In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an $m \times n$ grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing + are square, rectangles containing - are strictly longer ...
Adler, Aviv +5 more
openaire +4 more sources
Theoretical Computer Science, 2022 Rikudo is a number-placement puzzle, where the player is asked to complete a Hamiltonian path on a hexagonal grid, given some clues (numbers already placed and edges of the path). We prove that the game is complete for NP, even if the puzzle has no hole.
Nguyen, Viet-Ha, Perrot, Kévin
openaire +4 more sources