12
$\begingroup$

Some time ago, I posted a reference request for graph problems where we want to find a 2-partition of the edges where both sets fulfill a property not related to their cardinality. I was trying to prove that the following problem is NP-hard:

Given a tournament $G = (V,E)$, is there a feedback arc set $F \subseteq E$ in $G$ that defines a transitive relation?

I do have a construction for an attempt at a proof, but it seems that that is going to run into a dead end, so I thought I might ask here to see whether I'm missing something obvious. In order to not confine your creativity to lines of thought similar to the ones I used, I won't post my attempt here.

Is this problem NP-hard? If so, how to prove it?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ perfect, thanks! (I deleted the comment because I wrote G=(E,V) instead of the standard G=(V,E) :-) $\endgroup$
    – Marzio De Biasi
    Commented Jan 20, 2014 at 16:13
  • 6
    $\begingroup$ If I understand correctly, this is equivalent to asking whether the edges in a tournament can be partitioned into two DAGs, one of which is transitively closed. $\endgroup$
    – dspyz
    Commented Jan 22, 2014 at 2:51
  • 1
    $\begingroup$ re dspyz's comment, there are not that many problems on DAGs that can be studied due to the complexity of them. there arent even that many theorems at all on DAGs it would seem. trees are a little more accessible. your problem (while apparently interesting as reflected in votes) seems to mix a lot of unusual elements together & not fit into any particular category. $\endgroup$
    – vzn
    Commented Jan 23, 2014 at 3:59
  • 5
    $\begingroup$ @IgorShinkar the arcs of any digraph can be partitioned trivially into two DAGs: order the vertices arbitrarily; one DAG is the forward edges, the other DAG is the backward edges. $\endgroup$
    – Sasho Nikolov
    Commented Jan 28, 2014 at 0:00
  • 1
    $\begingroup$ @SashoNikolov of course! $\endgroup$
    – Igor Shinkar
    Commented Jan 28, 2014 at 7:08

3 Answers 3

Reset to default
4
$\begingroup$

To add a little context, here's a construction for a graph that doesn't have a transitive feedback arc set. For this construction, I'll use the following gadget graph:

gadget graph used to force implications

This tournament has the following properties (which I checked using a program, I didn't prove it formally):

  • if (2,7) is not in a given TFAS, then (1,3) is
  • if (5,1) is in a given TFAS, then so is (3,6)
  • if (7,3) is in a given TFAS, then (5,1) is not

or slightly abusing predicate logic notation:

  • $\neg (2,7) \rightarrow (1,3)$
  • $(5,1) \rightarrow (3,6)$
  • $(7,3) \rightarrow \neg (5,1)$

You'll notice that for each implication, the two edges are pairwise disjoint, so the following construction works:

construction for graph that doesn't have a TFAS

I hope you can make out the idea of the graph: using the implication properties of the tournament above, we can construct a graph in which each transitive feedback arc set both includes and doesn't include the edge $A$, i.e. a contradiction, which means the graph doesn't have a transitive feedback arc set. Any completion of that graph cannot have one either since the same contradiction will remain in any completion. I left out a large number of vertices, all of which can be derived from substituting the tournament above for the implications.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I'm sorry, I don't follow. Is there any reason you can't just post a list of the edges so I can run it through an ASP solver and try to verify it? According to clingo, your gadget graph has 8 different TFAS's. Here's the smallest one: tfas(edge(5,0)) tfas(edge(6,0)) tfas(edge(7,0)) tfas(edge(6,2)) tfas(edge(7,3)) tfas(edge(1,2)) tfas(edge(1,3)) tfas(edge(7,5)) $\endgroup$
    – dspyz
    Commented Jan 30, 2014 at 4:13
  • $\begingroup$ I just noticed you mentioned the edge (6,3) in the gadget graph, but the image you provided has the edge (3,6) $\endgroup$
    – dspyz
    Commented Jan 30, 2014 at 5:20
  • $\begingroup$ I figured it out, see my updated answer: cstheory.stackexchange.com/a/20778/13643 $\endgroup$
    – dspyz
    Commented Jan 30, 2014 at 6:32
  • $\begingroup$ @dspyz I thought the construction was clearer than just a list of the edges, since if my reasoning isn't wrong, all that would be required to verify is whether the tournament above the construction actually has those implication properties. Thanks for pointing out the mistake about edge (3,6)! I also got 8 TFAS for that gadget, the one you listed being one of them. $\endgroup$
    – G. Bach
    Commented Jan 30, 2014 at 14:02
  • $\begingroup$ I'm sorry. I constructed the graph wrong. I fixed it and clingo now reports no TFAS. $\endgroup$
    – dspyz
    Commented Feb 1, 2014 at 19:10
1
+100
$\begingroup$

I ran a short clingo program which reported no graph without a TFAS, but there was a bug. I fixed it and now it verifies there's no graph without a TFAS for n=8 or less. For n=9, it finds this one:

is_edge(edge(2,3)) is_edge(edge(1,4)) is_edge(edge(2,4)) is_edge(edge(3,5)) is_edge(edge(4,5)) is_edge(edge(1,6)) is_edge(edge(2,6)) is_edge(edge(3,6)) is_edge(edge(5,6)) is_edge(edge(1,7)) is_edge(edge(4,7)) is_edge(edge(5,7)) is_edge(edge(6,7)) is_edge(edge(1,8)) is_edge(edge(3,8)) is_edge(edge(4,8)) is_edge(edge(5,9)) is_edge(edge(6,9)) is_edge(edge(7,9)) is_edge(edge(2,1)) is_edge(edge(3,1)) is_edge(edge(4,3)) is_edge(edge(5,1)) is_edge(edge(5,2)) is_edge(edge(6,4)) is_edge(edge(7,2)) is_edge(edge(7,3)) is_edge(edge(8,2)) is_edge(edge(8,5)) is_edge(edge(8,6)) is_edge(edge(8,7)) is_edge(edge(9,1)) is_edge(edge(9,2)) is_edge(edge(9,3)) is_edge(edge(9,4)) is_edge(edge(9,8))

Here's the (fixed) encoding

% tfas.asp
#show is_edge/1.
vertex(1..n).

opp_edges(edge(A,B),edge(B,A)) :- vertex(A), vertex(B), A < B.
possible_edge(E1;E2) :- opp_edges(E1,E2).

{is_edge(E1); is_edge(E2)} = 1 :- opp_edges(E1, E2).
ntfas(E) :- possible_edge(E), not is_edge(E).
ntfas(edge(X, X)) :- vertex(X).

tfas(E) | fs(E) :- is_edge(E).
ntfas(E) :- fs(E).

broken :- ntfas(edge(A,C)), tfas(edge(A, B)), tfas(edge(B,C)).

reachable(X, Y) :- fs(edge(X, Y)), is_edge(edge(X, Y)).
reachable(X, Z) :- reachable(X, Y), fs(edge(Y, Z)), is_edge(edge(Y, Z)).
broken :- reachable(X, X).

tfas(E) :- broken, possible_edge(E).
fs(E) :- broken, possible_edge(E).
:- not broken.

Run it with clingo -c n=7 tfas.asp (Using clingo 4.2.1)

(the n=7 indicates graphs of exactly 7 vertices)

It should return satisfiable if and only if there exists a graph with no TFAS on 7 vertices.

Ok, I figured out what graph @G.Bach was describing and coded it up in clingo (see the clingo description below. It starts with a description of the gadget graph and proceeds to describe how to join copies of it together to get the full 34-vertex tournament graph G.Bach is describing. I've attached the grounded graph description as well).

I then proceeded to run clingo on that graph and it claimed to have found a TFAS with 241 edges. But I made a mistake in the graph encoding. I fixed the mistake and clingo now reports unsatisfiable (ie there is no TFAS).

Here's the program for finding TFAS's on a graph

{tfas(E)} :- is_edge(E).
:- not tfas(edge(A,C)), tfas(edge(A, B)), tfas(edge(B,C)).

reachable(X, Y) :- not tfas(edge(X, Y)), is_edge(edge(X, Y)).
reachable(X, Z) :- reachable(X, Y), not tfas(edge(Y, Z)), is_edge(edge(Y, Z)).
:- reachable(X, X).

tfas_count(N) :- N = #count{tfas(E) : tfas(E)}.

#show tfas/1.
#show tfas_count/1.

Here's the (updated) program for generating G.Bach's graph. I added indicators at the end to check that the graph is a well-formed tournament graph:

gadget_vertex(0..7).

gadget_edge(0,1).
gadget_edge(0,2).
gadget_edge(0,3).
gadget_edge(0,4).
gadget_edge(1,2).
gadget_edge(1,3).
gadget_edge(1,6).
gadget_edge(1,7).
gadget_edge(2,3).
gadget_edge(2,4).
gadget_edge(2,5).
gadget_edge(2,7).
gadget_edge(3,4).
gadget_edge(3,5).
gadget_edge(3,6).
gadget_edge(4,1).
gadget_edge(4,5).
gadget_edge(4,6).
gadget_edge(4,7).
gadget_edge(5,0).
gadget_edge(5,1).
gadget_edge(5,6).
gadget_edge(6,0).
gadget_edge(6,2).
gadget_edge(6,7).
gadget_edge(7,0).
gadget_edge(7,3).
gadget_edge(7,5).

special_edge(a;b;c;d;e).

forces(a,b).
forces(b,c).
forcesn(c,a).
nforces(a,d).
forces(d,e).
forces(e,a).

relates(A,B) :- forces(A,B).
relates(A,B) :- nforces(A,B).
relates(A,B) :- forcesn(A,B).

is_se_pair(se_pair(A,B)) :- relates(A,B).
vertex_name(v(V,P)) :- gadget_vertex(V), is_se_pair(P).

matches(from(A), v(5, se_pair(A,B))) :- forces(A,B).
matches(to(A), v(1, se_pair(A,B))) :- forces(A,B).
matches(from(B), v(3, se_pair(A,B))) :- forces(A,B).
matches(to(B), v(6, se_pair(A,B))) :- forces(A,B).

matches(from(A), v(2, se_pair(A,B))) :- nforces(A,B).
matches(to(A), v(7, se_pair(A,B))) :- nforces(A,B).
matches(from(B), v(1, se_pair(A,B))) :- nforces(A,B).
matches(to(B), v(3, se_pair(A,B))) :- nforces(A,B).

matches(from(A), v(7, se_pair(A,B))) :- forcesn(A,B).
matches(to(A), v(3, se_pair(A,B))) :- forcesn(A,B).
matches(from(B), v(5, se_pair(A,B))) :- forcesn(A,B).
matches(to(B), v(1, se_pair(A,B))) :- forcesn(A,B).

same_vertex(V, V) :- vertex_name(V).
same_vertex(M, N; N, M) :- matches(X, M), matches(X, N).

already_found(v(Y,N2)) :- vertex_name(v(X,N1)), same_vertex(v(X,N1),v(Y,N2)), N1 < N2.
vertex(V) :- vertex_name(V), not already_found(V).

named_gadget_edge(edge(v(X,SE),v(Y,SE))) :- gadget_edge(X,Y), is_se_pair(SE).
from_gadget_edge_named(edge(A, B), edge(C,D)) :- named_gadget_edge(edge(C,D)), same_vertex(A,C), same_vertex(B,D), vertex(A), vertex(B).
from_gadget_edge(edge(A,B)) :- from_gadget_edge_named(edge(A,B),edge(C,D)).
is_edge(E) :- from_gadget_edge(E).
is_edge(edge(A,B)) :- vertex(A), vertex(B), A < B, not from_gadget_edge(edge(B,A)).

vertex_count(VN) :- VN = #count{vertex(V) : vertex(V)}.
edge_count(EN) :- EN = #count{is_edge(E) : is_edge(E)}.

#show vertex_count/1.
#show edge_count/1.

bidirectional :- is_edge(edge(A,B)), is_edge(edge(B,A)).
phantom_vertex :- is_edge(edge(A,B)), not vertex(A).
phantom_vertex :- is_edge(edge(A,B)), not vertex(B).
incomplete :- vertex(A), vertex(B), not is_edge(edge(A,B)), not is_edge(edge(B,A)), A != B.

#show bidirectional/0.
#show phantom_vertex/0.
#show incomplete/0.
Improve this answer
$\endgroup$
17
  • $\begingroup$ I'm positive there is a tournament on 18 vertices that doesn't have a TFAS. $\endgroup$
    – G. Bach
    Commented Jan 29, 2014 at 19:07
  • $\begingroup$ Can you please give it as an example? Just attach a file with the edges listed $\endgroup$
    – dspyz
    Commented Jan 29, 2014 at 19:08
  • $\begingroup$ How do I attach a file? It may take a few hours, I don't have the tournament to hand right now. I also miscalculated, it should have 34 vertices. It's probably easier to verify if I give the building blocks of the tournament. $\endgroup$
    – G. Bach
    Commented Jan 29, 2014 at 19:25
  • $\begingroup$ Upload to any file host and link to it (see meta.stackexchange.com/a/4643/185877), or if it has a regular structure, just describe it (give the building blocks) $\endgroup$
    – dspyz
    Commented Jan 29, 2014 at 19:29
  • $\begingroup$ cant follow your code yet but youre asserting that you are validating for finite n≤20? last sentence which asserts it is true for all $n$... if so quite remarkable(!) but not a "solution" to the general question (which would require a proof of all size cases). ps thx for working/posting an empirical observation to this site which in general is rare ... @G.Bach it would be great to see an image of the graph rather than just edge/vertex lists if possible $\endgroup$
    – vzn
    Commented Jan 30, 2014 at 2:07
0
$\begingroup$

SWAG conjecture [something better than nothing?]:

Given a tournament $G = (V,E)$, there exists a feedback arc set $F \subseteq E$ in $G$ that defines a transitive relation. hence the problem is $O(1)$

notes: shootdown counterexamples welcome! none seem to be given so far. even better would be some observations of patterns of edge orientations related to particular graph classes. or some more motivation or tieing it into some existing literature. offered in the style of Proofs and refutations (Lakatos)... also, since it seems such an offbeat problem that doesnt [yet?] relate to much, suggest studying it empirically....

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ I did run a program to check whether this holds and found that there are tournaments that do not have a transitive feedback arc set. I'll post one tomorrow, I won't get around to it today. $\endgroup$
    – G. Bach
    Commented Jan 28, 2014 at 17:09
  • $\begingroup$ @vzn can you prove the conjecture for a random tournament? $\endgroup$
    – Igor Shinkar
    Commented Jan 28, 2014 at 19:53
  • $\begingroup$ Counterexample with only 5 vertices: a->b, a->c, b->c, d->a, b->d, c->d, e->a, e->b, c->e, d->e. For any four vertices, the induced graph contains a cycle, so a transitive DAG can contain at most 3 edges among 3 vertices of the graph. There are only 5 possibilities (all other triplets are cycles): abc,eab,dea,bcd,cde It's easy to check that in each of the five cases there is a cycle among the other 7 edges $\endgroup$
    – dspyz
    Commented Jan 29, 2014 at 6:31
  • 1
    $\begingroup$ Yeah, nvr mind, it's not a counterexample $\endgroup$
    – dspyz
    Commented Jan 29, 2014 at 6:39
  • 1
    $\begingroup$ @dspyz I ran a brute force check on all tournaments on up to 8 vertices. All of them have transitive feedback arc sets, but there are some you can use to build a tournament that doesn't. $\endgroup$
    – G. Bach
    Commented Jan 29, 2014 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.