1,548 reputation
715
bio website
location Newcastle, Australia
age 34
visits member for 4 years, 3 months
seen 2 days ago

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