# Questions tagged [np-complete]

The tag has no usage guidance.

137 questions
Filter by
Sorted by
Tagged with
41 views

### How to prove this josephus problem variation is a np-complete problem? [closed]

have a problem that is a Josephus problem variation. It is described below: There are m cards with number from 1 to m，and each of them has a unique number. The cards are dispatched to n person who sit ...
58 views

### 3-partition problem is NP-complete. How about “N-partition problem”?

It is well known that 3-partition problem is strongly NP-complete. (https://en.wikipedia.org/wiki/3-partition_problem) Then, My question is, how about "N-partition problem"? Is it NP-...
38 views

26 views

### Polynomial-time reducibility of Primality and 3-SAT

Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated. Thank you.
37 views

### Efficient algorithm for finding segregators in a directed acyclic graph

Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ...
332 views

### Is the maximum independent set in cubic planar graphs NP-complete?

In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation ...
108 views

311 views

### Complexity of finding the largest induced subgraph with all even degrees

What is the complexity of the following problem? Instance: Simple, undirected graph $G$, and a positive integer $k$. Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...
730 views

### Relationship between two graph optimization problems

Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph: P1. Find a largest induced subgraph of the ...
114 views

### Example of decidable NP-hard problem that is not NP-complete [closed]

I am looking for an example of a decision problem which fulfills the following conditions: 1. It is decidable 2. It is NP-hard 3. It is not NP-complete All my search attempts yielded examples that ...
845 views

### What languages can be reduced to a NP-complete problem in polynomial time

NP-complete: Language is NP-complete, when it is in NP and every problem in NP is reducible to it in polynomial time. But what languages are reducible to a NP-complete problem (for example SAT) in ...
71 views

### Short $\exists$SO sentences over strings that define an NP-complete problem

[Q1] I'm wondering if there are some "official" SHORT existential second order sentences with ONE binary relation, over strings (over a small alphabet) that define an NP-complete set. (Something ...
277 views

### “Relatives” of the shortest path problem

Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such ...
229 views

67 views

117 views

### NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: https://epubs.siam.org/doi/abs/10.1137/0205049 For a problem I'm ...
474 views

56 views

### NP-Complete graph problems where a special vertex is given as input?

I am currently working on a graph theory problem where the instance includes a graph and a special vertex in the graph. I am trying to prove the NP-completeness of the problem as well as explore ...