All Questions

11,524 questions
Filter by
Sorted by
Tagged with
27 views

Parameterized complexity of problems related to trees

I am trying to shown that Parameterized complexity of proper spanning tree. But i don't have any idea. Are there some problems related to spanning trees that are fixed parameterized intractability?
20 views

Steiner Tree Problem for circle graph

Can Steiner Tree Problem be solved in polynomial time on circle graph?
129 views

Lower bound for the OR problem

Let us have booleans $x_1, \cdots, x_n$. Any algorithm that determines $\bigvee_1^n x_i$ with probability at least $2/3$ requires $\Omega(n)$ time. It is not too difficult to prove this, but the proof ...
13 views

Understanding the behavior of Conflict Serializability and View Serializability with respect to blind writes

I have seen that most standard college textbooks of Database Management Systems use this method to classify whether a schedule is view serializable or not. I know the definitions of Conflict ...
117 views

Does a graph resulting from the union of triangles has a particular name?

I have different simple triangle graphs. As an instance, $G_1=(V_1,E_1)=(\{1,2,3\},\{\{1,2\},\{2,3\},\{3,1\}\})$ and $G_2=(V_2,E_2)=(\{1,4,5\},\{\{1,4\},\{4,5\},\{5,1\}\})$. The union of both graphs ...
57 views

Using the probabilistic method to fill the gaps in a proof of set disjointness

In the 2-party $k$-sparse set disjointness problem, we have a set $U$ of size $n$ and there are two parties: Alice, who gets a set $X \subseteq U$ and Bob who gets a string $Y \subseteq U$, and it ...
17k views

What is the best text of computation theory/theory of computation?

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and ...
23 views

Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?

The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph. It seems like these problems would fall under the framework of network design problems (...
53 views

The parameterized complexity of proper edge-colored spanning tree

I want to FPT reduce from Multicolored Clique to proper edge-colored spanning tree, parameterized by treewidth. The input of Multicolored Clique consists of a graph $G$, an integer $k$, and a ...
45 views

What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?

Suppose we have a graph $G$ with treewidth $t$. Let $p \in (0,1)$ be a constant. Then let's independently remove each edge from $G$ with probability $p$. What is the expected treewidth of the ...
1k views

What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

I would like to know the current state of the phase transition for random k-sat, given n variables and m clauses, what is the best known c=m/n for upper and lower bounds.
2k views

43 views

k-Median Problem With Restricted Centers

The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the ...
94 views

Generalization bound for parameters rather than loss functions

I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and ...
41 views

Permutation Graphs is Chordal?

Whether the permutation graphs are a subclass of the chordal graphs? If not, what is the counter-example?
113 views

Complexity of NFA to DFA minimization with binary threshold

What is the complexity of the following problem? Given an NFA $A$ and a number $k\in \mathbb{N}$ in binary encoding, does there exist a DFA $B$ with at most $k$ states such that $L(A)=L(B)$? ...
137 views

Any problems for which we know the complexity, but no algorithms with the same time?

I suddenly found myself wondering if there are any problems for which the complexity (time or space or anything else) is proven, say to be O(n^2), but for which the best known algorithms are worse ...
36 views

Asymptotic Analysis of code that are unusual [closed]

We all know that the RUN Time of most of our program are Big O of linear time, quadratic time, cubic time or log time. But Can this be in unusual or uncommon poly time like $x^6-y$ or cosine function ...
95 views

Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover

Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
97 views

Are there an algorithm that find Minimum spanning tree in $O(n^2\log\log^*n)$?

Given completed metric weighted graph $G=(V,E)$ that have $n$ vertices. Are there an algorithm that find MST of $G$ in $O(n^2)$? I read abstract of this paper that mentioned an algorithm with running ...
66 views

Example of any non-NP decision problem without invoking time-hierarchy theorem

References appreciated for any problem decided by a Turing machine with a finite transition table that does not belong to the class NP. The non-membership is proven without the use of diagonalization ...
92 views

Can finite difference methods approximate the space/time complexity of given programs?

While benchmarking a language prototype, I realized that I had a superlinear implementation of a test program, but wasn't sure if it was quadratic or cubic. I stayed up too late and wrote half a page ...
238 views

Partition a graph into two clusters

Suppose given a complete weighted graph $G=(V,E)$, with positive weight. Are there an algorithm that partition $G$ into two clusters $C_1,C_2$ such that sum of heaviest edges in $C_1,C_2$ minimized? ...
95 views

exact path cover for undirected graph

In a Python plotting application, I have an undirected connected graph, not necessarily simple, that I'd like to cover with paths such that each edge is contained in exactly one path. The number of ...
91 views

Regular Expressions that converts into unambiguous automata

Brüggemann-Klein and Wood (1992) proved that a certain kind of regular expressions, that they call “Deterministic Regular expressions”, when converted into automata using the Glushkov's Construction, ...
19 views

algebraic specification online course, do you know any?

I am in need of an online course/tutorial on algebraic specification. Do you know any good resource with problems with solutions?
104 views

Derandomizing arbitrary width *read-many* and *ordered* branching programs?

Modifying following TedP We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
123 views

Oracle-Decidability of Algebraic Independence

Consider numbers $x_1,...,x_n\in \mathbb{R}$ given by TMs $M_1,...,M_n$ such that $M_i$ approximates $x_i$ to an arbitrary precision (by allowing it to run longer and longer). I am interested in the ...
63 views

Does this sequence of quantified boolean formulas make sense to anyone else? most of these qbfs are valid [closed]

do all logicians on earth know that a question is a qbf? yes and they know the answer to a qbf is always yes or no? yes ok good all logicians know that solving one qbf is hard and buggy? yes but ...
118 views

Finding top-K items in a sliding window

Imagine we have a stream of bank transactions. Each transaction has a target account and some amount of money. I'd like to find top K accounts over some period of time (e.g. last 7 days) which ...
71 views

Fine-Grained Hardness for Undirected Hamiltonicity

The fastest known algorithm for detecting Hamiltonian cycles in directed graphs on $n$ nodes runs in essentially $2^n\text{poly}(n)$ time. However, for undirected graphs on $n$ nodes, there is an ...
106 views

Status of certain problems in knot theory

I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-...
258 views

Cook inspiration for NP completeness

An academic descendant of Cook just lectured on NP completeness. He said that the idea came from a well-known theorem in first-order logic that talks about completeness of satisfiability for ...
28 views

Bounded-Frequency Minimum Set Cover Problem

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets. Can this problem be solved in polynomial time? Is there a nontrivial upper ...
96 views

Does any physical process constitute a "computation"? [closed]

I am trying to sharpen the convex hull of what seems like a (surprisingly) stubborn concept to enclose based on answers here, as well as conversations with others, around the nature of what actually ...
51 views

Canonical tester for dense graphs: from tester to removal lemma?

A theorem of Goldreich and Trevisan [1] on property testing in the dense graph model states the following (docusing on the one-sided part): Suppose there exists a one-sided testing graph algorithm ...
155 views

State of the art approximation algorithm for $\text{MAXCUT}$ that does better than Goemans and Williamson

I had thought that the Goemans-Williamson approximation algorithm was the best for MAXCUT. To quote from Wikipedia: The polynomial-time approximation algorithm for Max-Cut with the best known ...
219 views

We are given a matrix $M$ with $0/1$ entries and the matrix is square of $n$ dimensions. We are given two integers $a$ and $b$ with promise one of the values is the permanent. Is there a faster than $... 1answer 88 views Maximally Permissive Strategies for Safety Properties Different definitions of maximally permissive strategies exist. For instance, in (Bernet, Janin, and Walukiewicz 2002), strategies are compared by looking at inclusion of the behaviors/outcomes they ... 1answer 51 views Maximize the absolute value of connected nodes after$k$modifications Given a graph$G=\{V,E\}$, each node$i$has a value$v_i$. Given budget$k$, we have$k$chance to add 1 or minus 1 for a node's value, for example,$v'_i=v_i+1$or$v'_i=v_i-1$. In particular,$v'_i$... 4answers 2k views What would be the consequences of PH=PSPACE? A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of$NP=PSPACE$. The answers list quite a few collapse consequences, including$NP=coNP$and others, providing ... 2answers 132 views Algebraic characterisation of star-free safety languages It is known that star-free languages are definable by aperiodic syntactic monoids. But is there any algebraic characterisation of star-free safety$\omega$-languages? Edit: A language$L$is safety if ... 4answers 4k views Consequences of NP=PSPACE What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones. In particular, would it have any ... 1answer 259 views Pagerank in directed *acyclic* graphs (DAG) I deal with pagerank computations on large directed acyclic graphs (DAG). I found no reference to work on this specific case, only some work on pagerank in more specific cases, e.g., PageRank of Scale ... 0answers 75 views On-line pagerank in a streaming DAG (Directed Acyclic Graph) Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge$(u,v)$is given only after all incoming edges of$u$are given. Let us denote by$n$and$m$the number of vertices ... 1answer 72 views Can this special case of Node Weighted Steiner Tree be solved in polynomial time? Consider the node-weighted steiner problem: Input: a graph$G=(V,E)$, a set$T\subseteq V$of terminals, a weight function$w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight subset$S \...
I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David. The theorem 6.7 has several equivalent statements for a class of functions $H$. The first ...
Let $P_1$ and $P_2$ be two disjoint point sets in $\mathbb{R}^d$ and $n = \vert P_1\vert = \vert P_2\vert$ and $P = P_1\cup P_2$. Let $c^\star$ be the optimal 1-median for $P$ and $opt^\star$ is the ...