1
vote
1answer
77 views

Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language: $L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$. ($G$ ...
2
votes
3answers
138 views

Reference Request for: Finding Large Bipartite Subgraphs via Destruction of Odd Cycles in Graphs

From the observation, that a bipartite graph doesn't contain odd cycles, it would seem natural to attempt to destroy all odd cycles in the most efficient way, by either removing edges or vertices of ...
1
vote
3answers
213 views

Strategic vertex labeling

We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0(all vertices with ...
1
vote
1answer
224 views

Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph

I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem. One of the respondents cited Professor David Speyer's Math ...
6
votes
0answers
451 views

Is Logical Min-Cut Problem, NP-Complete?

Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by ...
2
votes
1answer
449 views

#P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...
2
votes
2answers
177 views

how to find vertex of parallelotope closest to given point P in R^n ? (Or minimize quadratic form over {+-1}) Is it NP ?

Consider a parallelotope in R^n and some point "P" in R^n. What algorithms (except of brute force) can be suggested to find the closest vertex of paralleloptope to "P" ? Is it NP ? Parallelotope ...
4
votes
1answer
921 views

Closest vector problem (=nearest lattice point) is trivial for “reduced lattice” ?

Consider some lattice in R^n. Take some point "P" in R^n (which does not belong to this lattice in general). The problem is to find "nearest" lattice point. The problem is known NP-hard in general it ...
2
votes
1answer
308 views

poly-time algorithm to choose elements of sets

Let $A_1,A_2,\ldots,A_k$ be finite sets. Furthermore, for each $i\in\{1,2,\ldots,k\}$, let $B_i$ be a set whose elements are subsets of $A_i$. Is there any polynomial-time algorithm that decides ...
5
votes
1answer
487 views

Minimal Backtracking Proof Tree

When trying to prove that a particular instance of a problem like graph coloring or SAT is unsatisfiable, generally one explores the search tree using an algorithm like DPLL and the proof of ...
18
votes
3answers
2k views

Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...