bio | website | |
---|---|---|
location | Newcastle, Australia | |
age | 34 | |
visits | member for | 4 years, 3 months |
seen | 2 days ago | |
stats | profile views | 1,286 |
May 14 |
awarded | Nice Answer |
May 11 |
comment |
What is known about the complexity of this covering problem?
@RupeiXu Yes, it means that for every vertex $v\in V\setminus X$ the intersection of $X$ and the neighbourhood of $v$ is either empty or has at least size 2. |
Apr 22 |
comment |
What is known about the complexity of this covering problem?
@DominicvanderZypen Yes. I can start the algorithm in the original post with a singleton $S=\{v\}$. If I get stuck then the complement of the final set is a critical set $\neq V$. Now let's do this for every start vertex $v\in V$. If we reach $S=V$ in each case it follows that every vertex is contained in every critical set, and therefore $V$ is the only critical set. |
Apr 21 |
comment |
What is known about the complexity of this covering problem?
@DimaPasechnik Note that in order to check feasibility it is not necessary to know all critical sets. The decision version of the problem is in NP, and I've added that to the question. |
Apr 21 |
revised |
What is known about the complexity of this covering problem?
added argument for membership in NP |
Apr 21 |
asked | What is known about the complexity of this covering problem? |
Apr 13 |
comment |
Segments on a family of parallel lines
For the case of infinite $I$, we can argue as follows: Fix two distinct $i,j\in I$. Then $X=L_i\cap L_j$ is compact, and we have that $X\cap\bigcap_{k\in J}(X\cap L_k)\neq\emptyset$ for every finite $K\subseteq I$. But now all considered sets in the intersection are closed subsets of the compact set $X$, and it follows that $\bigcap_{i\in I}L_i\neq\emptyset$. |
Feb 1 |
awarded | Yearling |
Jan 25 |
awarded | Custodian |
Jan 25 |
reviewed | Approve Counting linearly ordered subsets of maximal length in partially ordered $d$-tuples of nonnegative integers |
Jan 24 |
revised |
Counting linearly ordered subsets of maximal length in partially ordered $d$-tuples of nonnegative integers
added 407 characters in body |
Jan 24 |
answered | Counting linearly ordered subsets of maximal length in partially ordered $d$-tuples of nonnegative integers |
Jan 23 |
comment |
Is the Manickam-Miklós-Singhi Conjecture solved?
The paper has appeared link.springer.com/article/10.1134%2FS0032946014040048 |
Jan 3 |
revised |
covering designs of the form $(v,k,2)$
added 208 characters in body |
Jan 3 |
revised |
covering designs of the form $(v,k,2)$
added 470 characters in body |
Jan 3 |
revised |
covering designs of the form $(v,k,2)$
added 341 characters in body |
Jan 3 |
revised |
covering designs of the form $(v,k,2)$
added 341 characters in body |
Jan 3 |
revised |
covering designs of the form $(v,k,2)$
added 178 characters in body |
Jan 3 |
answered | covering designs of the form $(v,k,2)$ |
Dec 29 |
answered | Stable Household Formation |