Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-complete]

Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

0
votes
0answers
11 views

Partition Problem Variant

I'd like to ask to solve a variant of set partition problem. Suppose we have some items $V = \{1, \cdots, n\}$ and a subadditive cost function $f: 2^V \to R^{+}$. For any partition $P$ of $V$, define ...
0
votes
0answers
8 views

Complexity of maximizing sum of fractional functions under cardinality constraint

Considering the following optimization problem: $max_{x} \ \sum_{i=1}^n \frac{W_i}{D_i - z_i},\quad s.t.\ \sum_{i=1}^n z_i \leq k,z_i\in[0,k]$, where $W_i$ and $D_i$ are postive constants and $z_i$ ...
-1
votes
0answers
11 views

delete some rows of a matrix

"delete k rows from a matrix and then sum each column, say the sum vector is c whose length is number of columns, we want to make sure that at least 5 elements in c is bigger than zero. The question ...
1
vote
1answer
59 views

Maximizing the total number of feasible constraints of a linear program

I have an optimization problem with $N$ linear inequality constraints and $K$ real valued parameters (e.g. $0.2\alpha_1+0.5\alpha_2\geq 0$, $K=2$) and no objective function. Here $N$ is much larger ...
0
votes
1answer
31 views

Positioning items to maximize separation subject to constraints

Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
0answers
25 views

Is the Maximum Clique Problem for Directed Acyclic Graphs NP complete as well?

Imagine I have a graph $(V,E)$ of vertices $V$ and undirected edges $E$. Then a clique is a set of vertices $(v_1,...,v_n)$ such that that there is an edge between any pair $(v_i,v_j)$ of vertices ...
5
votes
3answers
56 views

Why can't set cover be reduced to min-cost max-flow?

Okay, so I know obviously I'm making some kind of easy mistake here, since set cover is NP-complete and min-cost max-flow is in P, but I can't figure out what the mistake is. So, given a universe $U$ ...
0
votes
0answers
11 views

Karp hardness of a module in a graph

DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property: For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
1
vote
0answers
20 views

NP-hardness proof of a model with a convex objective

Let $T=(V,E)$ denote a tree. Each node $j \in V$ in the tree has a known attribute $c_j$. From T, construct a bi-directional graph $G' = (V, E')$ where $E' = \{(j,k), (k,j)| (j,k) \in E\}$. Simply, ...
0
votes
0answers
62 views

A Language in CNF with distinct variables per clause and each variable appears in at most three literals is in P

Let A be a language defined thus A = {φ | φ is in CNF, with three literals, comprising distinct variables, per clause; and each variable appears in at most three literals; and φ is satisfiable} . ...
0
votes
1answer
31 views

NP Completeness of a Graph Problem, Proof Required

I have a graph problem that I would like to prove NP-completeness. It is outlined below: A graph problem compromising of two graphs, say $G_1(V_1,E_1)$ and $G_2(V_2,E_2)$ such that $V_i$ and $E_i$ ...
0
votes
1answer
25 views

Why is showing that ILP in NP not trivial

I have a question regarding the topic of showing that ILP is in NP What is the problem with Guess and Check? Guess a solution and then check if it is optimal. Or further: Calculate a solution via ...
0
votes
0answers
47 views

Maximizing absolute values in LP - practical applications

It is NP-hard to maximize absolute values with respect to a polyhedral set of constraints. The reason is that the objective is then a convex function and we maximize it. Since the constraints are ...
1
vote
1answer
33 views

Is the n-Queens problem only np-complete for the task of finding all setups or also for finding any solution?

I have read on Wikipedia that the n-Queens problem is NP-complete when it comes to finding all possible solution implies it that finding one possible solution is also NP-complete?
0
votes
1answer
23 views

Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$ [closed]

How to solve Big-O for $\Sigma_{i = 1}^{N} i \times \binom{N}{i}$? Can I simply say it is in $O(N!)$?
2
votes
1answer
30 views

GI-Completeness of graph isomorphism with connected graphs

The Wikipedia page for Graph Isomorphism lists connected graphs as GI-complete. The citation has a paywall, and I have not been able to find any NP-complete algorithms for isomorphism of connected ...
1
vote
0answers
42 views

How to prove a submodular maximization problem is NP-hard

We know that a submodular maximization problem of the form $$ \mathcal{P}: \,\, \mathop {\max }\limits_S f\left( S \right) $$ where $f(S)$ is a submodular set function, is NP-hard (Claim 1). This ...
3
votes
1answer
110 views

Properly stating a decision problem for a Hamiltonian cycle problem

I'm running an algorithms seminar and I'm trying to express the Hamiltonian cycle problem in a new way that is exciting to students. I know that many of them play a game called Hearthstone and I'm ...
0
votes
0answers
20 views

Proof for correctness of reduction from 3-SAT to quadradic equations NPC problem

A reduction from 3-SAT to quadratic equations is described as follows: Given an input expression to 3-SAT, convert it to a quadratic example as follows: $x_i \rightarrow ax_i$ ~$x_i \rightarrow a(1-...
1
vote
1answer
40 views

Does this solve boolean satisfiability problem in polynomial time?

CNF can be easily converted into a formula that uses only AND and NOT operations, using the fact that ...
3
votes
0answers
31 views

Looking for name of combinatorial problem- Permute rows and columns to minimize distance to target matrix

I am trying to find a solution (or algorithm) for the following combinatorial problem: Given an input matrix and a target matrix, find a permutation of the rows and permutation of the columns that ...
0
votes
0answers
32 views

how to convert SAT to 3SAt

My teacher showed these steps when converting SAT to 3SAT (he was working with an example). He said to construct a formula F1 ...
0
votes
0answers
21 views

NP-hardness of finding the zero norm of a sparest null vector

The abstract of the paper The Null Space Problem I. Complexity states that finding a sparsest null vector of a matrix with more columns than rows is NP-hard (actually NP-complete). I wonder whether ...
0
votes
1answer
36 views

If a NP-complete problem is not in P, then all NP-complete problems are not in P?

It is clear to me that if a NP-Hard problem is solvable in P, then all NP-Hard problem (which include NP-Complete problems) are solvable in P. But, is it also the case that if a NP-Complete problem ...
0
votes
0answers
19 views

USAT, Arora Barak's book

Here on the page 354 Arora and Barak write below the shaded area "but in fact $f(\phi)$ $\notin SAT$" and not "but in fact $f(\phi) \in SAT$" While in the last line of the shaded area they write $...
0
votes
0answers
25 views

minimize system of infinity norm of polynomials

I have a problem that looks like this: set of expressions of the form: $p_i = ax_{i}+bx_{i}^{\frac{2}{3}} $ for $ 1 \leq i \leq n$ and I'm trying to find $ min_{\Sigma x_i=G}\{max_{1\leq i \leq n}|...
0
votes
1answer
37 views

Showing NP-completeness of a variant of the assignment problem

Suppose we have $k$ jobs, $J=\left\{ j_{1},\ldots j_{k}\right\}$ and $n$ agents, $A=\left\{ a_{1},\ldots a_{n}\right\} $. Each assignment has associated with it a subset of agents which can perform ...
1
vote
0answers
42 views

Is $k$-rainbow coloring of a hypergraph NP-complete or not?

A hypergraph is $k$-rainbow colorable if there exists a vertex coloring using $k$ colors such that each hyperedge has all the $k$ colors. The problem is also called "polychromatic coloring" Is $k$-...
6
votes
0answers
217 views

Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete? [closed]

Question I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete. Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$. Where $\...
0
votes
1answer
102 views

Alternating hamiltonian cycles is in NP-complete

• Alternating-Hamiltonian-Cycle: Given a graph G = (V, E), and a subset A ⊆ V of its vertices, does there exist a Hamiltonian Cycle of G, such that the cycle alternates between vertices in A and ...
3
votes
1answer
30 views

Team Ranking Model vs Graph Theory Model

Suppose we have $4$ sports teams, $\{T_1, T_2, T_3, T_4\}$, and we have to following records: $T_1$ beat $T_2$ by a score of 4 $T_1$ beat $T_4$ by a score of 2 $T_2$ beat $T_3$ by a ...
2
votes
1answer
71 views

Why Hamiltonian cycle decision problem in NP-complete?

I was reading the algorithm book of Neapollian and Naeempoor and it says Hamiltonian cycle decision problem is np complete and CNF can be reduced to it .I understand that why it is NP but i want to ...
0
votes
0answers
35 views

Polynomial time reduction mapping for coNP

We know that the following statement is true for NP and P classes. A≤pB and B∈P, then A∈P But is this statement also true for co-NP languages? is the trick of ...
0
votes
0answers
31 views

Knapsack as a dynamic programming problem

Ok so we are given the following linear programming problem: $\max x_1 + 2x_2+2x_3+3x_4$ Subject to: $2x_1 + 3x_2+x_3+2x_4 \le 4$ $1x_1 + 2x_2+ 3x_3+x_4 \le 4$ $x_1,x_2,x_3,x_4\in {0,1} $ My ...
0
votes
0answers
31 views

Where i can find example of ant colony method for knapsack problem?

I could not find example of solving the problem of a backpack by the method of an ant colony. Has found only the description of a method. If you know where to find please help.
2
votes
1answer
87 views

Famous convex maximization problems

Which are the most famous problems having an objective of maximizing a nonlinear convex function (or minimizing a concave function)? As far as I know such an objective with respect to linear ...
2
votes
1answer
39 views

Create a circuit based on a graph

Let's say I have a graph, and from this graph I want to create a circuit $K$ whose inputs can be set so that $K$ outputs true iff the graph has an independent set of size $\ge2.$ I've seen some ...
1
vote
1answer
61 views

Determine the independent sets of size 2 of G

So lets say I have a graph.. and I want to find the independent sets of size 2. I'm a little confused on how to go about this. I know that a Independent set if there are no edges between vertices in ...
0
votes
0answers
10 views

Maximize vertex cover weights with bounded edge weights in a connected subgraph

In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is bounded and the sum of internal vertex weights is maximal. Is this problem ...
0
votes
1answer
46 views

Reducing 3 SAT to max 2 SAT

In the reduction done here, you take one clause $d = a \cup b\cup c$, and make 10 clauses $a, b, c, d, a \cup \neg d, b \cup \neg d, c \cup \neg d, \neg a \cup \neg b, \neg b \cup \neg c, \neg a \cup ...
0
votes
0answers
80 views

NP-completeness certificate of a Hamiltonian path

A Hamiltonian path is a path in a directed , edge positive valued finite graph which visits every vertex exactly once and returns to the original vertex. This should be a NP-complete problem, but I do ...
1
vote
0answers
135 views

Travelling Salesman Problem Nearest neighbor heuristic

One criticism of the nearest-neighbor TSP heuristic is that the last edge added (from the last city back to the starting city) can be very long. How much effect can that last edge have on the ratio NN/...
-2
votes
1answer
47 views

Can a completely non-brute algo exist for solving Sudoku given it's NP-complete? [closed]

As far as I understand it, Sudoku is an NP-complete problem and the best known algorithm for solving it would therefore scale exponentially with grid-size, N. All the algorithms I have so far seen ...
3
votes
1answer
80 views

Rules for Reductions in NP-Completeness Proofs (many-one vs one-many)

My understanding is that when reducing one problem known to be NPC (e.g., HAM-Cycle) to another problem known to be NP (e.g., Ham-Path) we have shown that the second problem (the target of the ...
1
vote
0answers
55 views

Rainer Schuler's algorithm of CNF SAT problem

I'm reading through this publication trying to understand the algorithm and what exactly did Schuler achieve compared to Cook's theorem. Can someone please explain me how this algorithm works in ...
0
votes
0answers
9 views

Is h(f(g(x))) NP-hard if g and h is NP-hard and f is Polynomial time solvable

Given two different problems $g$ and $h$ both of which are proven to be NP-Hard. We assume size of solution is not deducible from the size problem for both $g$ and $h$ (So $g$ and $h$ are not decision ...
1
vote
0answers
55 views

Is Threshold Logic Minimization (synthesis) NP-Hard, NP-Complete or NP or..

Consider a problem of generating a minimal threshold logic circuit for an arbitrary boolean function. This is akin to usual circuit optimization, but gates are allowed to be any threshold (linearly ...
1
vote
2answers
41 views

Euclidean Case of the TSP for a given problem.

My textbooks states that the "Euclidean Plane" case of the Traveling Salesperson Problem is a special case of the TSP, when all the points lay in the euclidean plane and the distance between these ...
1
vote
0answers
50 views

Can't understand this statement

I was reading some bachelor thesis and it mentioned reducing the hitting set problem to the set cover problem. However I am unable to understand the last line in the referenced paragraph, I would ...
1
vote
2answers
337 views

P/NP reduction (hamiltonian cycle to TSP)

I have a P/NP question. I have read that were any NP problem be found to have a polynomial time algorithm, then we can reduce any other NP problem to a form where we can use our first algorithm to ...