Skip to main content
Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Saves in:saves
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options not deleted user 2233

This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.

5 votes
Accepted

Approximation of Hamiltonian cycles

Claim. For every $\rho \geq 1$, there is no polynomial $\rho$-approximation algorithm for $\texttt{MinHalfSimpCycle}$, unless P=NP. Proof. Let $G$ be an instance of the Travelling Salesman Problem (TS …
Tony Huynh's user avatar
  • 32.1k
6 votes

Efficient Hamiltonian cycle algorithms for graph classes

One class of graphs for which many NP-hard problems (including finding a Hamiltonian cycle) are easy (linear-time) are graphs of bounded tree-width. Indeed, by Courcelle's theorem any problem which c …
Martin Sleziak's user avatar
7 votes
Accepted

NP-hardness of finding maximum of minimum element in diagonal of a matrix

This seems to be polynomial. Here is a proof. It will be convenient to regard $A$ as an edge-weighted complete bipartite graph $G$. Let $m_1 < \dots < m_\ell$ be the list of edge weights of $G$, le …
Tony Huynh's user avatar
  • 32.1k
2 votes

Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them ...

The problem is indeed NP-hard, and cannot even be well-approximated in polynomial time. To see this, consider an instance $(\mathcal{F}, V)$ of the set cover problem. We construct an instance of the …
Tony Huynh's user avatar
  • 32.1k
5 votes
Accepted

The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones

Regarding the fraction of satisfiable 3-CNF formulas in $n$ variables, it is widely believed that there is a phase transition that occurs depending on how many clauses there are compared to the number …
Tony Huynh's user avatar
  • 32.1k
8 votes

Erdős multiplication problem revisited

The answer to both your questions are (essentially) yes, and are given in a recent paper of Brent, Pomerance, Purdum, and Webster. Regarding (b), they show that $A(n)$ can be computed in subquadratic …
Tony Huynh's user avatar
  • 32.1k
7 votes

Metric TSP with integer edge cost

No polynomial-time algorithm exists, unless P=NP. Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and Kar …
Tony Huynh's user avatar
  • 32.1k
2 votes
Accepted

One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets...

Let $G=(U,V,E)$ be a bipartite graph where $U=[n], V=\binom{[n]}{3}$, and there is an edge between $u \in U$ and $v \in V$ if and only if $u \in v$. Then $\deg(u)=\binom{n-1}{2}$ for all $u \in V$ an …
Tony Huynh's user avatar
  • 32.1k
1 vote

Examples of Super-polynomial time algorithmic/induction proofs?

Another example is the matroid intersection theorem, which is a rich source of min/max theorems in combinatorial optimzation. For example, it includes your example (Kőnig's theorem) as a special case …
Tony Huynh's user avatar
  • 32.1k
19 votes
Accepted

Lagrange four-squares theorem --- deterministic complexity

As far as I know, this is still an open problem. This is discussed in Section $5$ of the paper Finding the four squares in Lagrange's theorem by Pollack and Treviño. They mention that there is a det …
Tony Huynh's user avatar
  • 32.1k
2 votes
Accepted

3-Approximation Algorithm for 3-Hitting Set

Let $\mathcal{H}$ be a hypergraph where each hyperedge has size $3$. A vertex cover is a set of vertices $X$ such that every hyperedge is incident to a vertex in $X$. Rephrased, our goal is to find …
Tony Huynh's user avatar
  • 32.1k
9 votes
Accepted

A minimum set hitting every base of a matroid

The problem is hard in general. Note that a minimal set that intersects every base of a matroid $M$ is a dependent set in the dual matroid $M^{*}$. Such sets are called cocircuits. So, you are look …
Tony Huynh's user avatar
  • 32.1k
3 votes
Accepted

Reconstructing a graph from shortest paths information

This problem is solvable in polynomial-time. Given a $V \times V$ distance matrix $A$, let $G$ be the graph with vertex set $V$, where $uw \in E(G)$ if and only if $A_{uw}=1$. Note that $G$ is the …
Tony Huynh's user avatar
  • 32.1k
8 votes

Variation on the Subset Sum Problem

I believe your problem is indeed NP-hard, via the following reduction from subset sum. Let $(a_i)_{i=1}^n$ be an instance of SUBSET SUM. We will make an instance of SMALLEST SUBSET SUM as follows. L …
Tony Huynh's user avatar
  • 32.1k
1 vote

Maximum subgraph edge distance greater than given number

Your problem is not polynomial (unless P=NP), because your problem is polynomially equivalent to maximum independent set, which is NP-hard. In one direction, given an edge-weighted graph $G$ and a …
Tony Huynh's user avatar
  • 32.1k

15 30 50 per page