0
$\begingroup$

In a question I had asked earlier, I was interested in knowing whether we could decide in polynomial time whether, for a directed graph $G$ with every one of its vertices belonging to an edge, a size-$w$ watch set, with $w$ at least half the number of vertices in $G$, exists (see the linked question). Several users showed that, in fact, such a polynomial time decider does not exist.

I'm interested in whether a polynomial time decider exists for a variant of this problem. Now, suppose that $G = (V,E)$ is an $n$-vertex directed graph with the property that every vertex in $G$ has an edge entering it. That is, for each vertex $v \in V$, there is an edge $(u,v)$ in $E$. With this in mind, consider the problem of deciding whether, for a given $w \geq 2n/3$, $G$ has a size-$w$ watch set. With the constraint that every vertex has an edge entering it, I'm not sure that we are able to reduce from arbitrary directed graphs, as Discrete lizard showed we could do in my earlier question. What I suspect is that any graph of this type must have a size-$w$ watch set, with $w \geq 2n/3$.

$\endgroup$
  • $\begingroup$ Actually, I think I can prove by induction the conjecture I give in the last sentence. I'll see if I can come up with a solution. $\endgroup$ – R. Potts Apr 29 '17 at 19:52
  • 1
    $\begingroup$ I suggest you try random testing: generate a million small random graphs with this property; for each, find the smallest watch set (e.g., through exhaustive search); and check whether your conjecture seems to hold in every such case. I bet this will either help give you higher confidence in the conjecture (that it's worth your time to try to prove) or find a counterexample. $\endgroup$ – D.W. Apr 30 '17 at 5:56
  • $\begingroup$ @D.W. Thanks, I'll try something like this. $\endgroup$ – R. Potts Apr 30 '17 at 6:11
  • 1
    $\begingroup$ @D.W. Personally, I find that directly trying to construct a counter example is more constructive than randomly letting 'someone else' experiment. In the case of experiments, you only really can understand anything if you actually find a counter example, otherwise you can only say that randomly searching for a counter-example is hard, which is essentially saying you don't understand anything! But if you try to construct a counter example, you often either get one or see why it is hard to construct a counter-example, which will often lead to a proof! ... $\endgroup$ – Discrete lizard May 2 '17 at 8:49
  • $\begingroup$ ... Of course, experiments can be very useful to find tricky cases that you haven't been able to think of, but I only see the value if you have actually tried (and 'unsatisfyingly' failed!) to find tricky cases. $\endgroup$ – Discrete lizard May 2 '17 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.